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 →
The absence runs deeper than rotations and duplicates. We also checked for
color-relabeling symmetry: an exhaustive enumeration of every color permutation
that could map the piece set to itself (up to rotation) finds only the
identity, because each of the 22 interior colors has a unique adjacency
profile across the pieces. The symmetry group has size one; the generator broke
every color swap too. (The interior colors do carry one piece of structure
worth knowing: they fall into exactly three frequency classes, 5 colors
appearing 24 times each, 5 appearing 48, and 12 appearing 50, totalling 960
half-edges, twice the 480 edges.)
Split the piece set by its color-relabeling structure and prune the search
with invariants computed over the part of the board already placed.
Measured, with a mechanism close to a proof. In a backtracker that only
ever places matching pieces, the placed region always satisfies any constraint
that mentions placed cells alone: the search enforces those invariants by
construction, so a pruner that inspects what is already on the board never
fires. We tried three variants of the idea and none of them pruned a single
branch; there are no speedup or score numbers to report because the pruners
literally never fired. A spiral scan-order variant was additionally worse, not
better, since it lost the good early-region ordering. The scope worth keeping:
this refutes static invariants on the placed region under a matching-only
search, not every conceivable use of the piece set's color structure. Useful
pruning has to look at what could still go, forward checks over the candidates
for unplaced cells, or live inside a search that permits mismatches. Compare
the border-supply check further down: that one fires too late; these never
fire at all.
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. 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).
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). Instead: the pruning
that does pay on this grid is exact, not probabilistic;
arc consistency and the
all-different matching filter.
We later ran the obvious rescue ourselves: message passing plus a per-piece
Lagrangian penalty meant to restore the use-once constraint, on a generated
4×4. Measured, and it does not converge. At least one piece's marginal
collapses to exactly zero everywhere, and once a marginal hits zero no
multiplier can revive it, so the duality gap never closes: the residual stayed
around 1.2 to 1.7 across more than 50 outer iterations in all three damping
and step-size settings we tried (minimum piece marginal 0.00 in every
configuration; maximum 2.2 to 2.3 where it should be 1). That is one toy
instance and three settings, already failing at 4×4. The contrast with the
tensor-network note below is the informative part: the identical Lagrangian
trick works when the inner step is an expensive exact contraction and fails
when it is cheap message passing. The accuracy of the inner marginals is the
whole game.
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 →
Pre-sort each candidate list so pieces whose bottom and right edges open the
most options downstream get tried first: a move-ordering heuristic that costs
nothing at solve time.
Measured. On the official puzzle, single thread, 10 seconds × 3 runs
against a tuned baseline: same maximum depth (192), same best score (344
matched edges), same node-visit pattern, and throughput dropped from 84 or 85
million to 80 million nodes per second, about 5%. A multi-thread 30-second
spot check scored 429 against a 444 baseline, but that is a single seed: it
shows the ordering can perturb outcomes, not that it reliably hurts. The
mechanism: the deepest reachable point was set by the solver's mismatch
schedule, not by move order, and "future-flexible" pieces correlate with
popular pieces the existing ordering already tries early, so the sort adds no
information; it only reshuffles memory layout and pays for it in cache
locality. Scope: this is the verdict for one tuned schedule path on the
official puzzle; the picture could differ on schedules without a depth wall or
on generated puzzles with uniform color distributions. Same lesson as the
belief-propagation entry above, from a cheaper angle: informed static
orderings do not beat the defaults here.
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 →
One amendment from later notebook work: the blind spot can be patched, at
small scale. Adding a Lagrangian penalty per piece on top of the contraction
recovers uniqueness well enough to fully solve generated 4×4 (one second) and
6×6 (five minutes) puzzles, verified piece-unique and fully matched. The cost
wall arrives long before 16×16: the first full-scale attempt ran out of memory
around 3 GB and died, and the truncation needed to fit may discard too much
for the fix to keep meaning. That is a single attempt, so the patched variant
is unvalidated at full scale rather than proven impossible; the Proven verdict
above is about plain contraction. Enforcing uniqueness through multipliers
needs accurate inner marginals, and accuracy at 16×16's color count demands a
bond dimension whose memory and compute blow up.
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). Instead: the
LP and ILP 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.
The integer version is no rescue at full scale either. With the 60 border
cells fixed, we asked an open-source MIP solver (HiGHS, 4 threads, a 30-minute
limit) for an integer-optimal interior: roughly 154,000 binary placement
variables and 13,000 constraint rows. It returned without finding any feasible
integer placement at all, and even mislabeled the empty assignment "optimal"
at objective 0, a reminder to sanity-check solver statuses. Scope that result
tightly: one solver, default settings, one budget. It does not refute integer
programming; we have since watched the encoding and solver choice change
everything on smaller instances (a CP-SAT-class solver full-solves instances
the same LP/MIP stack fails on, in under a second). A generic formulation at
full scale simply exceeds what one mainstream solver could even find feasible
in half an hour; restricted-region and restricted-corpus integer models do
work, and that is where these solvers earn their keep.
Precompute, for every small patch of cells, the minimum number of edge
corrections any completion needs, and sum those per-patch costs into an
admissible heuristic: the technique that cracked Rubik's Cube and the
15-puzzle.
Proven. On Eternity II the heuristic carries exactly zero information, by
direct computation rather than sampling. The official set has 22 distinct
interior colors and, across the 256 pieces with rotation, every one of the 22
is available on every side, so every potential interior edge is individually
matchable. The per-edge upper bound therefore comes out at 480, the maximum,
and the per-2×2-patch bound (225 patches × 4 internal edges, corrected for
overcounting) is also exactly 480. Both collapse to the trivial statement that
all 480 edges could match. Pattern databases earn their keep when the
objective is non-additive, when a patch's joint cost exceeds the sum of its
parts, as Rubik's move counts do. This puzzle's matched-edge count is exactly
additive per edge, and the only joint structure, each piece used once, couples
cells globally, which no local patch can see. Instead:
LP and ILP relaxations, which do
encode the global piece-once constraint, strictly dominate any patch table.
Encode placement as 0/1 integer equations, take the kernel lattice, reduce it
(LLL or BKZ), and search for the solution as a closest-vector problem: the
machinery behind the famous knapsack and integer-programming attacks.
Proven (the core arguments are structural; the scaling probe is measured).
Three doors close in turn. First, the part a lattice attack handles cleanly,
each cell gets one piece and each piece one cell, is a totally unimodular
assignment system, solvable in polynomial time by the Hungarian algorithm; our
recovery experiments (10 of 10 planted 2×2 and 3×3 instances recovered
exactly, following the Aardal, Hurkens and Lenstra kernel-lattice
reformulation) demonstrate the method solving a problem that was never hard.
Second, the part that is hard, facing colors must agree, is a conditional
("bilinear") constraint with no faithful linear-equality embedding short of a
combinatorial blowup of auxiliary variables, which erases the lattice
advantage. Third, the color-supply system is not a knapsack: every coefficient
is exactly 1, so the classical low-density subset-sum attacks (Lagarias and
Odlyzko 1985; Coster and colleagues 1992) do not even apply, and an LLL attack
on the unit-weight embedding degenerates to plain enumeration. The scaling
probe agrees: exact-integer LLL on just the easy assignment kernel took 0.35 s
at 2×2 and 42.6 s at 3×3, and was killed past 175 s at 4×4 (kernel dimension
993); the full 16×16 backbone would be around 262,000 variables. (Those
timings are one pure-Python exact implementation, a practical statement rather
than an asymptotic one; the structural arguments carry the verdict.) Per-color
sublattices are cheap to reduce, under half a second, but 12 of the 60
shortest vectors examined at 3×3 already require one piece to sit in two
cells: they omit exactly the constraints that matter. The puzzle's hardness
lives in a problem shape, bilinear matching plus global distinctness, that
lattice-reduction tools are not native to; the sub-problem they are native to
is already polynomial.
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 →
Make the board differentiable: a doubly stochastic piece-to-cell matrix by
Sinkhorn normalization plus per-cell rotation softmaxes, maximize expected
matched edges by gradient descent with temperature annealing, then round to a
real board.
Measured. The relaxation gap is intrinsic. The soft score climbs to
367/480, but the best rounded board scores 336 matched edges (other seeds 324
and 325, best of 4), and rounding gets worse as the temperature sharpens; a
straight-through hard-forward variant is worse still at 280. The strongest
test was also the smallest: restricted to the last two or three rows of a
459-out-of-480 board of ours (strict scoring, all five clues placed) with the
rest frozen, exactly where exact re-solving reliably earns one to three edges,
the optimizer could not even reproduce the board's own tail (41 versus the
incumbent's 49 region matches over 8 restarts on two rows; 63 versus 76 on
three rows). One campaign, but the gap on the easiest region is 15 to 20
percent below the incumbent, far outside noise. The mechanism echoes the
fake-480 and tensor-network entries on this page: the continuous optimum is a
superposition of many mutually incompatible boards, and the constraint the
relaxation softens, every piece used exactly once, is precisely the one that
carries the hardness, so softening it fakes matches no real permutation can
honor. It is a third failure mode in the learning family; see
when learning collapses.
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 →
Build row by row, using exact bipartite matching to pick the best possible
row given the edge colors the previous row exposes.
Measured. Each row is locally optimal; the board still dies. In our test
the build hit a wall around row 10 of 16, at 294/480 matched edges, with rows
11 and beyond infeasible outright: the locally best early rows consume exactly
the pieces whose edge colors the later rows need, and by row 10 the remaining
pool can no longer supply the required colors at all. Keeping the 32 best
row-sequences in parallel does not help; all the leading candidates draw on
the same scarce pieces and starve together at the same row. (Single-run proof
of concept; the greedy dynamic program is essentially deterministic. Much
larger beams, 256 or 1,024, were not tried, though the shared-pool argument
predicts the same wall.) The one-line mechanism: local optimality does not
compose, because the binding resource is the shared piece pool and a
row-at-a-time commit spends it invisibly. What works instead is joint
foresight across rows: the full-board
beam search our builders actually
use.
Grow the board top-down and bottom-up at the same time and join the halves at
a middle row: each half gets the easier, border-anchored part of the work.
Measured. The join kills it. With independent top and bottom beams at
width 32, piece-disjointness alone failed on more than 99.9 percent of
pairings: 0 valid pairs out of 1,024. A second variant guaranteed disjointness
by re-running a dedicated bottom-up beam per top state, about 8 times the
compute, and still produced zero merges, because the meeting row demands an
exact 16-position color-sequence match on an alphabet of about 22 colors, and
with the remaining pieces constrained the matching set is effectively empty.
Two obstructions stack: independent searches pull from the same pool of
promising pieces, and even disjoint halves must agree on a full row of
interface colors that neither side optimized for. Building from both ends does
not remove the interface difficulty; it relocates the mid-board wall to the
meeting row. Scope: two variants at one beam width; softened joins (allow a
few interface mismatches then repair, or meet on a diagonal) were never run,
so the verdict covers the exact-join versions, not bidirectional construction
in general. The exact-methods cousin of this idea has its own page:
meet in the middle.
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 lines up every
exact attack against the barrier it dies on, so you can see why this one was
always going to stop there.
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.
A colony of agents each builds a full board greedily at random; a pheromone
field over (cell, piece, rotation) decisions is reinforced along the paths of
the best finishers (a standard max-min ant system: evaporation, elite
deposits, clipping), so future builds concentrate on globally consistent
regions.
Measured, three failures deep. The standalone ceiling was 296/480 matched
edges, the best over the swept configurations (best configuration at one seed,
proof-of-concept scale), below even a plain wide-search baseline. Turning the
pheromone learning on made the colony worse: the population mean dropped from
about 265 to about 252 over 40 iterations while a no-pheromone random-restart
control held about 265 and reached 289; that control was a direct
head-to-head. And the learned field carries no information about what good
boards actually do: checked against a 455-scoring board of ours (matched
edges, all five clues placed), the field ranked the good board's choice first
in 1.2 percent of cells against a chance rate of 0.9 percent, with a mean
percentile of 0.502, statistically indistinguishable from a coin flip, so it
cannot even serve as guidance for a better search. The mechanism is credit
assignment: with about 600 legal candidates per cell and good final scores
arising from vast, interchangeable sets of early choices, "this decision was
on a good path" is noise. The pheromone amplifies an arbitrary early lottery
winner and the colony converges prematurely on a mediocre basin.
A 2024 result showed that for the travelling-salesman problem, a strong MCTS
with a parameter-free prior matches learned neural heatmaps
(arXiv:2411.09238). Port the underlying
engine (Fu, Qiu and Zha, AAAI-21)
faithfully, mapping its k-opt tour move to the exact assignment analogue, a
cyclic relocation of k pieces that is always feasible.
Measured, two clean negatives. As a refiner: the pairwise-swap phase is a
sound repair engine (boards damaged from 452 matched edges down to 295 recover
to exactly 452) but never exceeds its starting score, and the headline
k-opt-style move is completely inert; across every run and the whole
hyperparameter grid (mixing weights, cycle length, simulations per move),
roughly 2,500 to 3,150 sampled relocation cycles per run produced zero
improvements. As a from-scratch producer: a constructive per-cell bandit
variant, after a 2.5 to 3.3× hot-path optimization to make the comparison
fair, performs like a beam of width 512 to 1,024, measurably below a
width-2048 beam at equal wall-clock (mean solve fraction 0.596 versus 0.743 on
our scaling ladder of generated puzzles; 0.644 versus 0.721 on the hard rungs,
24 runs), and the gap does not close with budget. The zero-improving-cycles
result is structural rather than a tuning failure, though only the faithful
port was tested. The mechanism: TSP k-opt works because the move chain follows
existing tour edges, so it reconnects mostly compatible structure by
construction; an edge-matching placement problem has no tour for the chain to
follow, and relocating a whole tile disturbs matches on all four sides at
once. The paper's transferable half, that search plus a cheap prior can
replace a learned model, held up; the search itself is TSP-shaped. On this
puzzle, raw beam width remains the
better use of the same wall-clock.
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 transplant version fails the same way, from the other direction. We took a
442-matched-edges partial of ours and a finished 459 board (strict scoring,
all five clues placed) and grafted the donor's placements over the largest
region where the two disagreed, 71 cells: the score fell from 442 to 271.
Grafting cumulatively through the six largest regions never climbed back above
271 (241 to 271 across the six variants). Local repair on this puzzle
typically recovers five to ten edges; the graft digs a hole of about 170. One
partial and one donor, a decisive worked example rather than a universal
constant, but the mechanism is generic: a grafted region gains its donor's
internal matches and breaks edges all along its boundary with the untouched
cells, and a region's boundary is large relative to its interior, so boundary
damage dominates. Repairing it means re-choosing the cells just outside the
seam too, and iterating that requirement expands until transplanting a region
has become rebuilding half the board. Good boards do not decompose into
exchangeable parts.
Every solver in the record-holding backtracker family can leave at most one
mismatched edge per cell; by construction its index cannot even represent a
cell that breaks twice. Yet top community boards produced by local search do
contain four or five such double-break cells. So build the same search over
the wider space where a cell may charge two breaks, and hunt where no one else
can.
Measured. At equal wall-clock the wider vocabulary earns nothing. A paired
A/B of 54 rounds, 27 seed-matched pairs across three schedule shapes and two
scan directions at 600 seconds × 4 threads per round, gave 20 ties, 4 wins for
the wider engine and 3 for the classic, every difference within ±3 matched
edges, with identical per-shape min/median/max distributions (415/420/425 in
both arms for one shape). The wider engine visited 0.87 to 0.94 times the
nodes for the same outcomes. A separate exhaustive census behind a 208-cell
prefix of a 464-scoring community board (five-clue scoring; context on the
records page) found exactly four completions at seven or
fewer total mismatches: the 464 itself and three one-cell variants at 462 and
463, and zero of them used a double-break cell. The mechanism: the wider space
is explorable but never forced. With the mismatch budget spread over the whole
board the search almost never has two units of headroom left at one cell, so
it spends its budget the way the classic engine does; and in the near-perfect
endgame region the double-break stratum is empty outright. The known
double-break cells in community boards sit mid-board and were made by
local-search repair moves, not by any depth-first pass. Scope: an
equal-wall-clock tie for one engine family on the official puzzle, not a proof
that the wider stratum is empty everywhere; the starting hypothesis, that the
community plateau is a representability wall, is downgraded to an unsupported
conjecture, not refuted.
View a perfect board as a codeword, every internal edge a parity check, and a
high-scoring board as that codeword plus a small error syndrome; if the error
pattern has structure, syndrome decoding or belief propagation should localize
and clear it cheaply.
Measured, on one 459-out-of-480 board of ours (strict scoring, all five
clues placed); this entry and the next are two lenses that treat the mismatch
pattern as structured signal, and both found none. The syndrome is as
unstructured as it could be: the 21 mismatches involve about 21 distinct color
pairs (only two pairs repeat), split into 13 disconnected fragments, and every
color's total half-edge count is even, so the parity floor on mismatches is
zero; nothing algebraic forbids a perfect board or forces these errors.
Decoding accordingly buys nothing. Exactly re-solving the error-support cells
(34 scattered cells, warm-started) holds at 459 across 8 seeds and a
200-second solve, no better than the plain rectangular-band re-solve it was
raced against; growing the region one hop makes it too big to re-solve well
(433); and without a warm start the scattered region regresses to 448. One
board studied, though the mechanism suggests the picture is generic: decoding
shortcuts require a structured error (repeated collisions, a low-dimensional
coset, one repairable cluster), and a maximally spread syndrome whose
fragments couple only through the piece inventory is exactly the regime where
decoding degenerates into the same exhaustive tail search we already run. The
mismatches are a budget allocated globally, not a local error to invert.
Model each mismatch as a charged topological defect in the color field:
defects should sit at conservation-forced, minimum-interaction sites, and
opposite charges should annihilate.
Measured, same board as the previous entry, and every premise fails.
Position predicts mismatch location extremely well: the row index alone
separates broken from unbroken edges with an AUC of 0.895, and all 21
mismatches sit in the last-filled rows. Every color signal is noise:
color-rarity AUCs of 0.46 to 0.50, and the mismatches carry common colors, not
rare ones. The color-conservation floor on the tail is about zero; the frozen
top pushes down no color demand the remaining pieces cannot supply, and even
the sharpest orientation-aware matching bound forces only 0 to 2 mismatches
where 10 to 19 exist. The charge spectrum has essentially no opposite-sign
pairs, so there is nothing to annihilate. A defect-repulsion objective added
to the exact tail re-solve changes which tie-broken solution comes out but not
the ceiling; the last row is provably optimal given the rows above it. (A
cold-start region-solve sweep was stopped after a single seed, at 441, once
the verdict was clear; treat that number as a single-seed illustration.) The
finding worth keeping: the mismatches are not defects in a color field at all.
They are pure combinatorial orientation-frustration from piece exhaustion in
whatever region is filled last; the color bookkeeping balances, and what
breaks is the joint four-sided constraint over all remaining pieces at once.
No single-cut, per-color, or pairwise-energy reduction captures it. The
geometry of where breaks land has its own page:
mismatch geometry.
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).
We measured the premise ourselves, from two directions. First, cataloguing
borders: a time-bounded search (120 seconds, explicitly not exhaustive; the
true count is unknown) produced 75,173 complete, internally valid border
rings. Feeding a 500-frame sample to the solver as pinned frames, 47 percent
exhausted the search in under 200 milliseconds under baseline propagation, and
essentially all were rejected outright once full propagation ran against the
official clue pieces. A ring that closes on itself satisfies only pairwise
edge-matching around the rim; joint feasibility with the clues and the
interior's use-each-piece-once constraint is a far stronger condition, and
essentially none of the catalogued rings meet it.
Second, perfect borders as seeds. We generated 5,000 distinct piece-unique
perfect borders by dynamic programming (all 60 border cells placed, every
border edge matched), sampled 100 evenly, and gave each the same pipeline: a
60-second constraint-propagation interior fill, then a 60-second local-search
polish. Top score of the whole batch: 436/480 matched edges; about half the
starts landed between 420 and 427, a quarter between 380 and 419, and none
above 437. The 455-to-460-class boards of the same era (strict scoring, all
five clues placed) all came from a depth-first producer that does not fix the
border first. The polish used a single seed and 60 seconds per start, so this
is a cheap-filter screen, not an exhaustive refutation: under a short
equal-budget polish, none of 100 border-first starts came within 20 edges of
what the direct search reaches. A perfect border over-commits the interior;
the fill then optimizes within whatever interior color profile the border
allows, and that family plateaus far below the best basins.
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 is why local repair cannot cross
this last gap, whatever board you start it from.
Use an exact constraint-propagation backtracker to build a very deep
consistent prefix, pin it, and hand it to the local-repair search as a head
start.
Measured, one configuration; scope it accordingly. The pinning trick
genuinely deepens the exact search itself; between rounds it took the solver
from depth 27 to depth 152, score 23 to 297 matched edges, a real depth
amplifier, and that positive half remains useful when hunting exact solutions
rather than high scores (see the
backtracking pages). But as a score-seeker it
backfires: repair from the pinned 297/480 partial (184 cells fixed) finished
at 424/480 matched edges, versus a 430-to-450 median (best 451) for plain
cold-start repair in the same-era 16-seed comparison batch. That seeded arm
was a single seed, one schedule and one repair preset, so read it as "this
configuration underperformed every plain cold start in the comparison batch",
not as a refutation of all exact-prefix seeding. The mechanism is the same
start-from-the-wrong-object lesson as the fake-480 entry above: an exact
solver in first-solution mode optimizes consistency, not score. It returns the
first feasible deep prefix it finds, not a good one; "deep and consistent" is
not "close to good", and pinning makes the mistake permanent, since the repair
search cannot undo cells it inherited and would never have built that skeleton
itself.
The center has the most rotational freedom, so start there and let the
constraints accumulate as you grow toward the border.
Measured, and the intuition is backwards. Head-to-head on generated
puzzles from 5×5 through 8×8 against row-major and border-first orders,
center-out lost every one of the six configurations: typically 10 to 100 times
slower, it failed outright on four of the six within budgets where
border-first finished (one 5×5 stuck at depth 22 of 25 after 2 million nodes
on a puzzle border-first solved in 2,000 nodes), and it was about 60 times
slower on one it did solve; the 8×8 case was the worst of the three orders
tested. Measured on generated small puzzles with one solver's scan orders, but
the direction and magnitude were uniform across all six cases. The mechanism:
freedom is the enemy of propagation. The border supplies hard, immediate
constraints (the gray edges); the center supplies none, so a center-out search
commits to arbitrary colors with no way to detect infeasibility early. More
freedom means less pruning, not faster search. Instead: the
fill order page covers orders that
do help.
Frame first, compact region growth around the clues, most-constrained-cell
first, disciplined backtracking, and deliberate "spend your mismatches wisely"
steering: code up how the best human solvers think.
Measured, and none of it survives. A perfect frame is found in
milliseconds and buys no traction (none of the five clues touch the border).
The real killer is piece exhaustion, and it is order-invariant: along a build,
the mean number of unused pieces that fit a cell perfectly collapses from 3.5
in the early rows through 2.6, 2.0, 1.6 and 1.4 to 0.4 by the final row, so a
mismatch is nearly always forced at the end, wherever the end is. Three human
fill orders were raced at 6 seeds each (matched edges): row-major 392,
center-out spiral 382, clue-anchored growth 359. Every order dumps its
mismatches on whatever it fills last (the spiral on the outer ring;
clue-anchored smeared everywhere, and scored worst), and a "preserve common
colors for later" tie-break made every order worse. A single guided trajectory
tops out around 392, roughly 67 edges below what a wide beam reaches on the
same hardware. The mechanism: the deficit that produces mismatches is a
conserved, global inventory fact; ordering chooses which cells inherit it,
never whether it exists. And the one human faculty that would actually help,
tracking thousands of hypotheses in parallel with global lookahead, is exactly
what beam search already is. See also
why there are no forced moves.
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. 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). Instead: the one free lever that does
shrink the tree is the fill order.
Drive the scheduled backtracker of the record-holding family inward in
concentric rings, on the theory that a layered geometry matches where the
breaks want to be.
Measured. It hits a structural depth wall that more time does not move. A
one-hour run on the official puzzle visited 3.4 billion nodes with the deepest
placement stuck at a wall of depth 80: the wall was at 80 after five minutes
and gained one cell over the rest of the hour. A two-hour run finished at the
same 382/480 matched edges as the five-minute run. One schedule paired with
one ordering, one run per budget, so the verdict is that this pairing fails,
not that layered orders are refuted in general. The mechanism: the scheduled
solver's relaxation plan, where it is allowed to spend its mismatches, is
tuned for a row-by-row scan; an externally imposed ring geometry fights the
schedule instead of helping it, so the search jams at a fixed depth regardless
of budget. Fill order matters, but
it has to be co-designed with the mismatch schedule, not bolted on.
Chess engines share a transposition table between threads; do the same here,
hashing each explored frontier so no worker re-explores a subtree another
worker already exhausted.
Measured, and the build was cancelled on the strength of the measurement,
which is the cheap way to kill an idea. Eight workers ran 15 seconds each on
the official puzzle with an identical solver, only the candidate order
shuffled per worker: each worker placed about 214 cells at its deepest board
(maximum depths 192 to 235 across the eight), but the pairwise agreement
between any two workers' deepest boards averaged 1.8 cells (maximum 5), an
agreement fraction of 0.8 percent. One measurement run of eight workers, but
against the 50-plus percent a shared table would need to pay, the effect size
leaves no ambiguity. The mechanism: the search is extremely path-dependent;
the first piece tried at depth k reshapes what is available at depth k+1,
compounding down the whole trajectory, so differently ordered workers never
reconverge on the same partial board. A dedupe table only pays if paths
reconverge the way chess openings funnel into shared middlegames, and this
search has no such funnel. The flip side is good news: parallel workers
genuinely cover different territory, which is why simple uncoordinated
parallelism scales (eight threads reached depth 235 and 427 matched edges in
30 seconds where one thread reached 192 and 344);
distributed solving builds on
exactly that.
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.
Instead: the supply-versus-demand idea pays when it is folded into the
propagation that fires first, the
all-different matching filter.
Seventeen years later we re-ran the same idea in our own engine, across all
colors instead of just the border: track how many piece edges of each color
remain unplaced, and cut the branch when a frontier cell demands a color whose
supply is exhausted. Official puzzle, single thread, one 10-second run: the
baseline visited 630 million nodes at 63 million nodes per second; with the
check, 388 million at 39 million, roughly a 40 percent throughput loss for the
same maximum depth (192) and the same best score (344 matched edges). Zero
additional pruning, and the reason is now precise: a candidate index keyed by
(top color, left color) already is this propagator. If placing a piece would
exhaust a color some upcoming cell demands, that cell's candidate bucket is
simply empty one step later and the search backtracks anyway; the explicit
check pays per node for a cut the index makes for free.
A dynamic per-color budget variant fares no better on a strict backtracker:
for each color, track how many of its half-edges are already permanently
mismatched, and prune any partial board that can no longer reach the target
score for that color. Across 15 deep snapshots of real search states (depths
195 to 212 of 256 cells) it fired zero times: a solver that never places a
mismatching piece only ever creates partials that cannot yet violate the
budget, and by the time the budget would bite, ordinary propagation has
already cut the branch. (On a mismatch-tolerant search the check is untested
here.) A related non-lesson: sorting all candidates globally by a color-rarity
weight, the same order at every cell, is not an informed heuristic at all; it
is equivalent to a fixed relabeling of the pieces and adds no information.
A valid border ring must trace an Eulerian cycle in the graph whose vertices
are border-edge colors and whose edges are border pieces: a clean necessary
condition proposed on the mailing list back in 2007. Check it during search
and prune borders that can no longer close.
Measured, zero pruning power on the official puzzle. Tested at five search
depths with 200,000 trials each, a million partial borders in all: the
Eulerian condition never fired on any configuration that ordinary propagation
had not already killed. The condition is necessary but vacuous on the actual
piece set, and the reason is a design fact: the official set was generated
with its rare colors placed only on the border ring, two per border piece, and
that structure makes Eulerian closure automatic for any border partial that
gets anywhere near a full ring. The configurations the check would reject die
much earlier under standard arc-consistency-style propagation. Same family
lesson as the lollypop check above: a prune only helps if it fires before the
checks you already run.
We proved that a set of 2×2 piece combinations can never appear in any fully
matched board. The obvious next step: check every completed 2×2 patch during
the depth-first search and prune when it is forbidden.
Proven vacuous by construction, then verified empirically: across 24
boards and 225 patches each, 5,400 completed patches, zero were forbidden,
exactly as the argument predicts. The forbidden-pattern test asks whether four
pieces can match internally under any rotations; but an edge-strict search
only ever completes a 2×2 after already matching all four internal edges, so
every patch it completes is feasible by construction and the check can never
fire. The theorem's discriminatory power is over piece subsets, which would
need a forward-checking integration that tests patches before their cells are
filled, and in a row-major scan the cheap version of that forward check is
already performed implicitly by the candidate index. The theorem itself is
still true and useful elsewhere: see
forbidden patterns. Same closing moral as
the lollypop entry: a prune that fires after your existing checks is worth
exactly nothing.
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.
One late convergence is worth recording. Four lenses tried independently in
the same season, codeword decoding, defect physics, gradient descent on a soft
board, and encoded human strategy, each rediscovered the same fact from a
different direction: the obstacle is global piece distinctness and inventory
exhaustion, not local edge matching. When four unrelated formalisms all hit
the same wall, the wall is probably the thing to study.
See why a faster computer doesn't help.