Complex theory: counting the search before you run it
Brendan Owen's complex theory estimates how wide the search tree is at every depth, and even how many solutions exist at all. Many in the community consider it the single most important thing to understand about Eternity II.
Complex theory is due to Brendan Owen, one of the puzzle's vetters; Peter
McGavin implemented it in C
with arbitrary-precision arithmetic and posted the numbers. We're writing it
up here because a community member (Dan Karlsson) rightly pointed out it was
missing, and because it underpins almost every good decision you can make
about a solver, above all the choice of search order.
Take a scan order and walk it one cell at a time. At each new cell, a random
unused piece matches its already-placed neighbours with some probability: a
product of per-edge colour-match chances. Multiply that by how many pieces are
left and you get the expected number of ways to extend the board one cell
further. Chain this down all 256 cells and you have a closed-form estimate of
how wide the search tree is at every depth and, at the last cell, how many
full solutions the puzzle has.
It is an average, not a true count: it assumes the 22 edge colours are drawn
independently, which they aren't (four edges are bolted to one rigid piece).
But calibrated against small puzzles where the real count is known, it lands
within about a factor of two. That is more than enough to see the shape.
With only the mandatory centre piece the puzzle has on the order of fifteen
thousand solutions; add the four other clues and the expected count drops to
about 4×10−8: overwhelmingly, exactly one. This is the formal
reason the 5-clue puzzle has a single designed solution.
Brendan tabulated the estimate not just for E2 but for the four smaller clue
puzzles, and this is where it earns trust. The clue puzzles are small enough
that their trees were searched exhaustively, so the estimate sits right next
to the true count. It lands within a factor of two, the calibration this page
keeps promising. The table also records the best-known fill order for each
puzzle, and they are not all the same: the order is a choice the search-space
shape rewards or punishes, not a property of the puzzle.
quantity
Clue #1
Clue #2
Clue #3
Clue #4
E2 · 1 hint
E2 · 5 hints
Estimated solutions
2.6e11
7.6e36
8.2e8
4.9e34
14,702
1
Solutions, actually countedcounted
115,071,633,408
·
2,195,647,488
·
·
·
Estimated search-tree nodes
1.3e13
2.0e40
1.1e11
8.4e37
1.4e47
3.1e40
Search-tree nodes, actually countedcounted
1.0e13
·
2.2e11
·
·
·
Best known fill order
spiral-in
border first, then vertical scans
spiral-in
border first, then vertical scans
horizontal scans from bottom-left
horizontal scans from bottom-left
Brendan Owen's complex-theory numbers for the four clue puzzles and the real E2 board. On the small clue puzzles the whole tree was searched, so the estimate can be checked against the true count: it lands within a factor of two. The best fill order differs per puzzle, the order is a choice, not a given.
Transcribed verbatim from the community "Backtracker estimates" table on groups.io. Blank cells are blank in the source (the clue puzzles too large to count exhaustively, and the un-run E2 columns).
The clue puzzles are four data points; Brendan checked the model far more
widely. His "NxM puzzles using Eternity II subset pieces" study plots the
estimated nodes-per-solution against the actual count for on the order of a
hundred smaller boards built from E2's own pieces, and on a log-log axis the
cloud hugs the diagonal across eleven orders of magnitude, from ten nodes to
1011. That is the real basis for trusting the estimate on a board too
large to ever search: it has been right everywhere it could be checked. A
companion study even shows a dead-simple static score (the sum of per-cell
edge-match counts, squared) predicts a rectangle's total node count with an
R2 of about 0.84, more evidence that the search cost is baked into the
board's structure before you place a piece.
Plot the expected width at each depth and three regimes appear. Their shape is
what the community calls the E2 funnel. Play the sweep below and watch the
counter: it climbs into the billions, then barely moves for a hundred cells
across the plateau, that flat crawl through an astronomically wide band is the
wall, before the last sixty pieces funnel it back down.
depth
1/256
ways to extend
1
regime
Growth
Growth. Every placement still has dozens of legal successors. The tree widens fast.
A search head sweeping depth 1 → 256 along the expected-branch curve. The number over the plateau is how many legal ways there are to extend a partial board there, and how little each placement prunes.
The same estimate, run live for different scan orders. The plateau peak (the
widest point the search must cross) is decided by the order alone, before a
single node is placed.
Growth (depth 1–50). Solutions multiply geometrically from one to
about 1027. Every placement is essentially free; nothing constrains you
yet.
Plateau (depth 50–200). The tree is at its widest, about 1045
ways to extend, while the solution count barely moves. This is where
backtrackers spend roughly 99% of their time, matching Joe's empirical
finding that most time is spent below depth 150.
Collapse (depth 200–256). The width falls from 1045 back to about
104. The last ~60 pieces are tightly constrained: each one placed
eliminates orders of magnitude of branches. The endgame is locally easy;
the hard part is reaching it.
If almost all the work is in the plateau, the goal isn't raw speed. It is
getting across the plateau to the funnel entrance (around depth 200), after
which the search chains down deterministically. And because complex theory
scores a scan order before you run it, you can compare orders by the height of
their plateau peak rather than by trial and error. That is the rigorous
version of a rule this site states everywhere: the fill order is a
first-class choice, and McGavin's bottom-left, left-to-right scan was picked
because complex theory said it was good.
The same idea works if you place 2×2 or 3×3 tiles instead of single pieces: a
whole block of cells is committed at once, with its internal edges already
matched. The search-path playground lets you do this for
real: pick a block shape (1×1, 2×1, 2×2, 3×3, …) and stamp blocks onto the
grid to build a block path. Race it and a dedicated macro-piece solver commits
one whole valid sub-assembly per block instead of one piece at a time, so the
search advances region by region. The plateau-peak estimate alongside still
scores the cell order your blocks imply, predicting the cost before you run a
single node.
Complex theory is a first-moment estimate, so it is blind to one thing:
whether the many counted partial boards are genuinely distinct. The
entropy and area-law results show that
distinctness collapses past ~80 cells, a second-order effect the
independent-edge model cannot capture. So use complex theory to choose orders
and read the tree's shape, never as a true count or a bound.
The theory's paper trail runs through the mailing list. Brendan Owen posted
the completed model in April 2008
(msg 5197,
5209), and later proved a neat
closed form: for a scan order the node-count peak sits at depth
256(1−1/e)≈161.8
(msg 8125); the funnel above
peaks there empirically. Peter McGavin typeset the theory
(msg 9188), published the
14,702 expected-solutions figure as early as 2011
(msg 8924), and in 2017
delivered its strongest validation: solving Brendan's hint-free 10×10
benchmark by searching complex-theory-ranked first rows: roughly 180
core-years, landing inside the theory's predictions
(msg 9686,
9688). His 2024 reference C
implementation (msg 11197) is
what this page's live estimator ports, line for line.