Course4all
Join us on telegram
Home/dsa/Backtracking/Sudoku Solver

Sudoku Solver

Master this topic with zero to advance depth.

Sudoku Solver

The Sudoku Logic

Sudoku is a constraint satisfaction problem. A valid solution must have the digits 1-9 exactly once in every row, column, and 3×33 \times 3 subgrid.

Backtracking Search

We find an empty cell, try placing a digit from 1-9, and if it's valid, move to the next empty cell. If no digit works, we backtrack to the previous cell and try the next possible digit.

State Representation

Instead of searching the board to validate, we can use boolean matrices or bitmasks to track which numbers are present in each row, column, and box.

Solve a Sudoku puzzle using backtracking. Includes visual constraint check trace.

Hard

Examples

Input: board = [[5,3,.,.,7,.,.,.,.],...]
Output: [[5,3,4,6,7,8,9,1,2],...]
Approach 1

Level I: Basic Backtracking

Intuition

Try every number in every empty cell.

Iterate through cells. For each '.', try numbers 1-9. Check if the number is valid in the current row, column, and 3×33 \times 3 box by scanning the board.

⏱ O(9^{81}) in worst case, though much less in practice.💾 O(1) extra space beyond the board.

Detailed Dry Run

Dry Run Trace: | Cell | Value | Validity Check (R, C, B) | Action | | :---: | :---: | :----------------------- | :----- | | (0,2) | '4' | [✔, ✔, ✔] | Recurse| | (0,3) | '1' | [❌ Row Conflict] | Try 2 | | (0,3) | '6' | [✔, ✔, ✔] | Recurse|
java
class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
    private boolean solve(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)) {
                            board[i][j] = c;
                            if (solve(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    private boolean isValid(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;
    }
}
Approach 2

Level II: Optimized Backtracking (State Tracking with Bitmasks)

Intuition

Use bitmasks to mark digits used in rows, columns, and boxes for O(1)O(1) validation.

Maintain rows[9], cols[9], and boxes[9] as integers. rows[i] & (1 << digit) tells us if digit is already in row i. This replaces the O(9)O(9) isValid check with bitwise O(1)O(1).

⏱ O(9!^9)💾 O(1) (fixed number of integers).

Detailed Dry Run

To check if '5' can be placed at (0, 2): Check: (rows[0] | cols[2] | boxes[0]) & (1 << 5) == 0.

java
class Solution {
    int[] rows = new int[9], cols = new int[9], boxes = new int[9];
    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int d = board[i][j] - '1';
                    flip(i, j, d);
                }
            }
        }
        solve(board, 0, 0);
    }
    private boolean solve(char[][] board, int r, int c) {
        if (c == 9) return solve(board, r + 1, 0);
        if (r == 9) return true;
        if (board[r][c] != '.') return solve(board, r, c + 1);
        
        int mask = ~(rows[r] | cols[c] | boxes[(r/3)*3 + c/3]) & 0x1FF;
        for (int d = 0; d < 9; d++) {
            if ((mask & (1 << d)) != 0) {
                flip(r, c, d);
                board[r][c] = (char)('1' + d);
                if (solve(board, r, c + 1)) return true;
                board[r][c] = '.';
                flip(r, c, d);
            }
        }
        return false;
    }
    private void flip(int r, int c, int d) {
        rows[r] ^= (1 << d);
        cols[c] ^= (1 << d);
        boxes[(r/3)*3 + c/3] ^= (1 << d);
    }
}
← Previous QuestionCombinations
Next Question →Palindrome Partitioning