Skip to main content

Sudoku Solver (Hard)

This page is about how to solve sudoku using recursion and backtracking.

Explanation​

The Sudoku solver uses a backtracking algorithm to solve the puzzle. It recursively tries to fill in each cell by testing numbers from 1 to 9 and checks if they are valid according to the rules of Sudoku:

  • Each number must appear only once in each row.
  • Each number must appear only once in each column.
  • Each number must appear only once in each 3x3 subgrid.

If a valid number is found, the algorithm moves to the next empty cell. If no valid number is found, it backtracks to the previous cell and tries the next possible number.

Time Complexity​

  • Worst-case Time Complexity:

The algorithm tries all possible configurations for each empty cell. Since there are 9 possible values to try (1 to 9) for each empty cell, the worst-case time complexity is O(9^{N^2}), where N is the size of the grid (9 for a standard Sudoku). In the worst case, this could result in testing all 9 possible values for every empty cell.

However, in practice, the backtracking approach often finds a solution much faster, pruning invalid possibilities and terminating earlier. Hence, the worst-case complexity provides an upper bound. If we consider the number of empty spaces as K then the time would be O(9^k)

Space Complexity​

  • Without Recursion Stack: The board is a fixed 9x9 grid, so the space required to store the board is O(N^2), where N is the size of the grid (9). Therefore, without considering recursion stack space, the space complexity is O(N^2). If the board is already given then it is O(1) time complexity as you don't use any extra space to store the board.

  • With Recursion Stack: The recursion stack depth will be proportional to the number of empty cells that the algorithm needs to explore. If there are K empty cells, the recursion stack will have a depth of O(K), where K is the number of empty cells in the board.

Code Implementation​

/**
 * LeetCode 37 - Sudoku Solver (Hard)
 * This function solves a Sudoku puzzle using backtracking.
 */

// Main function to solve the Sudoku board
const solveSudoku = function (board) {
  for (let row = 0; row < board.length; row++) {
    // Loop through each row
    for (let col = 0; col < board[row].length; col++) {
      // Loop through each column in the row
      if (board[row][col] === ".") {
        // Check if the current cell is empty
        for (let n = 1; n <= 9; n++) {
          // Try placing numbers 1 to 9
          if (isValid(`${n}`, row, col, board)) {
            // Check if the number is valid for the current cell
            board[row][col] = `${n}`; // Place the number
            if (solveSudoku(board) === false) {
              // Recursively solve the rest of the board
              board[row][col] = "."; // If it doesn't work, backtrack
            } else {
              return true; // If it works, return true
            }
          }
        }
        return false; // No valid number found, so return false
      }
    }
  }
  return true; // Board is completely filled and valid
};

// Function to check if placing a number 'n' in the board is valid
const isValid = (n, row, col, board) => {
  for (let i = 0; i < board.length; i++) {
    // Check the row for duplicates
    if (board[row][i] === n) return false;
  }
  for (let i = 0; i < board.length; i++) {
    // Check the column for duplicates
    if (board[i][col] === n) return false;
  }
  const startRow = 3 * Math.floor(row / 3); // Find the starting row of the 3x3 subgrid
  const startCol = 3 * Math.floor(col / 3); // Find the starting column of the 3x3 subgrid
  for (let i = 0; i < 9; i++) {
    // Loop through the 3x3 subgrid
    if (board[startRow + Math.floor(i / 3)][startCol + (i % 3)] === `${n}`)
      return false;
  }
  return true; // If no conflicts, return true
};

const board = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"],
];

console.log("Before solving:");
console.log(board);

solveSudoku(board);

console.log("After solving:");
console.log(board);