Sudoku Solver - Solution & Explanation

Problem Overview: You are given a partially filled 9x9 Sudoku board. Empty cells are marked with '.'. Fill the board so each row, column, and 3x3 subgrid contains digits 1 through 9 exactly once. The solution must modify the board in-place.

Approach 1: Backtracking (Exponential Time, O(9^k) time, O(81) space)

This problem is a classic use case for backtracking. Iterate through the grid to find the next empty cell. For that position, try digits 1-9. For each candidate, check whether the digit already exists in the same row, column, or 3x3 box. If the placement is valid, write the digit and recursively attempt to solve the remaining board. If the recursive call fails, undo the placement and try the next digit.

The key insight is that invalid partial boards can be detected early, which prunes large parts of the search tree. Validity checks scan the row, column, and subgrid using simple loops over the array or matrix. In the worst case, each empty cell tries 9 digits, giving roughly O(9^k) time where k is the number of blanks. Space complexity is O(81) due to recursion depth and the board itself.

Approach 2: Constraint Propagation + Backtracking (O(9^k) worst-case, O(81) space)

A more optimized approach maintains fast lookup structures to track used digits. Instead of scanning rows and columns repeatedly, store three sets (or boolean arrays): rows[9], cols[9], and boxes[9]. Each structure records which digits are already used. This effectively turns validity checks into constant-time lookups using a hash table or fixed-size arrays.

When placing a digit, update the corresponding row, column, and box structures. During backtracking, remove the digit from those structures. This reduces repeated scanning of the grid and significantly lowers constant factors. Some implementations also choose the next cell with the fewest candidate digits, further reducing branching.

The theoretical complexity remains exponential because Sudoku solving is a constraint satisfaction problem. However, constraint propagation dramatically speeds up real-world cases by pruning invalid choices earlier and performing O(1) constraint checks.

Recommended for interviews: Interviewers expect a clean backtracking solution. Start with the basic recursive search to demonstrate understanding of constraint validation. Strong candidates optimize it using row/column/box tracking to avoid repeated scans. The optimized version shows practical mastery of backtracking combined with efficient data structures.