# The DFS study > 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. - Canonical page (with interactive figures/demos): https://eternity2.dev/research/lab/experiments/raphael-anjou/dfs-study/ - Updated: 2026-07-16 - Topics: backtracking, search-space, speed - Reproduce: `just experiments dfs-study` - Source: Runnable engine + committed results + scripts (this study's backing directory) — https://github.com/raphael-anjou/eternity2/tree/main/research/experiments/dfs-study --- 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 edge *break*. 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. > **[Interactive: StartingPuzzleCarousel]** Rendered on the canonical page (link above); not shown in this markdown export. ## The family, and the leaderboard 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. > **[Interactive: DfsStudyLeaderboard]** Rendered on the canonical page (link above); not shown in this markdown export. ## What the study found - **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](/research/lab/experiments/raphael-anjou/dfs-study/method), and the path, heuristic and break comparisons are worked through on the [findings page](/research/lab/experiments/raphael-anjou/dfs-study/findings). ## How to read the numbers 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](/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](https://github.com/raphael-anjou/eternity2/tree/main/research/experiments/dfs-study), and `just experiments dfs-study` rebuilds the engine and reruns the whole grid. ## Pages in this section - [How the study is built](https://eternity2.dev/research/lab/experiments/raphael-anjou/dfs-study/method) — The engine behind the DFS study: one composable backtracker where a variant is a declared change over a parent, a shared IO layer every algorithm speaks, and the definitions of every statistic the study raises: node rate, depth, breaks. - [What each idea buys](https://eternity2.dev/research/lab/experiments/raphael-anjou/dfs-study/findings) — The three comparisons at the heart of the DFS study, worked through: fill order (row-major wins, a bad order is catastrophic), heuristics (MRV rescues border-first but costs throughput; more propagation did not help), and breaks (they smash the depth wall; the break schedule is the lever, not the per-cell cap). ## Related - [Raphaël Anjou's experiments](https://eternity2.dev/research/lab/experiments/raphael-anjou) — A notebook of Eternity II search experiments, organised into the shared engines they run on, the combination pipelines that chase the score, three studies that take one search paradigm apart a decision at a time, and exact endgame solves. Each has its idea, its best board, and the questions it left open. The best reaches 463 of 480. - [Single-core benchmark](https://eternity2.dev/research/lab/experiments/single-core-benchmark) — Fifteen solvers, ours and our implementations of the community's two record backtrackers, each run once on ten corner-pinned variants of the official puzzle, single core, 60 seconds per run. The finding: node count is not score. - [Fill orders](https://eternity2.dev/research/build/backtracking/fill-order) — The order in which a backtracker visits the 256 cells is its one free choice: it costs nothing at runtime and moves the size of the search tree by orders of magnitude. Twenty years of community science, from the fixed-vs-dynamic wars and the strategy races to the magic 10×16 square and Verhaard's comb search, all answer the same question: which path through the board is cheapest?