Sudoku Solver

Examples:

Input: [[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]]

Output: [[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]

Explanation: The program fills in the empty cells with numbers from 1 to 9 such that each row, column, and 3x3 sub-grid contains each number exactly once.

Solutions

Backtracking

Time: O(9^(n*n))Space: O(n*n)

The backtracking approach is used to solve the Sudoku puzzle. The program tries to fill in the empty cells with numbers from 1 to 9. If a number is valid (i.e., it does not appear in the same row, column, or 3x3 sub-grid), the program recursively tries to fill in the rest of the puzzle. If it is not possible to fill in the rest of the puzzle, the program backtracks and tries a different number.

function solveSudoku(board) {
  function isValid(board, row, col, num) {
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === num) return false;
    }

    for (let i = 0; i < 9; i++) {
      if (board[i][col] === num) return false;
    }

    let startRow = row - (row % 3);

    let startCol = col - (col % 3);

    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (board[i + startRow][j + startCol] === num) return false;
      }
    }

    return true;
  }

  function solve(board) {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] === 0) {
          for (let num = 1; num <= 9; num++) {
            if (isValid(board, i, j, num)) {
              board[i][j] = num;

              if (solve(board)) return true;

              board[i][j] = 0;
            }
          }

          return false;
        }
      }
    }

    return true;
  }

  solve(board);
}

Constraints:

Examples:

Solutions

Backtracking

Follow-up: