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?
A backtracker has almost no freedom. The pieces are given, the matching rule
is given, the board is given. The one thing entirely up to you is the fill
order: the sequence in which the 256 cells get filled. It looks like a
detail (the search is exhaustive either way), and it is instead the
highest-leverage decision in the whole solver. Brendan Owen said it plainly
in 2007: "One of the biggest node count savings you can have is choosing a
good search order"
(msg 2714). The same puzzle,
walked in a different order, can cost ten orders of magnitude more nodes.
And the choice is free, decided before the first piece is placed.
That is why the mailing list argued about it for twenty years. The first
great debate, in the summer of 2007, was fixed versus dynamic: veterans of
Eternity I argued for dynamically picking the most-constrained cell at every
step, the classic CSP heuristic
(msg 2392). The empiricists
answered with node counts: the best results came from fixed, precomputed
paths, and Owen's verdict was that "a scan-line search after the hint piece
is placed seems the best"
(msg 2425). A year later,
asked why nobody bothered with fully dynamic placement, istarinz compressed
the engineering half of the answer into one word, speed: a fixed path keeps
the inner loop branch-free and table-driven
(msg 5860). The theory half
took longer, and is the subject of this page.
One idea underneath everything: a piece placement is only ever tested
against the neighbours already on the board. A 16×16 grid has exactly 480
internal joins, and every complete fill order (row scan, spiral, anything)
ends up checking all 480 of them. The order changes only the schedule:
which joins are paid early, while the tree is still narrow, and which are
deferred to where it is wide. A cell that arrives with two placed neighbours
admits few candidate pieces; a cell that arrives with none admits nearly all
of them and prunes nothing. Good orders are the ones that feed the search a
steady diet of constrained cells, which is exactly what a row scan does:
after the first row, almost every new cell touches a piece on its left and a
piece below.
Owen turned this into a method. For a fixed order, the nodes at depth D
are (in expectation) the number of ways to tile the shape the order has
built at depth D. Any candidate order can therefore be scored, shape by
shape, without running it. His conclusion from doing this exhaustively: the shapes
that dominate the total are those of sizes 121–185, and the best shapes in
that critical window "form a simple row scan order"
(msg 2714). The full
machinery, join probabilities and all, became
complex theory; this page is what its
answers look like in practice.
The project lab notebook puts numbers on the diet itself. Write k for the
number of already-placed neighbour sides a cell has when the search reaches
it. A mean-field law says the cell should admit about 4Rpk candidate
placements, where R is the count of pieces still in hand and
p≈0.048 is E2's average probability that one side matches one
colour. At the start of interior fill that predicts roughly 38 candidates
for a k=1 cell, 1.8 for k=2, 0.09 for k=3 and 0.004 for k=4. Exact
enumeration against the real 256-piece set (40 seeded trials per
configuration) lands within 20 to 40% of those predictions and confirms the
three regimes behind them: k=1 cells are essentially always fillable;
k=2 cells cross 50% dead somewhere around 50 to 62% board fill; and cells
with three or more placed neighbours are dead in 87 to 100% of trials at
every fill level, including the very first interior placement. (The law is
a mean-field idealization validated for Eternity II's colour statistics,
one instance; it is not a claim about edge matching in general.)
Read as a design rule: a good order is one whose frontier presents every
new cell with exactly two placed neighbours, enough to prune, few enough to
survive. Row scan does that by construction, a constant k=2 after the
first row; any order whose frontier develops concave, three-sided pockets
pays near-certain dead cells no matter how full the board is. The same
regimes also measure what backtracking itself buys. With no backtracking at
all, a greedy random fill stalls within the first 5 to 12% of the board
whichever sweep it uses: over 8 seeds per order, the median stall came at
step 15 for row-major, 13 for a diagonal sweep and 15 for a spiral (the
diagonal ranged from 4 to 32), and none of the 24 runs got further. Every sweep manufactures a
fatal concave corner within a handful of placements; that number is an
illustration of the geometry, not a solver benchmark.
The lab below makes the schedule visible. It animates the visit sequence of
four preset orders over a 16×16 grid and plots, live, the constraint count
(how many already-placed neighbours each new cell has) together with the
running total of joins collected. (It shows the geometry; to race real
solves along paths you draw yourself, the hands-on companion is the
search-path playground.)
The strategy races. By late 2007 the question had become quantitative:
shared benchmark puzzles, full-search node counts, and a public scoreboard.
The style peak was doc_s_smith's fully automatic strategy-finding algorithm,
which designed a search order that exhausted the size-14 hints15_2
benchmark in 89,794 nodes, beating Txibilis's hand-tuned 141,628: machine
over human (msg 2896).
Txibilis struck back within two days with 85,729
(msg 2928); doc_s_smith had
already been musing about why humans are so strong in this discipline
(msg 2883). The lesson that
survived the race: order quality is measurable, and the differences are
never small.
Dynamic versus fixed, measured. The fixed-versus-dynamic argument from
2007 got a small controlled test in September 2008. Markus Zajc ran three
orders on the hint-free 8×8, each over ten randomized tile orders to cancel
input-order effects, all under a constraint resolver: plain scanline, a
minimum-remaining-value order that always takes the cell with the fewest
candidates, and a maximum-reduction order that takes the cell whose placement
prunes the most. Minimum-remaining-value won; scanline came second but swung
with the input order (its best run was still ~2× the winner); maximum-reduction
came last, because seeding the open interior early buys a big first cut but
then a punishing branch factor on every backtrack
(msg 5918; the per-order domain
dumps are in his files-area folder). It is a small board, but it is the cleanest
head-to-head of the classic CSP heuristic against a fixed scan, and it lands
where the community's later node counts do: the value is in feeding the search
constrained cells, whether a dynamic rule or a good fixed path gets you there.
Scanline's win is a fact about E2's design. In April 2008 Owen built
16×16 puzzles with the border/interior colour balance deliberately tipped
(2 border and 19 interior colours, then 14 and 15) and scored scanline,
middle-first and border-first orders on each. The tipped designs are
attackable: middle-first beats scanline by ~150× on the 2/19 design,
border-first wins on the 14/15. On E2's actual 5/17 split, every deviation
loses: middle-first costs 1.22×1060 nodes against scanline's
1.07×1050, because the design balances border and interior
tileability, giving the puzzle "no weak areas to start tiling from"
(msg 5263,
5243). Row scan is not a law
of nature; it is the correct answer to one specific, adversarial design.
The magic 10×16 square. Why row scan and not, say, a 4×4 block order?
Louis Verhaard's frontier-shape rule of thumb: most orders hit their
node-count maximum around depth 160, so what matters is the shape your
order has built there, and the best known depth-160 shape for E2 is a
10×16 rectangle (with two corners filled). Orders whose frontier passes
through "the magic 10×16 square" are near-optimal; a 2×2 block scan does, a
4×4 does not, which is exactly the gap Max had just measured
(msg 5868,
5879). This is the piece the
constraint-count curve alone can't see: two orders can pay joins on the same
schedule and still differ through the perimeter of the region they build.
Why "solve the border first" is a trap. The most natural human instinct,
build the easy frame and then fill the middle, is quantitatively one of the
worst orders, and in 2025 Owen and Peter McGavin spelled out why on exactly
this depth-160 peak. The border really is easy: after the start piece there are
about 5.17×1037 ways to complete it, of which only 14,702 can be
filled by the 196 interior pieces, so about 3.5×1033 frames must be
tried before one even can finish
(msg 11572). That alone is
hopeless, but it is not the real problem. The problem is that with the frame
fixed first, the node count keeps climbing after the border to a peak of about
1057 around 160 pieces, versus about 1043 for scan-row. A border-first
order commits early to the border and then walks straight into a peak fourteen
orders of magnitude taller than scan-row's, because only about 1 in 1031
frames leads anywhere and each is expensive to rule out
(msg 11573). Row scan wins not by
building a nicer frontier but by never paying for a border it cannot yet know is
doomed.
Which scanline, though? Even within row scans there are eight
orientations: four corners to start from, rows or columns
(msg 6018). Max ran multi-day
sampling estimates of the full-tree size per orientation: right-to-left held
stable just below 2.7×1040 nodes, while bottom-up, left-to-right
(the orientation that connects the mandatory starter piece earliest, and
the one Verhaard already used) came out around 2.3×1040
(msg 6015,
6023). A folklore choice
turned into a measured ~15%: small next to the orders of magnitude above,
but free.
Deviations that paid. The scan-order orthodoxy was tested constantly,
and mostly won, but not always. Owen himself solved his 14×14 challenge
with a decreasing squares order after scanline stalled; on irregular
boards the balance argument no longer holds
(msg 3124). Hybrids were
proposed that start as increasing squares (cheaper early) and switch to
scanline before the mid-depth peak
(msg 6142). And Max found a
genuine within-scanline improvement: at a row start, border candidates that
differ only in their unmatched second border colour are equivalent: refute
one and you have refuted them all. Verhaard, delighted ("Finally something
that beats simple scan-row!"), implemented it and confirmed ~10% of the
search space gone at near-zero cost
(msg 5980,
5983,
6062).
The community mostly published the deviations that had a case. The project
lab notebook holds the other kind, attractive orders that lost, and the
k-regimes above can name the mechanism for each.
Spirals pay a closure tax. On a bordered 14×14 interior testbed
(8 seeds per arm), an outside-in spiral jammed at depth 26 on all 8 seeds,
at the closing corner of its first ring. A free-rim spiral stalled at
depths 133 to 141 with 0 completions, against 344 to 347 for a row scan;
with every assistance in the engine switched on it still walled at 131 to
140 with 0 completions in 300 s, against 446 to 448 for the row scan. The
k-law says why: a free-rim spiral's whole first ring runs at one placed
neighbour or fewer per cell, nearly unprunable branching, while a bordered
spiral pays a closure tax: every ring carries 4 or 5 cells with three
placed neighbours at its corners and loop-back, and three-sided cells are
close to unfillable. Row scan is the Goldilocks order, a constant two
neighbours and a single active damage zone.
Starting from the clues loses. "Begin where the information is" sounds
right and points backwards. In a 60 s head-to-head on the real puzzle (one
configuration, one run, so read it as our test rather than a refutation), a
clue-centric order spreading outward from the five clue cells reached depth
42 (62 matched edges) while a dynamic most-constrained-cell order, which in
practice eats the border first yet stays free to abandon it (unlike the
committed frame of the trap above), reached depth 164 (282 matched edges).
The cells around the centre clues carry the widest piece domains on the
board, so clue-centric prioritizes exactly the least-constrained cells.
An X through the clues loses too. Pre-committing two 3-cell-wide
diagonals through the five clues, then filling outward from them, finished
51 matched edges below its baseline (396 against 447 after identical
budgets, single seed).
Three experiments, one pattern, stated as a pattern and not a theorem:
every static order we tried that routes early through wide-domain interior
cells lost. A static order does not dodge the hard region; it chooses which
region becomes the hard region. It also chooses where the failures land:
where the mismatches pile up on a
near-perfect board tracks the scan order, bottom-centre for top-down scans,
top for bottom-up ones (visible on the community's own 469-class boards),
corners for centre-out spirals. A fill order decides not only how much you
fail but where.
The academic literature lands in the same place. Ansotegui, Bejar,
Fernandez and Mateu, who turned edge-matching puzzles into SAT/CSP
benchmarks, worked with static orders of the checkerboard-plus-centre-spiral
family; replayed in our engine without the full all-different filtering
their models assume, that order exploded node counts by roughly 600×. And
the backtracking baseline of Wauters, Vancroonenburg and Vanden Berghe's
2012 hyper-heuristic study raced scan-row against spiral, inverse-spiral
and mirrored orders and found scan-row significantly best: an independent
rediscovery of the mailing list's thesis.
All of the above optimizes a full search, whose node count peaks near
depth 160. In October 2008, while privately sitting on the boards that
would win the $10,000 scrutiny prize, Verhaard answered a different
question from Owen: what is the best order when you are chasing a partial
score, and therefore living much deeper in the board
(msg 6111)? His answer named
a geometry: the best orders he had found resemble a comb search (most
rows searched horizontally, then the remaining rows searched vertically),
with the tooth length tied to the target: "The lower the score you aim for,
the longer the teeth of the comb become"
(msg 6112). Max had
independently converged on nearly the same order (twelve rows of scanline,
then column scan) and reported scores "roughly 1 edge lower" than what
Louis's solver accomplished
(msg 6126).
The intuition: a full search must cross the depth-160 bottleneck as cheaply
as possible; a high-score search instead wants many cheap ways to finish.
Each vertical tooth is a short, nearly independent column whose failures are
local, so deep, high-scoring frontiers are reached again and again. The comb
was one half of the machine behind the 467; the other half,
depth-gated edge slipping, decided
what the teeth were allowed to place. And the two were tuned together:
Verhaard optimized the fill order and the slip array jointly with a Markov
chain over (depth, slips used), built from measured per-depth fit
probabilities (msg 6423).
Order design by calculation, not folklore. The full engine is on
the Verhaard eii page.
The comb sat in the record history for eighteen years before we tried it at
home; rereading the messages above is what surfaced it. Grafting the comb
geometry onto a from-scratch beam-search producer (top rows row-major,
bottom rows filled as short vertical teeth) raised its best raw partial
from 455 to 457 matched edges of 480 on strict five-clue boards, from the
visit order alone; nothing else changed. Behind that sentence sits a sweep,
not a lucky run: five orders (row-major plus comb splits after rows 8, 10,
12 and 14) crossed with three beam widths (2048, 8192 and 16384), 24 seeds
each at matched compute, on 8 cores. The new ceiling only appears at the
widest beam, where split 14 reached 457 on one seed and split 12 reached
456 on two, each board checked three independent ways (an independent
re-scorer, an external verifier and the producer's own count; strict
five-clue placement, all 256 pieces distinct). At smaller widths the comb
ties row-major's best.
What the comb moves reliably is the floor and the middle of the
distribution. At beam 2048, splits 10 and 12 lift the 24-seed minimum from
446 to 449 and the median from 449 to 451; at the widest beam, split 12's
median is one edge up. Split 12 also reaches 455, row-major's former
ceiling, at half the beam width, and at beam 8192 a 24-seed sweep yields 15
boards at 453 or better against row-major's 9: +67% high-quality starting
boards per unit of compute. Verhaard's teeth-length rule holds from the
high side too. Long teeth (split 8, 8-cell teeth) regress below row-major
at every beam width; short teeth win. Split 12, Max's exact "twelve rows,
then columns", is best for the whole distribution, while split 14 with its
2-cell teeth finds the single best board on a lower median: a thinner,
higher-variance finish geometry. The mechanism is the intuition stated
above, now measured: each short tooth is a nearly independent column whose
failures stay confined, so deep high-scoring frontiers are reached again
and again.
The order also decides where the recoverable slack ends up. An exact
re-solve of the last three rows lifts a row-major 455 board to 457 and does
nothing for a comb 457 board: the comb's last-filled, least-constrained
region is its vertical teeth, not its bottom rows, so a row-band repair
aims at the wrong place. A teeth-aligned, column-band exact re-solve takes
comb boards to 459 and no further, because the teeth leave the beam already
exactly optimal (an exact solver proved a 32-cell teeth region optimal in
about 21 s); the comb spends during construction the slack the repair would
otherwise recover. Both routes converge at 459: the comb front-loads the
score, row-major leaves it in a recoverable tail, and order plus endgame
repair harvest the same slack. For scale, 455, 457 and 459 are matched-edge
counts on strict five-clue boards from one notebook producer on 8 cores;
community boards sit higher, and the records page has
the standings.
Everything above orders cells. The sibling knob is the order of the
pieces tried within a cell: Zajc's head-to-head was about which cell to
open next, this one is about which candidate goes into it first. The
notebook answer is a clean null. Inside a fixed row-major fill, reordering
every cell's candidate list by global colour scarcity (rarest colours
first) changed nothing measurable over 8 seeds per arm: at equal 60 s
wall-clock the median was 389 matched edges (hint-pinned, five-clue puzzle) in
every arm, baseline order, scarcity-first, and a deliberate anti-order
control (most-abundant colours first) that was designed to lose. The
control did not lose; its best run (419) beat the baseline's best (415).
Node throughput was flat across arms, 8.2 to 9.6 million nodes per second,
so the reordering is free, and worthless, in both directions. (Before
comparing, the baseline arm was verified node-for-node identical to the
unmodified engine.)
The mechanism is a starved signal. By the time a row-major scan reaches a
cell, the candidate list is already filtered down to the handful of pieces
matching two fixed colours, and a global supply-and-demand feasibility
prune already exploits colour scarcity across the whole remaining pool; the
scarcity ordering re-derives, more coarsely, information the search already
uses, and which of three legal pieces goes first barely matters when the
bucket will be exhausted anyway. Scope it as measured: candidate order was
inert in our engine at one operating point (one prune stack, one 60 s
budget, global scarcity signals only), not "value ordering never matters
anywhere". It also rhymes with the one within-scanline win above: Max's
~10% came from removing border candidates, not reordering them. The wins
live in pruning and in cell order.
Watch the row scan. After the first row, nearly every placement meets
exactly two placed neighbours: left and below. The constraint curve
flatlines at 2, and the cumulative joins climb steadily: the search pays
as it goes.
Switch to the spiral. The entire first ring (60 placements) arrives
with at most one placed neighbour: sixty nearly unconstrained choices
stacked up before the interior starts paying them back. The cumulative
line sags below the row-scan reference exactly where the tree can least
afford it.
Try the diagonal. Surprise: the counts look almost like the row
scan's. This is the limit of the neighbour-count view: the diagonal's
frontier is longer than a scanline's for much of the middle game, a shape
effect only complex theory (or the magic
10×16 rule) can score.
Select the comb at teeth 4. Twelve rows of scanline, then vertical
teeth, Max's order from
msg 6126. Note the little
cliff at each new tooth: the first column pays a weak, 1-neighbour cell
at its base, the price of the high-score geometry.
Lengthen the teeth. More of the board moves into vertical mode and
the weak placements multiply. That is Verhaard's trade, stated
visually: the
lower the score you aim for (the more slips you'll allow), the longer
the teeth you can afford.
Then race it for real. The
search-path playground lets you draw any of these
paths, or your own, on a real puzzle and watch solvers race them,
with a live plateau-peak estimate alongside.
At runtime, nothing: a fixed fill order is a precomputed array of 256 cell
indices, and "choose the next cell" is an index increment: O(1), zero
branches, which is precisely the speed argument that killed dynamic
ordering for E2 (msg 5860).
All the cost and all the payoff live in the tree the order induces:
Between order families, orders of magnitude. Middle-first on E2 is
1010 times more expensive than scanline
(msg 5263); a 4×4 block
order costs ~70× over 1×1 scanline by Max's complex-theory estimates,
the gap the magic 10×16 rule summarizes
(msg 5867).
Within a family, measurable percentages. Bottom-up-left-right vs
right-to-left scanline: ~15%
(msg 6023); border-piece
equivalence pruning: ~10%
(msg 6062). Worth having,
never decisive.
Choosing wrong is invisible. A bad order produces no error, just a
tree that is 1010 times bigger, silently. That is why the community's
real advance was not any single order but the ability to score an order
before running it: Owen's shape counts, then
complex theory, then Verhaard's Markov
chain tuning order and slip schedule together
(msg 6423).
Every record engine since has treated the order as a designed, calculated
object: Verhaard's comb-plus-slip-array
(eii), McGavin's
complex-theory-picked bottom-left scan, and the fixed scan order under
Blackwood's depth-gated breaks. Twenty
years of scan-order science compress into one instruction: before you spend
a single CPU-hour, spend a millisecond scoring the path.