Sudoku Solver - Solution & Explanation

Problem Overview: Sudoku Solver asks you to fill a partially completed 9×9 board so that every row, column, and 3×3 subgrid contains digits 1–9 exactly once. Empty cells are marked with '.'. The challenge is finding a valid assignment that satisfies all constraints without modifying the fixed cells.

The board naturally forms a matrix, and each placement must respect three constraints: unique numbers per row, column, and 3×3 box. Because every empty cell can potentially take multiple values, the search space grows quickly. The core strategy is to try candidates, verify constraints, and backtrack when a choice leads to an invalid state.

Approach 1: Backtracking (Exponential Time, O(9^(n)) worst case, O(81) space)

This approach treats Sudoku as a constraint satisfaction problem solved using backtracking. Iterate through the board to find an empty cell. Try digits 1–9 one by one and check whether placing the digit violates row, column, or 3×3 box rules. If the placement is valid, recursively attempt to solve the remaining cells. If a later step fails, revert the cell and try the next digit.

Validation is typically done by scanning the row, column, and subgrid each time you place a number. Although the theoretical complexity can reach O(9^(81)), pruning invalid placements dramatically reduces the search space in practice. The recursion depth is bounded by the number of empty cells, so the extra space is mainly the recursion stack, around O(81).

Approach 2: Constraint Propagation with Backtracking (Exponential Time, O(9^(n)) worst case, O(81) space)

This optimization improves the basic backtracking strategy by tracking constraints explicitly using sets or bitmasks. Maintain three structures that record which digits are already used in each row, column, and box. These can be implemented with arrays, hash tables, or bitmasks. When you place a digit, update the corresponding row, column, and box constraints instantly.

Instead of scanning the entire row or column every time, you perform constant-time checks against these constraint structures. This dramatically reduces repeated work and prunes invalid candidates earlier. Some implementations also choose the next cell with the fewest valid candidates (a common constraint propagation heuristic), which further shrinks the branching factor.

The worst‑case complexity remains exponential because Sudoku solving is fundamentally a search problem. However, constraint propagation makes the solver significantly faster in real cases by avoiding unnecessary recursion and repeated validation scans.

Recommended for interviews: Interviewers expect a clean backtracking solution that validates row, column, and box constraints correctly. Showing the baseline recursive search demonstrates understanding of the problem structure. Adding constraint tracking with sets or bitmasks shows stronger problem‑solving skills and awareness of optimization techniques commonly used in constraint satisfaction problems.