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 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).
All of the above optimizes a full search, whose node count peaks near
depth 161. 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.
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.