# 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. - Canonical page (with interactive figures/demos): https://eternity2.dev/research/why/complex-theory/ - Updated: 2026-07-02 - Topics: structure, backtracking - Source: Brendan Owen's peak-depth closed form, 256·(1−1/e) (groups.io msg 8125, 2010) — https://groups.io/g/eternity2/message/8125 - Source: Peter McGavin's 10×10 solve validating complex theory (groups.io msg 9686, 2017) — https://groups.io/g/eternity2/message/9686 - Source: Brendan Owen's solution-count estimates (groups.io message 5209) — https://groups.io/g/eternity2/message/5209 - Source: Peter McGavin's reference implementation and depth table (groups.io message 11197) — https://groups.io/g/eternity2/message/11197 - Source: Brendan Owen's "Backtracker estimates" tabulation for the clue puzzles and E2 (groups.io Databases) — https://groups.io/g/eternity2/databases - Source: Brendan Owen's estimated-vs-actual validation, "NxM puzzles using Eternity II subset pieces" (groups.io Files, Brendan folder) — https://groups.io/g/eternity2/files/Brendan/NxM_actual_theory.pdf - Source: Brendan Owen's heuristic-vs-node-count study, "Heuristics: 20×2 rectangle" (groups.io Files, Brendan folder) — https://groups.io/g/eternity2/files/Brendan/heuristics.pdf --- > **Whose idea this is** > > Complex theory is due to Brendan Owen, one of the puzzle's vetters; Peter McGavin [implemented it in C](https://groups.io/g/eternity2/message/11197) 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. ## The idea 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. ## The headline numbers | Clues placed | Expected solutions | | ---------------------------------- | ------------------ | | One clue (the centre piece only) | ≈ 14,702 | | All five official clues | ≈ 1 | 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\times10^{-8}$: overwhelmingly, exactly one. This is the formal reason the 5-clue puzzle has a single designed solution. ## The same numbers, checked against reality 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. > **[Interactive: ClueEstimatesTable]** Rendered on the canonical page (link above); not shown in this markdown export. 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 $10^{11}$. 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 $R^2$ of about 0.84, more evidence that the search cost is baked into the board's structure before you place a piece. ## The funnel 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. > **[Figure]** interactive: ComplexFunnelAnimated. Rendered on the canonical page (link above); not shown in this markdown export. ## Try it: the order decides the funnel 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. > **[Figure]** Interactive: the search-space funnel — interactive: ComplexFunnelLab. Rendered on the canonical page (link above); not shown in this markdown export. ## Three regimes - **Growth (depth 1–50).** Solutions multiply geometrically from one to about $10^{27}$. Every placement is essentially free; nothing constrains you yet. - **Plateau (depth 50–200).** The tree is at its widest, about $10^{45}$ 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 $10^{45}$ back to about $10^{4}$. 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. ## Why it changes how you search 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. ## Bigger tiles 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](/playground/paths) 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. ## What it can't see 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](/research/why/entropy-area-law) 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. ## Provenance and validation The theory's paper trail runs through the mailing list. Brendan Owen posted the completed model in April 2008 ([msg 5197](https://groups.io/g/eternity2/message/5197), [5209](https://groups.io/g/eternity2/message/5209)), and later proved a neat closed form: for a scan order the node-count peak sits at depth $256\,(1 - 1/e) \approx 161.8$ ([msg 8125](https://groups.io/g/eternity2/message/8125)); the funnel above peaks there empirically. Peter McGavin typeset the theory ([msg 9188](https://groups.io/g/eternity2/message/9188)), published the 14,702 expected-solutions figure as early as 2011 ([msg 8924](https://groups.io/g/eternity2/message/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](https://groups.io/g/eternity2/message/9686), [9688](https://groups.io/g/eternity2/message/9688)). His 2024 reference C implementation ([msg 11197](https://groups.io/g/eternity2/message/11197)) is what this page's live estimator ports, line for line. ## Related - [Why a faster computer doesn't help](https://eternity2.dev/research/why/prune-vs-speed) — The single most important idea in hard combinatorial search: shrinking the space you search beats searching it faster, by an exponential margin. Eternity II is engineered so you can barely shrink it at all. - [Tuned to the hardness peak](https://eternity2.dev/research/why/phase-transition) — Eternity II uses 22 colors. They split 17 interior to 5 frame-only, and that 17 is exactly where this kind of puzzle is hardest to solve. - [Entropy and the area law](https://eternity2.dev/research/why/entropy-area-law) — Eternity II has two rules: edges must match, and each piece is used once. The first is generous. All the hardness lives in the second.