LietCode
Sudoku Solver

Sudoku Solver

Abhi's photo
Abhi
·

4 min read

Explain the Problem

Write a program to solve a Sudoku puzzle by filling the empty cells. The Sudoku board is a 9x9 grid, and each cell can contain a digit from 1 to 9. The puzzle has the following rules:

  1. Each row must contain the digits 1-9 without repetition.

  2. Each column must contain the digits 1-9 without repetition.

  3. Each of the nine 3x3 sub-grids must contain the digits 1-9 without repetition.

The input to the program is a partially filled 9x9 grid.

Example:

Input:

[
 ["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"]
]

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"]
]

Short, Easy-to-Remember Solution/Approach

To solve this problem, we can use a recursive backtracking approach:

  1. Recursive Function: We'll create a helper function that tries to fill each empty cell with digits from 1 to 9.

  2. Validity Check: Ensure that placing a digit in a cell follows Sudoku rules.

  3. Backtracking: If a valid digit placement is found, we proceed to the next cell. If not, we backtrack.

Solution in JavaScript with Code Commenting

Here's the JavaScript solution with detailed comments:

function solveSudoku(board) {
  const n = 9;

  // Helper function to check if placing num at (row, col) is valid
  function isValid(board, row, col, num) {
    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(col / 3) * 3;

    for (let i = 0; i < 9; i++) {
      // Check row, column, and 3x3 box
      if (board[row][i] === num || board[i][col] === num || board[boxRow + Math.floor(i / 3)][boxCol + i % 3] === num) {
        return false;
      }
    }

    return true;
  }

  // Helper function for backtracking
  function backtrack(board) {
    for (let row = 0; row < n; row++) {
      for (let col = 0; col < n; col++) {
        if (board[row][col] === '.') {
          for (let num = 1; num <= 9; num++) {
            const charNum = String(num);
            if (isValid(board, row, col, charNum)) {
              board[row][col] = charNum;
              if (backtrack(board)) {
                return true;
              }
              board[row][col] = '.';
            }
          }
          return false; // No valid number found, backtrack
        }
      }
    }
    return true; // All cells are filled
  }

  backtrack(board);
}

// Example usage:
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"]
];

solveSudoku(board);
console.log(board);

Explanation of the Solution in Simple Terms

Imagine you have a Sudoku puzzle, and you want to fill in the empty cells with numbers from 1 to 9 while following the rules of Sudoku.

  • Recursive Function: This is like a helper that tries to fill each empty cell with a valid number.

  • Validity Check: This means ensuring that placing a number in a cell doesn't break the rules of Sudoku (no repeated numbers in a row, column, or 3x3 box).

  • Backtracking: This means if the current placement of numbers doesn't lead to a solution, you go back and try a different placement.

For each empty cell, you try placing each number from 1 to 9. If placing a number is valid, you move to the next empty cell. If you fill all cells correctly, you've solved the puzzle. If not, you undo your last move and try another number.

Code Explanation in Pointers

  1. Initialize Board Size: Set the board size (9x9).

  2. Define Validity Check: Create a function to check if placing a number in a cell follows Sudoku rules.

  3. Define Backtracking Function: Create a recursive function to explore different placements.

  4. Loop Through Cells: Loop through each cell in the board.

  5. Check for Empty Cell: If a cell is empty, try placing numbers from 1 to 9.

  6. Check Validity: If the placement is valid, proceed to the next cell.

  7. Recursive Call: Call the function recursively with the updated board.

  8. Backtrack: If no valid number is found, undo the last placement and try the next number.

  9. Start Search: Start the search from the first cell.

Complexity Analysis

  • Time Complexity: O(9^(N*N)), where N is the size of the board (9). This is because we try each number in each cell.

  • Space Complexity: O(N*N), due to the recursion stack and the board storage.

backtracking