Sudoku Solver using Backtracking

Sudoku is a popular puzzle game where you fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids (also known as regions or boxes) contains all of the digits from 1 to 9 without repetition.

Now, let’s implement a Sudoku Solver using a Backtracking algorithm in C++.

Sudoku Solver Algorithm

The Backtracking algorithm for solving Sudoku works like this:

1. Find an empty cell in the Sudoku grid.
2. Try all numbers from 1 to 9 (N) in that cell.
3. Check if the number is valid (i.e. number is not present in the same row, column, or 3x3 subgrid).
4. If the number is valid, recursively try to fill the next empty cell.
5. If all cells are filled, we have found a solution. If not, we backtrack and try the next number.

Code Implementation

//
//  main.cpp
//  Sudoku Solver
//
//  Created by Himanshu on 24/04/24.
//

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;


bool isSafe(vector<vector<int>>& board, int row, int col, int num, int N) {
    
    // Check row and column
    for (int i = 0; i < N; i++) {
        if (board[row][i] == num || board[i][col] == num) {
            return false;
        }
    }

    // Check subgrid
    int sqrtN = sqrt(N);
    int startRow = row - (row % sqrtN);
    int startCol = col - (col % sqrtN);
    
    for (int i = 0; i < sqrtN; i++) {
        for (int j = 0; j < sqrtN; j++) {
            if (board[i + startRow][j + startCol] == num) {
                return false;
            }
        }
    }

    return true;
}

bool solveSudoku(vector<vector<int>>& board, int N) {
    int row = -1, col = -1;

    // Find an empty cell
    bool foundEmpty = false;
    for (row = 0; row < N; row++) {
        for (col = 0; col < N; col++) {
            if (board[row][col] == 0) {
                foundEmpty = true;
                break;
            }
        }
        if (foundEmpty) {
            break;
        }
    }

    // If there is no empty cell left, Sudoku is solved
    if (!foundEmpty) {
        return true;
    }

    // Try numbers from 1 to N
    for (int num = 1; num <= N; num++) {
        if (isSafe(board, row, col, num, N)) {
            board[row][col] = num;

            // Recur to fill next cell
            if (solveSudoku(board, N)) {
                return true;
            }

            // If not a valid solution, backtrack
            board[row][col] = 0;
        }
    }

    return false; // No solution
}

void printSudoku(vector<vector<int>>& board, int N) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    int N = 9; // Size of Sudoku grid

    // Define the Sudoku grid (N x N), '0' represents empty cells
    vector<vector<int>> board = {
        {5, 0, 0, 6, 0, 0, 0, 0, 0},
        {8, 2, 7, 5, 0, 0, 0, 0, 0},
        {6, 0, 0, 8, 3, 1, 0, 0, 5},
        {0, 0, 2, 4, 0, 0, 0, 8, 7},
        {0, 0, 0, 0, 0, 0, 4, 0, 2},
        {0, 0, 4, 0, 0, 8, 0, 0, 6},
        {0, 9, 0, 1, 0, 7, 0, 0, 0},
        {2, 1, 0, 0, 0, 6, 7, 0, 0},
        {0, 5, 3, 0, 0, 0, 0, 0, 9}
    };

    if (solveSudoku(board, N)) {
        cout << "Solved Sudoku:" << endl << endl;
        printSudoku(board, N);
    } else {
        cout << "No solution exists." << endl;
    }

    return 0;
}

Output

Solved Sudoku:

5 3 1 6 7 2 9 4 8
8 2 7 5 4 9 6 3 1
6 4 9 8 3 1 2 7 5
9 6 2 4 1 5 3 8 7
1 8 5 7 6 3 4 9 2
3 7 4 9 2 8 5 1 6
4 9 6 1 5 7 8 2 3
2 1 8 3 9 6 7 5 4
7 5 3 2 8 4 1 6 9

Working of the code

  • The isSafe() function checks if it is safe to place a number num at position board[row][col] by checking the row, column, and each subgrid.
  • The solveSudoku() function recursively solves the Sudoku puzzle by trying numbers from 1 to N and backtracking if a solution is not valid.
  • Intuition behind inner or sub grid calculations,
    startRow = row - (row % sqrtN), could be understood from:
    startRow = (row / sqrtN) * sqrtN

    let’s consider the example of 9×9 grid (sqrtN is 3) for the sub-grid calculations:

    startRow = (row / sqrtN) * sqrtN,

    will result in startRow having values as 0 for rows (0-2), 3 for rows (3-5) and, 6 for rows (6-8).

    Also, we know that startRow is the additive factor used for rows for sub-grid correctness calculations. Similarly, startCol is the additive factor for the columns.

Note: This code works for all the values of N. However, for large values of N, it may take too long to finish, particularly for sparse grids. Also, you’ll need to tweak the code for values of N that are not perfect squares. This is because of the variable dimensions of sub-grids.

Time complexity: O(NN*N), N x N is the size of the grid.
Auxiliary Space: O(N2)

Explanation

Time complexity
O(N(N*N)), for every cell (number of cells is N*N), there are N possible options, hence this time complexity.

Space complexity
O(N2), to store the N x N Sudoku grid

Leave a Reply

Your email address will not be published. Required fields are marked *