# Backtracking

> Depth-first search done seriously. The order a solver visits the cells is its one free choice and moves the tree size by orders of magnitude; restarts turn a heavy-tailed runtime into a portfolio. This is the family behind every record backtracker.

- Canonical page (with interactive figures/demos): https://eternity2.dev/research/build/backtracking/
- Updated: 2026-07-13

---
Depth-first search done seriously. The order a solver visits the cells is its one free choice and moves the tree size by orders of magnitude; restarts turn a heavy-tailed runtime into a portfolio. This is the family behind every record backtracker.

The pages below go technique by technique: what each is in a line, what it
actually reached on the real 16×16 board, where it stops, and the labs and
measurements to back it. For the whole territory at once, start with
[a map of every known approach](/research/build/approaches-map).

## Pages in this section

- [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?
- [Restarts and heavy tails](https://eternity2.dev/research/build/backtracking/restarts) — Run the same backtracker on the same puzzle twice and the runtimes differ by powers of ten. The community measured this in 2007; the CSP literature had already named it. The cure (cut off, reshuffle, restart) is why every record solver since has been a restart portfolio.

## Related

- [A map of every known approach](https://eternity2.dev/research/build/approaches-map) — The survey the community keeps asking for and never finds: every family of attack tried on Eternity II, what each one actually reached, where it walls out, and a link to the deep page. One organising insight runs through all of them.
- [The techniques](https://eternity2.dev/research/build/techniques) — The technique shelf: the algorithms and pruning ideas that recur in every serious Eternity II solver, each with what it is, what it costs, and what it actually bought when measured on this puzzle.