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 has the setup;
where the community got there first, we cite the archive message.
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 →
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 1019 CPU operations on the puzzle, then shut down
without a solution
(msg 3511). And the quantum
hope has been re-floated regularly, from
2007 to
2024.
Why this is a wall →
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).
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 →
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 1090 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 →
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×1011 permutations, and 17×17 blows up to 2.97×1013
(msg 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 →
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).
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 →
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 1012 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), and veterans
pointed back at years of earlier 2×2 work in the archive
(msg 11429).
Why this is a wall →
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.
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 result on this page:
imitation learns the distribution it is shown and cannot invent the rare
structure that a record needs.
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 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.
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 measures exactly how little), and
the endgame damage lands in the interior corners
(MOSAIC).
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.
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 1040
where it needs to be 104. A 10× or 100× speedup on an out-of-reach tree is
still out of reach (msg 5883).
Macro-tiles are a real constant-factor win for a fast solver, which is why the
block-order playground supports them, they are just not a
domain reduction, and only a domain reduction would move the needle.
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). A pruning
rule only helps if it fires before the checks you already run, not after.
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.