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.
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.