Fill every empty cell of a Sudoku grid with a digit 1-9 so each row, column, and 3×3 box contains every digit exactly once. The puzzle is a textbook constraint satisfaction problem, and backtracking solves it by the simplest possible policy: fill the next empty cell with a legal guess, and if that guess dead-ends, erase it and try another.
How It Works
- Find the first empty cell.
- Try each candidate value
1-9. - Validate the candidate against the cell’s row, column, and 3×3 box.
- Place a valid value and recurse to the next empty cell.
- Backtrack — clear the cell and try the next candidate when no value completes the puzzle.
The validity check is a constraint test: it guarantees the partial grid stays legal after every placement, so a fully filled board is automatically correct — no final verification pass needed.
Key Insight
This is “chronological backtracking”: each placement is a guess that later placements must honor. On failure, the solver unwinds to the most recent decision and changes it, climbing back up the recursion stack. Because constraints are checked incrementally, hopeless partial grids are abandoned as soon as the first illegal cell appears — that pruning is what turns an astronomically large search into seconds.
Worked Example
The visualizer solves a classic Wikipedia puzzle. The solver fills cells in a fixed left-to-right, top-to-bottom order:
- The first empty cell is
(0,2), which can legally hold a small set of candidates — watch it try each until one survives. - Near the top rows, candidates usually succeed quickly; the backtracking becomes visible in the middle rows, where an early guess leads to a row/box conflict and the solver steps back, clears cells, and retries.
- The final frame shows the completed grid with every row, column, and box containing
1-9.
The key moment to watch: after an invalid guess, the solver doesn’t restart — it undoes just one placement at a time and continues from the nearest decision point.
Edge Cases & Pitfalls
- Duplicate clues: the puzzle must be consistent; the solver will still report failure if no fill satisfies all clues.
- Guaranteed uniqueness: a well-posed puzzle has exactly one solution — but a plain backtracker will happily stop at the first one.
- Order matters for speed: filling in naive row-major order is much slower than filling the cell with the fewest candidates first (MRV).
- Row/col/box indexing: the box check uses
(r//3)*3 + (c//3)— off-by-one here silently corrupts the grid.
Optimizations
| Heuristic | Idea | Effect |
|---|---|---|
| Minimum Remaining Values (MRV) | Fill the cell with the fewest candidates | Prunes far earlier |
| Constraint propagation | Apply naked/hidden singles before searching | Often solves easy puzzles with zero guesses |
| Dancing Links | Exact-cover formulation | Near-instant on hard puzzles |
Applications
- Constraint satisfaction — scheduling, timetabling, and resource allocation share this search shape
- Logical deduction engines — infer-and-check reasoning
- Crypto/encoding puzzles — any “fill slots obeying rules” problem
Practice Trajectory
- Watch the visualizer: identify the first dead-end branch and count how many cells it unwinds.
- Verify a single placement by hand using the row/column/box check.
- Add MRV (pick the empty cell with the fewest candidates) and compare step counts.
- Detect a puzzle with no solution and confirm the solver reports failure rather than looping.
- Explain why a fully-filled board needs no final correctness pass.