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.
deterministic — reproduces byte-for-byte
just research-prune-vs-speedPicture 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.
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 to divides the work by . A 5% cut, applied all the way down, is worth , 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.
Trade a raw speedup against a small per-level prune and watch the prune win by orders of magnitude.
At this setting the prune does the work of a 27× speedup.
A speedup is a constant divisor — it buys you a fixed multiple, no matter how deep the search. A prune lowers the branching factor at every one of the ~64 levels here, so its effect compounds: (reduced ⁄ original) to the 64th power. Even a few percent off the branching factor dwarfs a large raw speedup. That is why record solvers win on what they prune, not on clock rate — and why a puzzle engineered to resist pruning is so hard.
Illustrative tree: branching factor 5, depth 64. Eternity II's is far deeper (256), so the gap is far larger still.
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.
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 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.
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.