# Why a faster computer doesn't help > 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. - Canonical page (with interactive figures/demos): https://eternity2.dev/research/why/prune-vs-speed/ - Updated: 2026-07-01 - Topics: speed, search-space, backtracking - Reproduce: `just research-prune-vs-speed` - Source: Article, source and results on GitHub (research/topics/prune-vs-speed) — https://github.com/raphael-anjou/eternity2/tree/main/research/topics/prune-vs-speed - Source: Peter McGavin: early doom-detection pruning is generally too expensive to be worthwhile (groups.io msg 11848) — https://groups.io/g/eternity2/message/11848 - Source: @95A31: a full battery of feasibility checks turned out to be useless on an 8×8 search (groups.io msg 11856) — https://groups.io/g/eternity2/message/11856 --- Picture the search as a tree. From the empty board you choose a piece for the first cell; from there a piece for the second; and so on, 256 cells deep. The number of leaves at the bottom is the branching factor raised to the depth, an astronomically large number. To prove a region has no solution, a search has to walk that tree. Now there are two ways to do less work. You can go **faster**: a better engine, more cores, hand-tuned inner loops. Or you can make the tree **smaller**, pruning branches that can't lead to a solution, so the effective branching factor drops. These sound similar. They are not even close. ## Constant versus exponential A speedup is a constant divisor. Make the machine 1000× faster and you do 1000× less waiting, the same whether the tree is ten levels deep or ten thousand. It buys you a fixed multiple, full stop. A prune compounds. Shave even a few percent off the branching factor and you save that fraction at every single level. Over 256 levels the savings multiply into each other: cutting the branching factor from $b$ to $b'$ divides the work by $(b/b')^{256}$. A 5% cut, applied all the way down, is worth $(1/0.95)^{256} \approx 5\times10^{5}$, a five-hundred-thousand-fold speedup's worth of work, from one cheap structural idea. That beats almost any speedup a real machine can offer. ## Feel the gap Trade a raw speedup against a small per-level prune and watch the prune win by orders of magnitude. > **[Figure]** Interactive: pruning power vs raw speed — interactive: PruneVsSpeedLab. Rendered on the canonical page (link above); not shown in this markdown export. ## Why this is exactly E2's curse If pruning is the lever that matters, the hard puzzles are the ones you can't prune. Eternity II was tuned to be precisely that. Four of its walls are, underneath, all the same statement: there is nothing local to prune on. - **[No forced moves](/research/why/no-forced-moves)**: every interior cell still has 73 to 137 legal neighbours, so propagation almost never collapses a cell to one choice. The branching factor stays stubbornly high. - **[On the hardness peak](/research/why/phase-transition)**: the piece and colour counts sit where there is about one expected solution, leaving no solution-dense region to aim a statistical shortcut at, the trick that cracked Eternity I. - **[The area law](/research/why/entropy-area-law)**: the count of genuinely-distinct partial boards collapses past ~80 cells, but no local scoring signal can see that global collapse, so you can't prune toward it cheaply. - **[Rigidity](/research/why/rigidity-wall)**: even at a record board, the move to a better one is huge and indivisible, with no gradient to follow and nothing nearby to prune away. ## What it means for everything else here This is the lens for the whole research section. A far faster engine makes the same search cheaper, not smaller, and does not move the record. Every experiment that did move the needle changed the shape of the search instead: a different scan order, a learned prior over where pieces sit, a confined region for the mismatches. And every dead end is, at heart, a prune that the puzzle's global structure refuses to honour. Speed first feels productive; it is almost never where the gap to 480 is hiding. ## The community landed here too, the hard way The counterintuitive half of this is that even *legal* pruning often loses. A check that detects a doomed partial board and backtracks early sounds like a free win, but if the check costs more than the subtree it saves, a plain backtracker that just barrels ahead is faster. Peter McGavin put the settled view plainly on the groups.io list: methods that try to detect a doomed partial placement and backtrack early "are generally considered too expensive to be worthwhile". A newcomer running a decision-diagram solver, @95A31, then confirmed it from scratch: after building a full battery of feasibility checks he reported that "all the feasibility checks I implemented turned out to be useless", with a complete 8×8 search still grinding through 953 billion nodes over 17 hours. The lesson is not that pruning is bad, it is that a prune only pays if it is *cheaper than the search it removes*, and on this puzzle almost nothing local clears that bar. > **Note** > > The tree numbers in the demo are illustrative: a branching factor and depth chosen to be E2-like and legible, not a measurement of a specific solver. The hardness curve and node counts, however, are real engine measurements on small puzzles, deterministic and reproducible with `just research-prune-vs-speed`. The principle itself, constant divisor versus exponential divisor, is exact. ## Related - [Which wall stops which method](https://eternity2.dev/research/why/walls-and-methods) — The research section has two halves: the structural walls that make Eternity II hard, and the algorithms built to climb them. This page is the bridge: each method lined up against the wall it actually attacks, and the score where that wall stopped it. - [Complex theory: counting the search before you run it](https://eternity2.dev/research/why/complex-theory) — 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. - [No forced moves](https://eternity2.dev/research/why/no-forced-moves) — The usual way to crack a logic puzzle is to find a spot where only one piece fits, place it, and repeat. That lever doesn't exist here: every interior piece has between 73 and 137 possible neighbours, and not one is ever pinned to a single option. - [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. - [The rigidity wall](https://eternity2.dev/research/why/rigidity-wall) — Every record board we have is frozen in place. You cannot nudge your way from a great board to a perfect one, and we can prove it. - [Arc consistency, from AC-3 up](https://eternity2.dev/research/build/reduce/arc-consistency) — Forward checking looks one move ahead; arc consistency makes every cell's candidate list defend itself against every neighbour's, to a fixed point. Mackworth's AC-3, the optimal refinements that followed, and what the whole family actually measured on this puzzle, including where it is unsound.