Sudoku Solver — Constraint Propagation + Backtracking

Basic backtracking

boolean solve(char[][] board) {
  for (int r = 0; r < 9; r++)
    for (int c = 0; c < 9; c++)
      if (board[r][c] == '.') {
        for (char d = '1'; d <= '9'; d++)
          if (isValid(board, r, c, d)) {
            board[r][c] = d;
            if (solve(board)) return true;
            board[r][c] = '.';
          }
        return false;
      }
  return true;
}

Validity check

Digit not in row + not in column + not in 3×3 box. Track with bitmasks for O(1).

Constraint propagation

Before backtracking: if cell has only one valid digit, fill it (naked single). If digit valid in only one cell in a unit, place it (hidden single).

Choose most-constrained cell first

Instead of scanning left-to-right, pick cell with fewest valid digits. Massive pruning.