The price of a full solution
An exact search of the 16x16 with five clues costs about 2^134.4 nodes, and no route examined closes the 56 to 73 bit gap against budgets of 2^78 and 2^61.5 nodes. The work is parked, with stated conditions for reopening. This page holds the fixed numbers and indexes the ten pages behind them.
Exhausting a plain row-scan search of the real Eternity II pieces with five clues takes about 10^40.457 nodes (2^134.4), measured, and the random-model prediction lands within 0.04 digits of it. The official piece set is an ordinary member of the boards painted with the same colour counts on this statistic. This prices the full search; it finds no way to shorten it.
Refuting a wrong full frame of the real pieces is not cheap: the preregistered kill line is met, and refuting partial frames costs 2.2 to 2.5 bits more than it can save. The cheap information about the frame, about 17.4 bits, sits at the four clue corners. Whether frames away from the corners can be refuted cheaply is undecided.
Under a row scan, one known tile removes between 1 and 10 bits of the full search tree depending only on where its cell sits in the scan (median 5.8 bits, on painted 16x16 boards), and several tiles together are worth less than the sum. On those boards, 10 spread tiles leave the tree above 10^15 nodes and 16 to 24 bring it under, a figure checked end to end only. Nothing here is a measurement of the real puzzle beyond two transfer checks.
A filter added to the row scan can save at most the bits its depth allows, and the checks that refute nearly all wrong boards only start to bite at depths 144 to 192, past the widest level of the tree (158). A perfect free cut at depth 144 would save 2.4 bits of the 134.4 the scan costs, so no late filter closes the gap. The ceiling table is derived arithmetic on a measured profile, not an experiment.
None of seven families of approaches (search that learns, lossy representations, the shape of the tree, adaptive orders, tile-set structure, algebraic and search-space reformulation), nor the far ideas, frame nogoods or alternative fill orders, is priced at 10 bits or more with a mechanism behind it. The largest surviving gain is about 5.5 bits, against a gap of 56 to 73 bits; a few closures rest on one reader or one solver family and are marked as such.
Ten small preregistered engine experiments on generated boards from 6x6 to 9x9 kept five and dropped five. The one measured speed-up is a node that costs 5.3 to 6.1 times less for the identical search; none of the three methods that change the tree (blocker backjumping, value order by impact, Hall matching) shrank it against its baseline. Nothing here is Eternity II progress.
Five preregistered experiments on remembering and keying dead ends found no gain that matters for a full solution. Three were killed (difference-map bands, cut-keyed replay, keying with five clues) and two were kept as measurements (quota keying, and the quota curve with five clues). The kept quota result is a rate effect of 53 times, about 5.7 bits of rate, which is not a smaller tree.
Our port of a record-style backtracker differed from the published engine in seven places; all seven were fixed and tested, and the node sequences match the earlier port wherever the legacy switches are on. With all five clues the faithful defaults do worse than the old ones (deepest depth 18 to 54 against 33 to 215 on eight seeds), so the fix is not an improvement for that setting.
On generated toy boards, a semidefinite relaxation of edge matching is certified clean on three 5x5 boards, undecided on one and not exact on one; it cannot run at 16x16 and gave no reading at 6x6. A low-rank form of it does find solutions, but as a randomised search that plain annealing beats on cost. Nothing here is Eternity II progress.
Clause learning gave no growing lead over plain arc-consistency propagation on wrong prefixes of the real pieces: the pre-stated stop line fired on summed work, and in counts learning is worth 0 bits over arc consistency. The toy boards (5x5 to 7x7) lean the same way but do not establish it. Nothing here is Eternity II progress.
deterministic: reproduces byte-for-byte
just experiments approach-pricingReprints the ceiling table of a perfect free cut from the committed level profile in seconds. It does not rerun the row-scan profile, the small-board runs or the re-checks, which sit in the experiment folders linked under sources.
Keep exploring
Referenced by
- A map of every known approach
- Raphaël Anjou's experiments
- The price of a full search
- Frame and corners: a wrong frame is not cheap to refute
- What a known tile is worth under row scan
- Late filters: every check that works, works too late
- Seven families of approaches priced out against the row-scan tree
- Ten engine experiments on small boards: faster nodes, no smaller trees