One question, asked carefully: among depth-first backtrackers for Eternity II, what does each fill order, each heuristic, and the break mechanism actually buy? A family of from-scratch backtrackers, each one change apart, run on the same ten corner-pinned variants, single core, sixty seconds.
Every record-holding Eternity II solver (Blackwood, Verhaard, McGavin) is a
depth-first backtracker. What separates them from a first-week homework
backtracker is not their kind but a handful of decisions: which order they fill
cells in, which look-ahead they run, and whether they let an edgebreak. This
study takes those decisions apart. It builds a family of depth-first backtrackers
from scratch, each one exactly one change away from a sibling, and runs them all
on the same ten corner-pinned variants of the official puzzle, single core, sixty
seconds a run. The maximum score is 480 matched edges.
The point is not to win. The strongest variant here averages the low 430s, well
short of the community's 464 on these five clues, because sixty seconds on one
core is a small fraction of the compute the records took. The point is to isolate
what each idea is worth by changing one thing at a time and measuring the result
with the same canonical scorer for every board.
The ten starting puzzles
Every engine runs on these ten instances: the official 256-piece puzzle with eight cells pinned (the five official clues and three corners), arranged differently each time. Only the pinned cells are shown; the rest is what the search must fill.
Four families, laid out so that neighbours differ by a single decision.
Baseline is the rawest possible backtracker, alongside a hand-specialised twin
that prices the low-level engineering. Path order fixes everything but the
sequence in which cells are filled. Heuristic fixes the order and adds one
propagator at a time. Break is the elite axis: the depth-gated edge-break
mechanism the records rely on. The community record engines, McGavin's C and
Blackwood's C#, are themselves break backtrackers, so they sit in the break
family too, not in a category of their own. Whose code an engine is stays a
matter of labelling, not colour. Both appear on the leaderboard at their
corner-pinned score, badged where they collapse, and again on a fair unpinned
grid further down where they run as designed.
The leaderboard — mean score by variant
Mean matched-edge score over ten corner-pinned variants of the official puzzle, single core, 60 s per run. Colour marks the family; the family is named on every bar, so colour is never the only signal. McGavin's C and Blackwood's C# appear here too, at the score their fixed scan path reaches before a corner pin dead-ends it, badged where they stall; the two-grid section below shows them running properly once the pins are gone.
Drawing…
baselinepath orderheuristicbreaks
How far each search reached, and how fast
The deepest placement each variant reached, out of 256. Strict backtrackers top out in the low 200s (the fastest, NAIVE-CODEGEN, reaches 216); the break family reaches materially deeper, 243 to 245, because it can push past a locally unmatchable edge instead of backtracking out of it. The table below adds median throughput, in search-nodes per second, which is never compared across families because a propagating node is not a naive node.
Drawing…
baselinepath orderheuristicbreaks
variant
family
max depth reached (of 256)
median throughput
BREAK-1
breaks
245
4.6M
BREAK-2
breaks
245
5.2M
VERHAARD-SLIP
breaks
243
2.3M
NAIVE-CLEAN
baseline
208
32.4M
ROWMAJOR
path order
208
31.5M
NAIVE-CODEGEN
baseline
216
44.9M
VERHAARD-COMB
path order
197
23.3M
BLACKWOOD-COMB-BREAK
breaks
197
17.9M
BORDER-MRV
heuristic
194
6K
MRV-RARE
heuristic
194
7K
MRV-FC
heuristic
193
7K
MRV-AC3
heuristic
192
8K
MRV-GACOLOR
heuristic
192
8K
ROWMAJOR-BOTTOMUP
path order
201
273K
SPIRAL-IN
path order
79
13.3M
BLACKWOOD-CS
breaks
47
—
BORDER-FIRST
path order
77
365K
SPIRAL-OUT
path order
31
20.1M
MCGAVIN-C
breaks
21
—
What stacks on what
Every variant is a depth-first backtracker declared as one change over its parent. This table is generated from the engine registry, so it always matches the code that ran.
variant
family
the one change it adds over its parent
breaks
mean
depth
NAIVE-CLEAN
baseline
the rawest depth-first backtracker: row-major, no heuristics, no breaks
strict
376.8
208
NAIVE-CODEGEN
baseline
same algorithm, a 16×16-specialised unrolled hot loop
strict
372.1
216
ROWMAJOR
path order
the row-major control (same as NAIVE-CLEAN, named for the path study)
strict
376.6
208
ROWMAJOR-BOTTOMUP
path order
fill bottom-to-top instead of top-to-bottom (Blackwood's scan direction)
strict
225.9
201
SPIRAL-IN
path order
fill the outer ring inward instead of row-major (the cloister spiral)
strict
80.2
79
SPIRAL-OUT
path order
spiral from the centre outward instead of inward
strict
24.5
31
BORDER-FIRST
path order
fill the whole border ring first, then the interior
strict
66.6
77
VERHAARD-COMB
path order
a horizontal band then vertical teeth (Verhaard's COMB order)
strict
357
197
BORDER-MRV
heuristic
choose the most-constrained empty cell dynamically (MRV) instead of a fixed order
strict
324.1
194
MRV-RARE
heuristic
try pieces carrying globally-rare colours first (Selby/Riordan rarity)
strict
323.7
194
MRV-FC
heuristic
add forward-checking: reject a placement that empties any neighbour's domain
strict
322.2
193
MRV-AC3
heuristic
extend the look-ahead to arc-consistency (AC-3) over the frontier
strict
320.6
192
MRV-GACOLOR
heuristic
add Régin per-colour all-different reasoning on the remaining supply
strict
320.6
192
BREAK-1
breaks
allow ≤1 broken edge per cell on a depth schedule (Blackwood's ladder)
break (≤1/cell)
431.3
245
BREAK-2
breaks
allow up to 2 broken edges at one cell (double-breaks the community 460s use)
break (≤2/cell)
428.5
245
VERHAARD-SLIP
breaks
Verhaard's interior edge-slip schedule instead of Blackwood's ladder
break (≤1/cell)
399.3
243
BLACKWOOD-COMB-BREAK
breaks
run the Blackwood break ladder on Verhaard's COMB fill order
break (≤1/cell)
356.4
197
MCGAVIN-C
breaks
the community's fastest DFS, run here; it collapses on our corner pins
break (≤1/cell)
13
21
BLACKWOOD-CS
breaks
Blackwood's C# record engine, run here; it stalls on our pins
break (≤1/cell)
75
47
The community's record engines, run here
McGavin's C and Blackwood's C# both build and run on the same machine. Neither can take the corner-pinned grid above: each is built around one clue configuration, so an arbitrary corner pin its scan never reaches early dead-ends it at once. The two panels below show both sides of that. First, the pins the study uses collapse them. Second, on a fair grid with only the one mandatory centre clue, they run as designed.
Same budget, same core: 60 s from scratch
The same engines on the official pieces with only the mandatory centre clue pinned, so nothing dead-ends on an arbitrary corner. Every score is canonically rescored from the engine's own board, single core, 60 seconds, cold start. This is a controlled-budget comparison, identical conditions for all four, not a contest of best strength: it shows how far each gets in one core-minute, not each engine's ceiling. That one pinned clue still bites: Blackwood scores 214 here, well below the 454 it reaches on its solver page, where its search places every piece freely instead of committing the centre clue up front (a legal board still, since only the centre clue binds, but an easier search). The faint marker on the two foreign engines is their best documented score, which needs long multi-core runs a 60-second budget cannot reach. What the grid does show is that all four run properly once the pins that break a fixed scan path are gone, which the pinned grid denied the two foreign engines.
Drawing…
The dashed line on each foreign engine marks its best documented score (Blackwood ~470, McGavin 469): the official puzzle has never been solved, so no engine has a genuine 480. These records need long multi-core runs a 60-second single-core budget cannot reach; Blackwood's own longer run on this same machine already rescored to 454. Throughput is labelled per engine (McGavin counts tiles, the others search-nodes) and is never compared across engines, because the units are not the same work. McGavin is built with its author's own ARM flags (native tuning and link-time optimisation).
engine
mean
depth reached
throughput
McGavin (C)
392
211
85M tiles/s
break-2 (ours)
344
192
33M search-nodes/s
Verhaard (our reimpl)
286
172
8k search-nodes/s
Blackwood (C#)
214
119
9M search-nodes/s
Pinned: the collapse, as a score
The same two foreign engines on the study's pinned configuration. The bar is the canonical score their board reaches before the fixed scan path strands them; the faint bar behind is what the same engine reaches unpinned. The gap is the collapse.
MCGAVIN-C(C)corner-pinned 13 · centre clue only 392
depth 21
BLACKWOOD-CS(C#)corner-pinned 75 · centre clue only 214
depth 47
The corner-pin collapse. Adding the study's three corner pins collapses its fixed scan path to depth 21 (canonical score 13), confirmed on 2 pinned variants: the scan never reaches a corner early, so a pinned corner dead-ends it at once.
The corner-pin collapse. It hardcodes its piece set and scan, so it cannot express the study's arbitrary corner pins; the matching constrained test is the five official clues, where its heuristic phase thrashes to depth 47 (canonical score 75) in 60 s.
Path order is the largest free lever, and the wrong order is catastrophic.
Plain row-major averages 377; a strict border-first or spiral fill, with no
heuristic to rescue it, stalls near 67. Same engine, same budget, a swing of
more than 300 points from the fill order alone.
The most-constrained-cell heuristic (MRV) is what makes border-first viable.
It lifts a stalled border-first from the sixties to a mean of 324, at a cost of
three orders of magnitude in node throughput. Node rate and score are different
axes, a distinction the study returns to throughout.
More propagation did not buy more score at this budget. Forward-checking,
arc-consistency and per-colour reasoning land within a point of each other (322,
321, 321), a gap far inside the run-to-run spread, so heavier look-ahead neither
helped nor clearly hurt. It spends the sixty seconds proving small regions
rather than reaching deeper.
Breaks reach deeper than any strict search. Strict backtrackers top out in
the low 200s (the fastest, NAIVE-CODEGEN, at 216); a depth-gated break budget
reaches past 245 and averages the low 430s, because it can push past a locally
unmatchable edge instead of backtracking out of it. The decisive factor is the
break schedule: unlocking breaks too early (Verhaard's ladder, mean 399)
scores well below the later Blackwood ladder (mean 431). Raising the per-cell
cap from one to two did not help at this budget, a null result reported as
measured.
Each of these has its own page: how the engine is built and what every raised
statistic means is on the method page,
and the path, heuristic and break comparisons are worked through on the
findings page.
Every board is re-scored by one canonical scorer, and no engine's self-reported
score is trusted. Throughput is reported in search-nodes per second and is
never compared across families, because a node that runs full arc-consistency
is not the same unit of work as a naive placement. Depth is the deepest placement
a variant reached, out of 256.
The break count deserves a precise definition, because it is easy to state
loosely. A board's score is its matched interior edges, and the gap
480 − score is the board's total unmatched-edge deficit. On a completed
board every unmatched edge is a genuine break, so there the score is exactly
480 − #breaks. Sixty seconds is rarely enough to fill the board, however, so
most break-variant boards here are partial, and their deficit is dominated by
edges that are simply still empty rather than broken. This study therefore reports
the true break count, meaning the interior mismatches the search actually
committed under its budget, tracked by the search itself rather than inferred from
the score. That number stays small even when the deficit is large. Every board
carries a bucas .url that opens in the viewer, so both the score and
the broken edges can be checked directly.
The whole apparatus (the engine workspace, the ten variants, the committed
per-run results and the grid scripts) lives under the study's
backing directory,
and just experiments dfs-study rebuilds the engine and reruns the whole grid.