# 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.

- Canonical page (with interactive figures/demos): https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/
- Updated: 2026-11-14
- Topics: search-space, backtracking, exact-methods
- Reproduce: `just experiments approach-pricing`
- Source: Approach pricing: question, numbers, routes, tripwires (https://github.com/raphael-anjou/eternity2/tree/main/research/experiments/approach-pricing)
- Source: Real-puzzle profile: the measured row-scan tree (https://github.com/raphael-anjou/eternity2/tree/main/research/experiments/real-puzzle-profile)
- Source: Working record of the two nights, with the log of corrections (https://github.com/raphael-anjou/eternity2/tree/main/research/program/night)

---
## The question and the answer

What would an exact solution of the 16x16 cost by search, and can any known family of ideas close the gap between that cost and what can be afforded? Answer: no route examined closes it. The largest gain that survived an independent re-check is about 5.5 bits of nodes, against a gap of 56 to 73 bits (budgets of 2^78 and 2^61.5 nodes, table below). The work is parked, not proven impossible: several closures rest on one reader or one solver family, and the page marks which. The conditions that would reopen it are listed below.

## The fixed numbers

Every other page in this series links here instead of restating these.

| Quantity | Value | Where it comes from |
|---|---|---|
| Row-scan tree, real pieces, five clues | 10^40.457 nodes, 2^134.4 (95% interval 10^40.440 to 10^40.473) | measured, `research/experiments/real-puzzle-profile/RESULTS.md` |
| Affordable: very large distributed effort | 2^78 nodes | `research/experiments/approach-pricing/README.md` |
| Affordable: 1,000 core-years at 1e8 nodes per second | 2^61.5 nodes | same file |
| Gap against those two budgets | 56 to 73 bits | same file |
| Gap against a modest run of about 10^15 nodes (about 2^50) | about 84 bits | derived here: 134.4 minus 50 |
| Expected solutions | about 14,702 with the starter clue, about 1 with all five | [solution counting](/research/build/analysis/solution-counting/) |

The 84 bits belongs to the 10^15 run and the 56 to 73 bits to the two larger budgets; the two are never combined. A tree size is an estimate from a particle sampler (one million particles), not an enumeration; the measured values differ from the random-model figures by -0.033, +0.0004, +0.009 and +0.007 digits (all within 0.04; the model figures are carried over from the earlier pricing, not recomputed here).

## The one-sentence reason

Every check that works, works too late. The tests that refute wrong boards refute nearly all of them only from depth 144 to 192, while the widest level of the measured tree is at depth 158, and a perfect free cut at depth 144 would save at most 2.4 bits of 134.4. The argument and its ceiling table are on [late filters](/research/lab/experiments/raphael-anjou/full-solve/late-filters/).

## The ten pages

Results on generated boards are toy-board results and are never Eternity II progress.

| Page | What was measured | Result | Status |
|---|---|---|---|
| [The price of a full search](/research/lab/experiments/raphael-anjou/full-solve/price-of-a-full-search/) | Size of the row-scan tree on the real pieces, with five, one and no clues | 10^40.457 nodes with five clues; no way found to shorten it | measured (estimates) |
| [Frame and corners](/research/lab/experiments/raphael-anjou/full-solve/frame-and-corners/) | Cost of refuting wrong frames of the real pieces | Cheap refutation of a full frame is dead; the cheap information (about 17.4 bits) sits at the clue corners; frames away from them undecided | parked |
| [What a known tile is worth](/research/lab/experiments/raphael-anjou/full-solve/worth-of-a-known-tile/) | Bits removed by a pinned tile, by cell, on painted 16x16 boards | 1 to 10 bits by position (median 5.8), sub-additive; 10 spread tiles still above 10^15 nodes, 16 to 24 under | measured on painted boards; end-to-end check only |
| [Late filters](/research/lab/experiments/raphael-anjou/full-solve/late-filters/) | Ceiling of a free cut by depth | A free cut at depth 144 saves at most 2.4 bits | refuted (derived arithmetic on a measured profile) |
| [Seven families priced out](/research/lab/experiments/raphael-anjou/full-solve/approaches-priced-out/) | Desk studies and re-checks of seven families of approaches | Largest surviving gain about 5.5 bits; none priced at 10 bits or more | parked; some closures rest on one reader |
| [Relaxations on small boards](/research/lab/experiments/raphael-anjou/full-solve/relaxations-on-small-boards/) | Semidefinite lift and low-rank form on 4x4 to 6x6 toys | Clean on 3 of 5 boards at 5x5, not exact on one, undecided on one; cannot run at 16x16; the low-rank form is a random search that annealing beats | refuted (toy boards) |
| [Learning against propagation](/research/lab/experiments/raphael-anjou/full-solve/learning-against-propagation/) | Clause learning against a propagation-only solver, 5x5 to 7x7 | Learning adds +1.31 bits at 5x5 and +2.03 at 6x6; no 7x7 value; on 160 wrong prefixes of the real pieces the stop line fired and learning gives no lead over arc consistency | negative (independently re-checked) |
| [Port fidelity](/research/lab/experiments/raphael-anjou/full-solve/port-fidelity/) | Seven differences between our port and a record-style engine | All seven fixed; with five clues the faithful defaults do worse than the old ones | refuted as an improvement |
| [Ten engine experiments](/research/lab/experiments/raphael-anjou/full-solve/search-engine-tracks/) | Node cost, orders, backjumping and bounds on 6x6 to 9x9 | A node 5.3 to 6.1 times cheaper for the identical search; no method shrank the tree | refuted for the tree (toy boards) |
| [Keying experiments](/research/lab/experiments/raphael-anjou/full-solve/keying-experiments/) | Replay and keying of dead ends | Three killed, two kept as measurements; a rate effect of 53 times, about 5.7 bits | refuted as a route |

## What would reopen this

From the tripwires in the approach-pricing record. Any one of them is enough.

1. A published method shows a class-level gain. Price it against the routes index and the ceiling table first.
2. Tiles of the solution become available from outside the search. An extra pin is worth about 10 bits at best and about 6 at the median on painted boards, and a 10^15 run needs more than 10, probably 16 to 24, spread pins.
3. Hardware improves by 15 orders of magnitude or more. Every credible multiplier together is about 2.5 orders.
4. A re-check or a run overturns a closure: the convex lift turns out exact at 6x6; the far stratum of frame cores resolves below break-even; a non-tree solver's work grows by less than 0.75 of the tree's from 6x6 to 7x7; a learning solver's lead over propagation alone rises with size.

The standing rule for reopening is a price of 10 bits or more and a falsifying experiment that takes under a day.

## The full record

The working record of the two nights (12 and 13 November 2026) is in the repository under [research/program/night](https://github.com/raphael-anjou/eternity2/tree/main/research/program/night): the daily reports, the log, the desk studies and their re-checks, and the index of routes. About sixty statements made during the work were withdrawn or corrected, among them a figure for the interior cost under a true frame (replaced by about 10^13.6 nodes in the mean), and the record keeps every one with its replacement. Read the log of corrections before quoting a number from any of the working notes; the pages of this series carry only what stood after it.

For record scores and the open frontier, see [records](/research/records/) and [open problems](/research/open-problems/).

## Pages in this section

- [The price of a full search](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/price-of-a-full-search/): 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.
- [Frame and corners: a wrong frame is not cheap to refute](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/frame-and-corners/): 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.
- [What a known tile is worth under row scan](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/worth-of-a-known-tile/): 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.
- [Late filters: every check that works, works too late](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/late-filters/): 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.
- [Seven families of approaches priced out against the row-scan tree](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/approaches-priced-out/): 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 engine experiments on small boards: faster nodes, no smaller trees](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/search-engine-tracks/): 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.
- [Keying and replay experiments: no gain found, one effect measured](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/keying-experiments/): 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.
- [Port fidelity: seven differences from a record engine, and a five-clue regression](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/port-fidelity/): 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.
- [Semidefinite relaxations on toy boards: a negative result](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/relaxations-on-small-boards/): 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 against propagation: a negative result](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/learning-against-propagation/): 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.

## Related

- [Raphaël Anjou's experiments](https://eternity2.dev/research/lab/experiments/raphael-anjou/): A notebook of Eternity II search experiments, organised into the shared engines they run on, the combination pipelines that chase the score, four studies that take one search paradigm apart a decision at a time, and exact endgame solves. Each has its idea, its best board, and the questions it left open. The best reaches 463 of 480.
- [Solution counting: measuring what you cannot find](https://eternity2.dev/research/build/analysis/solution-counting/): Nobody has ever seen a full Eternity II solution, but first-moment (expected-value) models of puzzles built like it predict about 14,702 with the starter. This page is the story and the craft of that estimate: exact censuses on small boards, the expectation formula and the modelling choices behind 14,702, and the culled-search estimates that repeated runs made credible.
- [Records & solvers](https://eternity2.dev/research/records/): Eternity II has never been solved, but nearly two decades of community effort have pushed the best board to 470/480. Who holds what, how they did it, and why some headline "480" boards are not actually the real puzzle.
- [Open problems](https://eternity2.dev/research/open-problems/): The open frontier of Eternity II in one place: every angle still worth a run, the wall it attacks, what has been tried and where it stopped, and whether it is a newcomer-tractable target or a hard, well-mapped one.
- [Dead ends and untested claims](https://eternity2.dev/research/build/dead-ends/): Approaches that did not move the score on Eternity II, each graded by the strength of its evidence. Twenty verdicts rest on committed data, a named public report or a derivation; twenty-two more are stated without evidence a reader can open, and are listed separately with the experiment that would settle each, and one measured negative result on clause learning.
