Sudoku solver

The problem it solves

Fill a grid so that every row, column and box contains each symbol exactly once, honouring the given clues. Sudoku is the friendly face of constraint satisfaction — the same problem family as exam timetabling, register allocation, and configuration solving — and the backtracking solver here is the family’s fundamental algorithm: guess, check, and un-guess, applied until either the board fills or every possibility is exhausted.

The board drawn is 4×4 (values 1–4, 2×2 boxes) rather than 9×9, deliberately: the algorithm is identical, but a 4×4 trace is short enough that you can watch every single guess and every single erasure — and the erasures are the entire lesson. A solved sudoku printed in a book shows only the surviving guesses; the algorithm’s actual life is dominated by the dead ones. The hard preset makes forty-nine wrong guesses before the answer; the player’s backtrack counter keeps the score that final answers hide.

The intuition — and where it breaks down

Solve like a cautious human with an eraser. Find an empty cell. Try the smallest value that doesn’t clash with its row, column, or box — write it in pencil. Move to the next empty cell and repeat. When some cell admits no value at all, the current pencil marks contain a lie: erase the most recent guess, try its next value, and if a cell’s values are exhausted, erase the one before that, and so on. Guesses cascade forward; contradictions cascade backward; the clues in ink are never touched.

The intellectual center is what a contradiction means, and the player’s third question asks it directly. A stuck cell does not mean the puzzle is unsolvable — it means some earlier guess is wrong, nothing more. The false return travels up exactly one level, where the caller erases its own guess and advances to its next candidate. Only when contradictions propagate all the way to the root — every value of the very first cell leading, eventually, to a stuck board — is the puzzle itself impossible. Backtracking is deduction by exhaustion, and the erasure discipline (undo exactly your own guess, in reverse order) is what keeps the exhaustion honest.

Where the intuition breaks down: humans don’t guess first — they deduce first, filling cells that have only one possible value, and guess only when deduction stalls. This solver guesses immediately, by design, so the raw search is what you watch; the deduce-then-guess refinement (constraint propagation) is real, powerful, and discussed under implementation notes as the thing production solvers add around this exact skeleton.

Loading…

A walkthrough you can check

On the default board, watch three characteristic moments rather than every step.

1. The first guess: the solver attacks the first empty cell in reading order (the opening pick-question), tries 1, 2, … and writes the first that fits. No intelligence in the choice of cell — the try-fail-undo loop is the whole machine.
2. A candidate count: mid-run, the number-question asks how many of 1–4 fit some cell. Answering means running the three constraint checks in your head — row, column, 2×2 box — which is the fits function performed manually. Cells with fewer candidates branch less; hold that thought for the MRV discussion.
3. A cascade: find a moment where the backtrack counter ticks several times in quick succession — a guess made two levels ago has doomed everything beneath it, and the erasures walk backwards to the culprit. This is the algorithm’s signature motion, invisible in any solved-board presentation.

The nearly preset shows the opposite regime — mostly forced moves, barely any branching — and the contrast between presets is the complexity story: identical algorithm, wildly different work, decided entirely by the input’s constrainedness.

The invariant

The filled cells are always mutually consistent — no duplicate in any row, column or box — and the guesses on the board are exactly the current root-to-node path of the search tree. Consistency is enforced at write time (fits gates every placement), so contradictions manifest only as no candidate fits, never as an illegal board. The path property is maintained by the erasure discipline: each frame erases precisely its own guess before trying the next value or returning, so the board never carries guesses from abandoned branches — and the clues, marked locked in the drawing, are never written at all.

Termination is the quiet corollary: each cell has at most four candidates and the recursion depth is bounded by the empty-cell count, so the tree is finite; the solver either finds a leaf with no empty cells (a solution, by the consistency invariant) or exhausts the root’s candidates (a proof of unsolvability).

Complexity, derived

Worst case: exponential in the number of empty cells — up to 4^16-ish nodes on an empty 4×4 board, 9^81-flavoured horrors on real sudoku, and no polynomial algorithm is known (generalised n×n sudoku is NP-complete; worth saying with the caveat that 9×9 sudoku is a fixed finite problem and the claim is about the family). Space is refreshingly small: O(cells) for the board and recursion stack — the board mutation-and-undo pattern means no copies.

The honest performance story is variance: the same algorithm runs near-linearly on heavily-clued boards (every cell nearly forced) and exponentially on sparse ones. Real speedups come from reducing branching, not faster code: attacking the most-constrained cell first (fewest candidates — MRV) collapses the tree because 1-candidate cells are free progress; propagating constraints between guesses (naked/hidden singles) fills forced cells without search at all. Both slot into this skeleton without changing its shape — the fits check and the erasure discipline survive every refinement.

What people get wrong

• Erasing clues while backtracking: guesses and givens must be distinguishable (here, the locked marks). One overwritten clue and the solver “solves” a different puzzle.
• Validating only at the end: placing values unchecked and testing the full board at the leaves is correct and astronomically slower — pruning at each placement is what makes search feasible.
• Copying the board per guess: mutate-and-undo is O(1) per node; copy-per-node multiplies everything by board size and drowns the machine in garbage.
• Misreading a contradiction as “unsolvable” and aborting — it indicts one guess, not the puzzle.
• Declaring victory at the first solution when uniqueness matters: puzzle setters need to know there is exactly one solution; keep searching after the first find and count.

Implementation notes

The skeleton is thirteen lines and worth keeping pristine: find an empty cell (row-major here), loop candidates, fits check, place, recurse, erase on failure, return false when candidates exhaust. Everything else is bolt-ons: MRV ordering replaces firstEmpty with argmin-candidates and is the single highest-value change (the candidates-question exists to seed that realisation); forward checking maintains per-cell candidate sets incrementally and fails early when any empty cell’s set goes empty; naked singles propagation fills forced cells between guesses in a loop until quiescence.

The far end of this road has a name: Knuth’s Algorithm X with dancing links, which models sudoku as exact cover and backtracks over a sparse 0/1 matrix with spectacular constant factors — the standard answer to “how do the fast solvers work?”, and still, structurally, guess-check-undo. Mentioning it by name, plus the sentence “same skeleton, better data structure”, is the right depth for an interview.

Two testing notes from this site’s own suite: validate solutions by checking (rows, columns, boxes, clue consistency) rather than comparing against a reference solver’s output — sparse boards can have multiple valid solutions and two correct solvers may legitimately disagree; and assert that backtracking actually occurred on presets that advertise it, or a “hard” board that solves greedily will quietly falsify your documentation.

The follow-up questions

What single change speeds this up most? Most-constrained-cell-first (MRV). A one-candidate cell is free progress; a four-candidate cell is a 4-way branch — ordering by constraint prunes the tree at its root.

What does a contradiction prove, exactly? That some guess on the current path is wrong. It unwinds one level at a time; only exhaustion at the root proves the puzzle unsolvable.

Why mutate-and-undo instead of copying the board? O(1) per node versus O(cells), and the undo discipline is the same three lines regardless of board size. Copying is the classic accidental 100× slowdown.

How do production solvers differ? Constraint propagation between guesses, MRV ordering, and — at the limit — dancing-links exact cover. All of them are this skeleton with sharper senses; none of them abandon guess-check-undo.