# Dead ends > Approaches we tried that look promising and don't move the needle on Eternity II, written down with what we found so you can spend your time elsewhere. - Canonical page (with interactive figures/demos): https://eternity2.dev/research/build/dead-ends/ - Updated: 2026-07-21 - Topics: search-space, learning, exact-methods - Source: eternity2.net shuts down: 1.6 TFlops, 10^19 CPU operations, no solution (groups.io message 3511) — https://groups.io/g/eternity2/message/3511 - Source: Max on probability propagation: constraint influence fades out about two cells away (groups.io message 6208) — https://groups.io/g/eternity2/message/6208 - Source: Markus Zajc: macro-tiles are a speedup but no domain reduction (groups.io message 5883) — https://groups.io/g/eternity2/message/5883 - Source: Markus Zajc benchmarks border-supply pruning: 0.0014% fewer tests, 8% slower (groups.io message 6060) — https://groups.io/g/eternity2/message/6060 --- Approaches we tried that look promising and don't move the needle on Eternity II. None of these are bad ideas in general; they just don't crack this puzzle. We're writing down what we found so you can spend your time elsewhere. Each entry opens its verdict with a firmness tag: **Proven** means a theorem or an exact computation closes the door; **Measured** means we ran it (or the community did) and watched it fail; **Reported** means another researcher ran it and wrote up the failure, and we have not re-run it ourselves. Where the verdict comes from our own runs, the linked “why” page carries the exact reproduction command, and [run it yourself](/research/build/run-it-yourself) has the setup; where the community got there first, we cite the archive message. ## Symmetry breaking *Assume the board has rotational or mirror symmetries and fix some pieces to shrink the search.* **Proven.** The official set was built with no rotationally-symmetric pieces and no duplicates, and the single center clue pins orientation. There's no global symmetry to break, so fixing corners just makes an arbitrary, not a free, choice. [Why this is a wall →](/research/why/rare-color-geography) ## Just throw more compute at it *Run the same SAT or search solver on a bigger machine, a GPU, an FPGA, or quantum hardware.* **Measured.** The wall isn't clock speed, it's how well the problem is encoded and how the search space is shaped. GPU SAT solvers give a small constant speedup at best; quantum annealers show no advantage at the scale this would need. The same algorithm, faster, hits the same wall a little sooner. The community ran this experiment at scale: the eternity2.net grid put 1.6 teraflops and over $10^{19}$ CPU operations on the puzzle, then shut down without a solution ([msg 3511](https://groups.io/g/eternity2/message/3511)). And the quantum hope has been re-floated regularly, from [2007](https://groups.io/g/eternity2/message/1446) to [2024](https://groups.io/g/eternity2/message/11407). The ceiling this is tested against is the standing 470/480 record; Blackwood, who set it, reported that SAT solvers, GPUs and pre-solved 2×2 caches did not help him past it ([Records & solvers](/research/records)). [Why this is a wall →](/research/why/prune-vs-speed) ## Survey propagation *The message-passing method that cracked huge random SAT problems by finding solution clusters.* **Proven.** It assumes the problem looks locally like a tree. Eternity II is a grid with a short cycle in every 2×2, which breaks that assumption. In practice the messages flatten out instead of sharpening, the opposite of what makes it work on random SAT. There are no published successes for it on grid puzzles. The community noticed the flattening early: in 2008, experiments with propagating piece probabilities found that constraint influence from the clues and corners seems to “fade out” about two cells away ([msg 6208](https://groups.io/g/eternity2/message/6208)). Instead: the pruning that does pay on this grid is exact, not probabilistic; [arc consistency](/research/build/reduce/arc-consistency) and the [all-different matching filter](/research/build/reduce/alldiff-regin). ## Belief-propagation move ordering *Run belief propagation over the colors and use its per-cell hints to decide which piece to try first.* **Measured.** The hints come out almost uniform, so they barely rank the candidates. When we raced it head-to-head, picking the next move at random did as well or better, because a fixed informed order tends to repeat the same mistakes. [Why this is a wall →](/research/why/no-forced-moves) ## Tensor-network counting *Treat the board as a tensor network and contract it to count or score boundary-consistent colorings.* **Proven.** It can only enforce that touching edges match, not that every piece is used exactly once. That blind spot is enormous: it counts on the order of $10^{90}$ boundary-consistent colorings against the puzzle's roughly one real solution. Local message passing simply can't see the global one-piece-per-cell rule. [Why this is a wall →](/research/why/entropy-area-law) ## Solve the colors first, place pieces later *Reformulate the board as a line graph over colors, solve for a color-adjacency arrangement that is edge-consistent everywhere, then hope that arrangement is easier to turn into a real tiling than solving for pieces directly.* **Measured.** It is a clean idea, explored on the list in 2023 to 2025: strip the puzzle down to which color meets which, solve that smaller object, and use it as a scaffold. The trouble is the smaller object is not small. Enumerating just the interior color arrangements for E2 leaves about $6.6\times10^{11}$ permutations, and 17×17 blows up to $2.97\times10^{13}$ ([msg 11182](https://groups.io/g/eternity2/message/11182)), and every one of those still has to be checked against a real piece assignment, because a color-consistent arrangement need not be tileable by the actual 256 pieces at all. It is the tensor-network blind spot in another costume: satisfying the color adjacencies is necessary but nowhere near sufficient, and the use-each-piece-once constraint that does the real work is exactly what the color-only view drops. The author's own summary after the enumeration was that you would "spend a lot of time just validating one" arrangement against all its inner-color permutations. [Why this is a wall →](/research/why/entropy-area-law) ## Relaxation bounds *Solve the linear-programming relaxation to get a tight ceiling on how many edges a board can match.* **Measured.** The relaxation lets pieces be fractional and spread across cells, which fakes matches that no real board can have. The result is a ceiling around 478 while the best real boards sit near 458, a gap too large to certify anything. The binding constraint is global piece-uniqueness, which the relaxation throws away. LP formulations were on the community's table in the first summer, and already there a 4×4 took over an hour to solve ([msg 1678](https://groups.io/g/eternity2/message/1678)). Instead: the [LP and ILP relaxations](/research/build/exact/lp-relaxations) page shows what these encodings can still earn (impossibility proofs and near-optimal fills on sub-boards), which is where their value actually is. ## Learn a heuristic on small boards *Train a neural network on small puzzles, then transfer it to the full 16×16 to guide the search.* **Measured.** We trained a model that nailed small boards and watched it collapse on the real one. It learns from candidate moves filtered one way and is then asked about moves filtered very differently, and the full puzzle's colors never appeared in training. The skill doesn't carry across the size and color gap. [Why this is a wall →](/research/why/rigidity-wall) ## Enumerate local clusters first *List every valid 3×3 or 4×4 cluster, then stitch the clusters together into a full board.* **Measured.** The counts blow up before they help. When we tried it, valid clusters around a single region already ran into the tens of millions, and combining four corners reaches the order of $10^{12}$ piece-disjoint tuples. You run out of time and disk long before the constraints prune anything. The idea keeps getting rediscovered. In late 2024, 2×2 “macro pieces” came up again, at around 4 million blocks before piece-disjointness even enters ([msg 11428](https://groups.io/g/eternity2/message/11428)), and veterans pointed back at years of earlier 2×2 work in the archive ([msg 11429](https://groups.io/g/eternity2/message/11429)). [Why this is a wall →](/research/why/rigidity-wall) ## Cube and conquer *Split the SAT instance into millions of sub-cases (cubes), solve each independently, and recombine. The technique that settled Schur number five and the Pythagorean triples problem.* **Reported.** William Millilaw tested it exhaustively in May 2026 and it does not clear the board. On 16×16 the cubing phase does not partition the instance into anything tractable without heavy preprocessing, and the conquer step (a lookahead solver on each cube) was itself slower than running kissat straight. The clean result was a firm boundary: the method works up to about 8×8 and stops there. It joins the long line of exact methods that meet the same wall as integer programming and SAT decision, without a foothold past it. Instead: [which wall stops which method](/research/why/walls-and-methods) lines up every exact attack against the barrier it dies on, so you can see why this one was always going to stop there. ## Generate boards with a transformer *Train a GPT-style model on a corpus of boards, condition it on a target score, and have it emit fresh high-scoring boards the search never found.* **Reported.** William Millilaw ran the full arc in May 2026 and each stage failed for its own reason. A 51-million-parameter model learned the grammar of a board (each piece used once, 96 percent structurally valid) but not the physics: unconditioned, its boards averaged around 250 matched edges, near random. Conditioning on a target score raised the average, but every board it emitted at the top of the range was an exact token-for-token copy of a memorized community board, McGavin's 469 among them. With only a couple of dozen distinct elite boards in the training set against tens of millions of parameters, the model had simply memorized them; the score condition became an index lookup. A final reinforcement-learning pass made it worse, not better, because the elite tail is sampled far too rarely to give a stable gradient. The lesson matches the [small-board transfer](/research/why/rigidity-wall) result on this page: imitation learns the distribution it is shown and cannot invent the rare structure that a record needs. ## Recombine two good boards *Take two high-scoring boards, keep the cells where they agree, and use partition crossover to splice the disagreeing regions into a child at least as good as both parents. The genetic operator with a tunneling guarantee on pseudo-Boolean problems.* **Reported.** William Millilaw implemented it and benchmarked it on pairs of boards scoring 455 and above. It degenerates. The permutation constraint (a piece cannot be reused) forces the disagreeing regions to merge into one component the moment you close them under piece-uniqueness, so the operator collapses into "pick the better parent" on more than 99 percent of pairs. The rare improving splices topped out at 469, the score of the parents, never above. It is the same lesson as the [rigidity wall](/research/why/rigidity-wall) from the recombination side: the good boards all sit in one narrow basin, so mixing them produces more of the same rather than something new. ## Force a diverse border, then fill *The border is a smaller sub-puzzle. Solve for many different valid frames first, on the theory that variety in the frame seeds variety in the whole board.* **Reported.** William Millilaw tried it and found the premise backwards. The border is the easy part: from scratch it is already varied and quick to place. The scarce resource is the interior fill, where the pieces run thin and the mismatches concentrate. Forcing frame diversity spends effort where there is no shortage and buys nothing where there is one. It is a recurring theme in this project's own experiments too: the frame is worth surprisingly little ([STAGED](/research/lab/experiments/raphael-anjou/pipelines/staged) measures exactly how little), and the endgame damage lands in the interior corners ([MOSAIC](/research/lab/experiments/raphael-anjou/pipelines/mosaic)). ## Build a fake 480 and repair it *Start from a board with every edge matched by allowing duplicate pieces, then greedily swap in the real pieces one at a time, hoping to keep the score at 480.* **Reported.** William Millilaw ran it and it collapses into whack-a-mole: every real piece you force in breaks edges elsewhere, and the repair never converges, topping out around 463. The reason is the lesson underneath this whole page. The barrier to 480 is not that the edges are hard to match; a fake board with repeated pieces matches all of them easily. The barrier is the global constraint that each of the 256 pieces is used exactly once, and that is exactly what the fake-480 construction throws away. The wall is informational, not a matter of local edge repair. Instead: the [rigidity wall](/research/why/rigidity-wall) is why local repair cannot cross this last gap, whatever board you start it from. ## Precompute 2×2 (or bigger) macro-tiles *Solve every 2×2 block once, store the valid ones, and place four cells at a time so the search is shorter.* **Measured.** Markus Zajc worked through it in 2008: building the macro-tiles just moves the work, it doesn't remove it. You trade a small set of single pieces for a very large set of 2×2 blocks, so placing a block is faster but the number of distinct partial boards is unchanged, still on the order of $10^{40}$ where it needs to be $10^{4}$. A 10× or 100× speedup on an out-of-reach tree is still out of reach ([msg 5883](https://groups.io/g/eternity2/message/5883)). Macro-tiles are a real constant-factor win for a fast solver, which is why the [block-order playground](/playground/paths) supports them, they are just not a domain reduction, and only a domain reduction would move the needle. The ceiling this is measured against is the standing 470/480 record: Blackwood reported pre-solved 2×2 caches did not help him past it ([Records & solvers](/research/records)). Instead: the one free lever that does shrink the tree is the [fill order](/research/build/backtracking/fill-order). ## Border-supply pruning (the "lollypop" check) *Before recursing, count the remaining border-colour demand against the pieces still available; if supply can't meet demand, cut the branch early.* **Measured.** Markus Zajc implemented this supply-versus-demand check as an add-on to his constraint solver and benchmarked it on the 8×8: it cut about 0.0014% of tests while adding 8% to the runtime, a clear net loss. The reason is instructive: on almost every branch the border-supply check would have failed, the ordinary constraint propagation has *already* failed a step or two earlier, so the extra bookkeeping pays for a cut the solver was about to make for free ([msg 6060](https://groups.io/g/eternity2/message/6060)). A pruning rule only helps if it fires before the checks you already run, not after. Instead: the supply-versus-demand idea pays when it is folded into the propagation that fires first, the [all-different matching filter](/research/build/reduce/alldiff-regin). ## What every dead end has in common The gap from the best known board to a full solution doesn't look like a missing optimization. The good boards are locally frozen and globally constrained in ways that local fixes, faster hardware, and standard relaxations don't touch. Reaching the end seems to need an idea of a different kind, not more of the same. See [why a faster computer doesn't help](/research/why/prune-vs-speed). ## Related - [Run it yourself](https://eternity2.dev/research/build/run-it-yourself) — The whole site, the engine, and every result in this section run from one repository. Here is how to get it going, rebuild the WebAssembly engine, and reproduce the numbers. - [Records & solvers](https://eternity2.dev/research/records) — Eternity II has never been solved, but fifteen years 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.