Sudoku Solver

I had this on a Square systems-onsite as the live-coding problem and the trick that made it pass under the time budget was maintaining THREE constraint sets (rows, columns, boxes) instead of recomputing legality on every recursive call. With incremental sets, each candidate check is O(1); without them, every placement scans up to 27 cells. The catalog covered valid-sudoku (the validation half) but it skipped the solver, which is the half that actually exercises backtracking.

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells. A Sudoku solution must satisfy all of the following rules:

• Each of the digits 1-9 must occur exactly once in each row.
• Each of the digits 1-9 must occur exactly once in each column.
• Each of the digits 1-9 must occur exactly once in each of the nine 3x3 sub-boxes of the grid.

The '.' character indicates empty cells. The given board has at least one valid solution. You must modify the board IN PLACE.

Examples

Example 1:

• Input:

[['5','3','.','.','7','.','.','.','.'],
 ['6','.','.','1','9','5','.','.','.'],
 ['.','9','8','.','.','.','.','6','.'],
 ['8','.','.','.','6','.','.','.','3'],
 ['4','.','.','8','.','3','.','.','1'],
 ['7','.','.','.','2','.','.','.','6'],
 ['.','6','.','.','.','.','2','8','.'],
 ['.','.','.','4','1','9','.','.','5'],
 ['.','.','.','.','8','.','.','7','9']]

• Output (board mutated to):

[['5','3','4','6','7','8','9','1','2'],
 ['6','7','2','1','9','5','3','4','8'],
 ['1','9','8','3','4','2','5','6','7'],
 ['8','5','9','7','6','1','4','2','3'],
 ['4','2','6','8','5','3','7','9','1'],
 ['7','1','3','9','2','4','8','5','6'],
 ['9','6','1','5','3','7','2','8','4'],
 ['2','8','7','4','1','9','6','3','5'],
 ['3','4','5','2','8','6','1','7','9']]

• Explanation: The unique completion of the canonical example puzzle.

Example 2:

• Input: a board with only one empty cell [r=0, c=0] = '.', all other cells filled correctly except for that.
• Output: the missing cell is filled with the unique digit that completes its row, column, and box.
• Explanation: A near-complete board has at most one valid completion per cell.

Example 3:

• Input: a board where 17 clues already fix the solution.
• Output: the unique 81-digit completion.
• Explanation: 17 is the proven minimum number of clues for a unique-solution Sudoku.

Constraints

• board.length == 9.
• board[i].length == 9.
• board[i][j] is a digit '1'-'9' or '.'.
• The board has at least one valid solution.

Follow-up

Why is this NP-hard for general n x n Sudoku but tractable in practice for the 9x9 case? The 81-cell search space with at most 9 candidates per cell has worst-case 9^81 ~ 1.97e77 configurations, but constraint propagation (the row/column/box sets) collapses this to a few thousand explored states for typical puzzles. The hard cases (like the world's hardest 17-clue boards) need additional heuristics like minimum-remaining-values or arc-consistency to stay under a second.