Obsidian Notes

Sudoku Solver

6 min read

Description

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:
Input: 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"]]
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"]]

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit 1-9 or '.'.
  • It is guaranteed that the input board has only one solution.

Brute Force Approach: Standard Backtracking with Grid Scan Validation

Intuition

Scan the 9×9 board cell-by-cell. Whenever an empty cell '.' is encountered:

  1. Try placing digits '1' through '9'.
  2. Check if placement is valid by scanning the row, column, and 3×3 sub-box using a loop (O(9) time check).
  3. Recurse to solve the rest of the board. If a branch fills the board, return true.
  4. If no digits '1'-'9' lead to a solution, backtrack (board[i][j] = '.') and return false.
class Solution {
    public void solveSudoku(char[][] board) {
        backtrack(board);
    }
 
    private boolean backtrack(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            // 1. CHOOSE
                            board[i][j] = c;
 
                            // 2. EXPLORE
                            if (backtrack(board)) {
                                return true;
                            }
 
                            // 3. UN-CHOOSE (Backtrack)
                            board[i][j] = '.';
                        }
                    }
                    return false; // Triggers backtracking if no digit 1-9 is valid
                }
            }
        }
        return true; // All empty spots filled successfully
    }
 
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            // Check same row
            if (board[row][i] == c) return false;
            // Check same column
            if (board[i][col] == c) return false;
            // Check 3x3 sub-box
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
        }
        return true;
    }
}

Complexity

  • Time Complexity: O(9N) — N is the number of empty cells (up to 81). For each empty cell, up to 9 choices are evaluated with an O(9) validity check.
  • Space Complexity: O(N) — Maximum recursion stack depth equals the number of empty cells.

Most Optimized Solution: Backtracking with O(1) State Tracking

Intuition

Instead of running an O(9) loop for isValid() on every digit placement, use three boolean arrays to check availability in O(1) constant time:

  1. rows[r][num]: Tracks if number num is present in row r.
  2. cols[c][num]: Tracks if number num is present in column c.
  3. boxes[boxIdx][num]: Tracks if number num is present in 3×3 box boxIdx, where boxIdx = (r / 3) * 3 + (c / 3).

Additionally, move linearly cell-by-cell (r, c) instead of re-scanning the board from (0, 0) at every recursive step.

class Solution {
    private boolean[][] rows = new boolean[9][10];
    private boolean[][] cols = new boolean[9][10];
    private boolean[][] boxes = new boolean[9][10];
 
    public void solveSudoku(char[][] board) {
        // Step 1: Pre-fill state arrays with existing digits on the board
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] != '.') {
                    int num = board[r][c] - '0';
                    int boxIdx = (r / 3) * 3 + (c / 3);
                    rows[r][num] = true;
                    cols[c][num] = true;
                    boxes[boxIdx][num] = true;
                }
            }
        }
 
        backtrack(board, 0, 0);
    }
 
    private boolean backtrack(char[][] board, int r, int c) {
        // Base case: Reached past the last row
        if (r == 9) return true;
 
        // Compute next cell coordinates
        int nextR = (c == 8) ? r + 1 : r;
        int nextC = (c == 8) ? 0 : c + 1;
 
        // Skip non-empty cells
        if (board[r][c] != '.') {
            return backtrack(board, nextR, nextC);
        }
 
        int boxIdx = (r / 3) * 3 + (c / 3);
 
        for (int num = 1; num <= 9; num++) {
            // Step 2: O(1) state check
            if (!rows[r][num] && !cols[c][num] && !boxes[boxIdx][num]) {
                // 1. CHOOSE
                board[r][c] = (char) (num + '0');
                rows[r][num] = true;
                cols[c][num] = true;
                boxes[boxIdx][num] = true;
 
                // 2. EXPLORE
                if (backtrack(board, nextR, nextC)) {
                    return true;
                }
 
                // 3. UN-CHOOSE (Backtrack)
                board[r][c] = '.';
                rows[r][num] = false;
                cols[c][num] = false;
                boxes[boxIdx][num] = false;
            }
        }
 
        return false;
    }
}

Complexity

  • Time Complexity: O(9N) — Significantly faster execution in practice due to O(1) constant-time checks and direct linear traversal without re-scanning solved cells.
  • Space Complexity: O(1) — Fixed auxiliary storage for state matrices (9×10) and maximum call stack depth bounded by 81.

Easy Memory Rule

“Try 1-9 at empty cells. Validate row, col, and box index (r / 3) * 3 + (c / 3). If valid → place digit → recurse → backtrack.”

1. Why [9][10] Dimensions?

private boolean[][] rows = new boolean[9][10];
  • First Dimension (9): Represents the 9 rows (or 9 columns / 9 boxes) on the Sudoku board, indexed from 0 to 8.
  • Second Dimension (10): Represents the Sudoku digits 1 through 9.
  • If we created an array of size 9, valid indices would be 0 through 8. To check digit 5, we would have to write rows[r][5 - 1].
  • By creating an array of size 10, indices range from 0 to 9. We can use the digit directly as the index without subtracting 1:
  • rows[r][1] tracks if digit 1 is used
  • rows[r][9] tracks if digit 9 is used
  • Index 0 is simply left unused.

2. Why the nextR and nextC Condition?

int nextR = (c == 8) ? r + 1 : r;
int nextC = (c == 8) ? 0 : c + 1;

This moves cell-by-cell through the grid in standard reading order (left-to-right, row-by-row):

(0,0) -> (0,1) -> ... -> (0,8)
                          ↓
(1,0) -> (1,1) -> ... -> (1,8)

  • **When c < 8** (not at the end of the row):

  • Move to the right neighbor in the same row: nextR = r, nextC = c + 1.

  • **When c == 8** (reached the end of the row):

  • Wrap around to the start of the next row: nextR = r + 1, nextC = 0.

Backlinks