Don't memorize the Sudoku solver — watch it guess, hit a wall and erase. Scan for the first empty cell, try each digit that is legal in its row, column and box, place it and recurse. When a cell has no legal digit, that is the signal: an earlier choice was wrong, so backtrack — undo the last placement and try the next. Same push-recurse-pop skeleton as subsets and combination sum, now steered by constraints.
first empty cell · legal in row + col + box · place & recurse · no digit → backtrack
CELL SCAN
Find the first empty cell in row-major order — the next decision to make.
CANDIDATES
Try digits 1..k in order; keep only ones legal for this cell.
CONSTRAINTS
A digit is legal only if unused in its row, its column and its 2×2 box.
BACKTRACK
No legal digit here? Erase the last placement and try the next candidate there.
sudoku.sim — 4×4 board, digits 1–4, four 2×2 boxes
Ready
Two clues are locked (grey). Press Step: the solver scans for the first empty cell, tries the lowest legal digit, and recurses — until a cell has no legal digit, where it must erase and back up.
legal(d) = d not in row ∧ not in col ∧ not in box
2
Cells filled
0
Backtracks
Constraints turn guessing into search
Subsets branched freely; combination sum added a bound; Sudoku adds a full set of constraints, and that is what makes it a genuine constraint-satisfaction problem. The solver is still the same depth-first walk — pick the next undecided thing, try a value, recurse, undo on failure — but now every value must pass three tests at once: it cannot repeat in the cell's row, its column, or its 2×2 box. Those tests are the pruning. Most digits are rejected instantly, so the branching factor collapses far below the naive four-choices-per-cell. The dramatic moments are the backtracks: the solver commits to a digit, fills several more cells on top of it, then discovers a cell with nothing legal left — proof that the earlier commitment was wrong. It rewinds, erasing as it goes, and tries the next option.
01
Scan for an empty cell
Row-major search for the first blank. If none remain, the board is solved.
02
Filter by constraints
For digits 1..k, keep only those absent from the cell's row, column and box.
03
Place and recurse
Write the first legal digit and recurse to the next empty cell.
04
Backtrack on a dead end
If a cell has no legal digit, return and erase the previous placement; try its next candidate.
Board
4×4 demo
Time
O(k^m)
Space
O(1)
Pattern
CSP + BT
A real 9×9 board works identically: digits 1–9, nine 3×3 boxes, the same scan-try-recurse-erase loop. The worst case is exponential — O(k^m) for m empty cells — but constraints keep the real search tiny, and heuristics shrink it further: fill the most-constrained cell first (minimum remaining values), propagate forced digits before guessing, and store each row, column and box as a bitmask so legality is one bitwise test. The backtracking core, though, is exactly what you just watched.
Check yourself
1 · What triggers a backtrack?
If every digit conflicts with the row, column or box, the cell is unsolvable given the current choices — so the solver erases the previous placement and tries again.
2 · A digit is legal in a cell only if it is unused in the cell's…
All three constraints must hold simultaneously: no repeat in the row, the column, or the box that contains the cell.
3 · Why is Sudoku called a constraint-satisfaction problem?
A solution is an assignment to every cell that violates no row, column or box constraint — backtracking searches assignments and rejects illegal ones early.
Questions
Why show a 4×4 board instead of 9×9?
The algorithm is identical; a 4×4 grid (digits 1–4, 2×2 boxes) is simply legible when animated. On 9×9 you swap in digits 1–9 and 3×3 boxes and run the exact same scan-try-recurse-erase loop.
How do real solvers get so fast?
Three tricks: the minimum-remaining-values heuristic fills the most-constrained cell first; constraint propagation fills forced cells before any guessing; and bitmasks for each row, column and box make the legality check a single bitwise AND. The exponential worst case rarely shows up on real puzzles.
Is this the same as N-Queens?
Yes, structurally. Both are constraint backtracking: place, check constraints, recurse, undo on failure. N-Queens constrains by attacked squares; Sudoku by row, column and box. Change the constraint check and the same engine solves a different puzzle.
The same engine, one more constraint.
Scan, try a legal digit, recurse, and erase on a dead end. Choices became bounds became constraints — that is the whole backtracking arc.