How the record solvers search
How the solvers that hold the records actually search. They are all, at heart, depth-first backtrackers; what separates them is the order they try things and how they bend the rules near the end.
How the solvers that hold the records actually search. They are all, at heart, depth-first backtrackers; what separates them is the order they try things and how they bend the rules near the end.
Every solver that holds a serious Eternity II record is, at heart, the same machine: a depth-first backtracker. What separates them is not the loop but three choices layered on top of it, the order they visit cells, the heuristics that decide which piece to try first, and how they bend the endgame when a perfect match runs out. This page is the neutral tour of those choices. The full, first-party engine story for each solver (decoded from the source and the literature, then built and measured) lives on its own lab page, linked from each section below.
Before the tour, the catalogue: one row per engine, and the four choices that set it apart. Every reach is measured single core on one machine, so the numbers compare like for like rather than across clusters; each row links its full write-up.
| Engine | Fill order | Pruning | Hardware regime | Measured reach |
|---|---|---|---|---|
| Blackwood's backtracker | bottom-left row scan, border pieces late | per-depth colour quota plus a depth-gated break-index budget | single core; the 470 came from many cores in parallel | 248/256 pieces unconstrained; stalls near 45 once the five clues are pinned |
| Verhaard's eii | comb-search orders | forward pruning against tuned score thresholds; a Markov-tuned slip schedule | single-core Win32 binary; no source to rebuild | 467/480, the only prize the contest paid |
| McGavin's C backtracker | per-puzzle scan-row, spiral-in, or border-first | generated code plus lookup tables and counter tricks for raw throughput | single core, ~109M placements/s on the real puzzle | past 200/256 pieces; built for speed, not a record score |
| Verhaard reimplementation | set-composition swap-annealing under the 2×2 metric | annealing acceptance, constants recovered byte-exact from the binary | single core; run committed and rerunnable | 438/480 on the real five-clue puzzle |
| CSP presets, measured | a dozen ordering presets, border-first the best | arc-consistency propagation | single core, ten corner-pinned variants | near 183 on the corner-pinned variants; below half a contender's score |
The tour below walks the three choices those rows share.
Fill the board cell by cell in some fixed order. At each cell, try every piece and rotation whose edges match what's already placed; if none fit, back up and try the previous cell differently. Correct but slow: the search tree is astronomically wide.
Here is exactly that, in slow motion: a real backtracker on a 3×3, one decision at a time. Step through it and watch a piece go down, a dead end appear, and the search un-place and try again.
The order you visit cells changes the difficulty by orders of magnitude, because some orders force conflicts to surface early (good) and others defer them until a lot of work is wasted (bad). Border-first beats row-major by a wide margin on the same puzzle. It is the single lever every record engine tunes: Verhaard's comb-search orders, Blackwood's bottom-left row scan with border pieces interspersed late, and McGavin's per-puzzle choice of scan-row, spiral-in, or border-first are all answers to the same question.
A plain backtracker tries candidates in an arbitrary order. A record engine scores them, so the pieces most likely to matter go down first, and prunes any branch that falls behind a schedule. Blackwood's solver, for instance, privileges three colours and enforces a per-depth quota that must be met to keep descending; Verhaard prunes forward against hand-tuned score thresholds. The details differ, but the shape is shared: commit the constrained pieces early, cut the branches that cannot pay their way.
A perfect 256-piece tiling has never been found. Every record board instead tolerates a handful of late mismatches, and the engines reach them by scheduling imperfection: a per-depth budget of mismatched edges that unlocks deep in the search. Verhaard called his a slip array; Blackwood calls his the break indexes. Same idea, gated by depth so the early board stays clean and the mismatches are spent only where they buy the most.
The lab below lets you move that budget around and watch the reachable score change:
One fixed 8×8 puzzle, the real solver running in your browser. A break — a single allowed mismatch — is permitted only in the bottom rows you license below, mirroring how the record solvers confine breaks to a few fixed positions. With none, the strict search stalls below a full board. License a row or two and it completes, near-perfect.
Try one row first: where the breaks are licensed matters as much as how many. Scatter the same number across the top and the board won't finish — the conflicts this scan order accumulates land at the bottom.
Each record engine has a dedicated page that decodes how it works and then builds and measures it on one machine, single core:
The playground runs a real depth-first solver in your browser. Watch it search live, or draw your own fill order and race it against the classics to feel how much the order matters.
For approaches that don't work, see the dead ends.