Sudoko Recursion

Sudoku Solver

Problem Statement:

Given a 9x9 incomplete sudoku, solve it such that it becomes valid sudoku. Valid sudoku has the following properties.

1. All the rows should be filled with numbers(1 - 9) exactly once.
2. All the columns should be filled with numbers(1 - 9) exactly once.
3. Each 3x3 submatrix should be filled with numbers(1 - 9) exactly once.

Approach:

• Let’s see the step by step approach. Our main recursive function(solve()) is going to just do a plain matrix traversal of the sudoku board. When we find an empty cell, we pause and try to put all available numbers(1 - 9) in that particular empty cell.
• We need another loop to do that. But wait, we forgot one thing - the board has to satisfy all the conditions, right? So, for that we have another function(isValid()) which will check whether the number we have inserted into that empty cell will not violate any conditions.
• If it is violating, we try with the next number. If it is not, we call the same function recursively, but this time with the updated state of the board. Now, as usual it tries to fill the remaining cells in the board in the same way.
• Now we'll come to the returning values. If at any point we cannot insert any numbers from 1 - 9 in a particular cell, it means the current state of the board is wrong and we need to backtrack. An important point to follow is, we need to return false to let the parent function(which is called this function) know that we cannot fill this way. This will serve as a hint to that function, that it needs to try with the next possible number. Refer to the picture below.

C++ implementation

#include <iostream>
#include <vector>
using namespace std;
bool isValid(vector < vector < char >> & board, int row, int col, char c) {
  for (int i = 0; i < 9; i++) {
    if (board[i][col] == c)
      return false;

    if (board[row][i] == c)
      return false;

    if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
      return false;
  }
  return true;
}

bool solveSudoku(vector < vector < char >> & board) {
  for (int i = 0; i < board.size(); i++) {
    for (int j = 0; j < board[0].size(); j++) {
      if (board[i][j] == '.') {
        for (char c = '1'; c <= '9'; c++) {
          if (isValid(board, i, j, c)) {
            board[i][j] = c;

            if (solveSudoku(board))
              return true;
            else
              board[i][j] = '.';
          }
        }

        return false;
      }
    }
  }
  return true;
}
int main() {
    vector<vector<char>>board{
        {'9', '5', '7', '.', '1', '3', '.', '8', '4'},
        {'4', '8', '3', '.', '5', '7', '1', '.', '6'},
        {'.', '1', '2', '.', '4', '9', '5', '3', '7'},
        {'1', '7', '.', '3', '.', '4', '9', '.', '2'},
        {'5', '.', '4', '9', '7', '.', '3', '6', '.'},
        {'3', '.', '9', '5', '.', '8', '7', '.', '1'},
        {'8', '4', '5', '7', '9', '.', '6', '1', '3'},
        {'.', '9', '1', '.', '3', '6', '.', '7', '5'},
        {'7', '.', '6', '1', '8', '5', '4', '.', '9'}
    };
   
    solveSudoku(board);
        	
    for(int i= 0; i< 9; i++){
        for(int j= 0; j< 9; j++)
            cout<<board[i][j]<<" ";
            cout<<"\n";
    }
    return 0;
}

Time and Space Complexity

Time Complexity

• Worst Case: $O(9^{m})$ - Where $m$ is the number of empty cells. In the worst case (nearly empty board), the algorithm might try up to 9 values for each empty cell.
• Best Case: $O(1)$ - If the board is already solved.
• Average Case: Significantly better than worst case due to constraint pruning (the isValid function eliminates many invalid choices early).

Space Complexity

• $O(m)$ - Where $m$ is the number of empty cells. The recursion stack depth is proportional to the number of empty cells (maximum 81 for a 9x9 grid). The space is used for the recursion call stack.
• Additional auxiliary space: $O(1)$ - The algorithm uses constant extra space (only flags and counters).

Explanation

The Sudoku solver uses backtracking with constraint validation. For each empty cell, it tries digits 1-9, checking validity against row, column, and 3x3 box constraints. The isValid function prunes the search space significantly by rejecting invalid choices immediately. If a number works, the algorithm recursively solves the rest. If no valid digit exists for a cell, it backtracks and tries different values for the previous cell. This constraint-satisfaction approach is much more efficient than brute force.