35. Sudoku Solver

Fill empty cells one at a time. For each, try digits 1-9 that don't already appear in the cell's row, column, or 3x3 box; recurse, and backtrack if a choice leads to a dead end.

Constrained backtracking

Precompute, for each row, column, and 3x3 box, the set of digits already present. Collect the empty cells. Then recursively fill them:

for each empty cell (i, j):
    for d in '1'..'9':
        if d not in row[i], col[j], box[b]:
            place d, update sets, recurse
            if solved: return True
            undo (backtrack)
    return False

The constraint sets make each validity check O(1), and the puzzle's unique solution guarantees success.

Complexity

• Time: exponential worst case, fast in practice with pruning.
• Space: O(1) (fixed 9x9 board and constraint sets).

class Solution {
    private boolean[][] rows = new boolean[9][10];
    private boolean[][] cols = new boolean[9][10];
    private boolean[][] boxes = new boolean[9][10];
    private char[][] board;

    public char[][] solveSudoku(char[][] board) {
        this.board = board;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int d = board[i][j] - '0';
                    rows[i][d] = cols[j][d] = boxes[(i / 3) * 3 + j / 3][d] = true;
                }
            }
        }
        backtrack(0, 0);
        return board;
    }

    private boolean backtrack(int r, int c) {
        if (r == 9) return true;
        int nr = c == 8 ? r + 1 : r;
        int nc = c == 8 ? 0 : c + 1;
        if (board[r][c] != '.') return backtrack(nr, nc);
        int b = (r / 3) * 3 + c / 3;
        for (int d = 1; d <= 9; d++) {
            if (!rows[r][d] && !cols[c][d] && !boxes[b][d]) {
                board[r][c] = (char) ('0' + d);
                rows[r][d] = cols[c][d] = boxes[b][d] = true;
                if (backtrack(nr, nc)) return true;
                board[r][c] = '.';
                rows[r][d] = cols[c][d] = boxes[b][d] = false;
            }
        }
        return false;
    }
}