Every method on this shelf so far treats Eternity II as a discrete search:
place, check, backtrack. The physics community proposed something stranger.
Veit Elser's group at Cornell reformulated constraint satisfaction as
geometry, a point bouncing between two sets in a high-dimensional space,
and rode one iteration scheme from X-ray phase retrieval to Sudoku, 3-SAT and
protein folding, landing the method on the cover of PNAS
(Elser, Rankenburg & Thibault, 2007).
Edge-matching puzzles are almost a poster child for the formulation, and the
cover of that PNAS issue showed one, as the member who brought the work to
the list pointed out
(groups.io message 9347).
This page explains the method properly, because it is genuinely striking and
genuinely different from everything else in the catalogue. It then reports
what the Eternity II community actually did with it: a flurry of interest in
2014–2015, one empirical test, one shared tarball of Elser's own code, and
no campaign. This is a known road, lightly traveled here.
Embed a board state as a point x in a Euclidean space, say a real vector
with one coordinate per (cell, piece, rotation) triple, where a legal board is
a 0/1 assignment. Now define two constraint sets:
- C1, pieces used once: every cell holds exactly one piece-rotation,
and every piece is used exactly once. Edge colors are ignored.
- C2, edges match: every pair of touching edges agrees in color, and
the rim is gray. Piece inventory is ignored, so cells may hold fractional
blends or duplicate pieces.
A solved Eternity II is exactly a point in C1∩C2. The trick that
makes the formulation useful is that each set alone is easy to project
onto. Given an arbitrary x, you can cheaply compute the nearest point of
the set:
- P1(x), the nearest valid piece assignment, is a bipartite matching
problem: assign 256 pieces to 256 cells to maximize total affinity. The
Hungarian algorithm solves it exactly in polynomial time, the same
assignment engine that powers the refill step in
local search.
- P2(x), the nearest edge-consistent coloring, decomposes edge by edge:
each interior join just averages its two sides toward agreement. Purely
local, embarrassingly parallel.
Each projection is a solved problem. The hardness of Eternity II lives
entirely in the intersection, and the naive scheme, alternating
projections x↦P1(P2(x)), fails exactly the way you'd guess: it
converges to a pair of points, one in each set, locally as close as possible
and globally wrong. A local minimum, in projection clothing.
This two-sided view reached the list independently of Elser. As early as
2008, antminder proposed cutting the pieces into edge-triangles and searching
in the domain of colored diamonds
(message 6184), and JSA
immediately recognized it as the dual problem
(message 6185): Eternity II is
256 pieces to be arranged so that 480 edges match, or 480 colored edge
squares to be arranged so that they generate the correct 256 pieces. Solving
means making both descriptions true at once.
Elser's answer to the local-minimum trap is not to alternate projections but
to iterate a difference map. In the published form, with the parameter set
to β=1, one step is
x↦D(x)=x+P1(2P2(x)−x)−P2(x),
and the general-β family interpolates around this using inner "estimate"
points fi(x) built from the projections
(PNAS 2007). Three properties do
all the work:
- Fixed point = solution. If D(x∗)=x∗, then
P1(2P2(x∗)−x∗)=P2(x∗): the same point lies in both
sets. You read the solution off as P2(x∗), not as x∗ itself:
the iterate is a searcher, not a board. Termination is detected when the
displacement Δ=∥D(x)−x∥ falls below a threshold, and
the candidate is then verified exactly.
- No cost function. The map does not descend anything. That sounds like
a defect and is the point: a hill-climber sticks wherever its score
function has a local optimum, but the difference map has no score to
flatter it into staying. Away from fixed points it keeps moving, in
practice chaotically, so near-miss configurations that trap
local search are places it
visits and leaves. This is the "tunneling" the physicists prized.
- The iterate lives outside both sets. x need not satisfy either
constraint while searching. Like the fractional boards of the
LP relaxation, it explores a
superposition of boards. Unlike the LP, it has no objective to optimize
and no optimum to plateau at: its only resting places are solutions.
For β=1 the difference map coincides with the Douglas–Rachford
iteration, a projection method convex analysts have studied since the
1950s; convergence is provable when both sets are convex, and entirely
unguaranteed here, where C1 is a scatter of permutation points. The
Eternity II list only learned the family name in 2025, when Wyatt Carpenter
found Wikipedia crediting "the Douglas–Rachford algorithm" for TetraVex
solving and flagged it as a possibly promising avenue no one had raised
(message 11592); JSA closed
the loop, pointing back to the Elser thread of 2014–2016 and framing
Douglas–Rachford as the f(x)+g(x) splitting view of the same attack
(message 11594). The
optimization literature had indeed adopted the method for exactly this family
of puzzles
(Aragón Artacho, Borwein & Tam).
The two-set picture above needed a global projection (P1 is one big
matching). Gravel and Elser's follow-up,
Divide and concur
(open preprint), makes the construction
mechanical for any CSP. Give every constraint its own private replica
of each variable it touches:
- The divide projection satisfies each constraint independently on its
own replicas. Every constraint is now a tiny local problem (for Eternity
II: one edge, two piece-sides), trivially projectable.
- The concur projection forces all replicas of the same variable to
agree, by replacing each with their average, the cheapest projection
imaginable.
Run the difference map between divide and concur and you get a general
CSP solver whose per-iteration work is entirely local, with the averaging
step playing the role of communication. Gravel and Elser benchmarked it on
3-SAT, where it scaled comparably to WalkSAT, and used it to improve known
sphere packings. When the method reached the list, Dima immediately recognized the
structure from his own field: the replica-averaging scheme is a close
relative of belief propagation on the constraint graph, a connection the
authors draw themselves
(message 9348). For readers of
this wiki the family resemblance goes further: a message-passing search over
a graph that is locally tree-like nowhere (every 2×2 block is a cycle) is
exactly the setting where the related methods on the
dead ends page (survey propagation,
belief-propagation move ordering) flattened out and died.
The record, in full, because it is short.
- 2008, a dismissal in passing. The first mention of the method on the
list is Don Milne listing "difference map" among the optimization
techniques he judged unable to solve complex CSPs: they shine only when
solutions are dense, and Eternity II was
designed to have almost exactly one
(message 5479).
- 2014, the real introduction. A member's diagram of the puzzle's edge
lattice prompted JSA to state the dual problem and introduce Elser's work:
the difference map "moves back and forth between the two dual problems"
(message 9347), with
pointers to the PNAS paper and the divide-and-concur Physical Review paper
(message 9350). Elser's own
ICCOPT-MOPTA 2007 slides, which mention Eternity II in their final three
slides, were uploaded to the group's files
(message 9349).
- 2014, the one empirical test. Dima read the PNAS paper, liked it, and
checked it: he wrote a simple hill-climber for the paper's own graph
3-coloring benchmark and solved the N=16 instance in seconds, where the
paper's Table 2 has the difference map taking on the order of ten minutes.
"So this makes me wonder whether it is really all that it is hyped up to
be" (message 9351), while
still calling the two-sided tiles-versus-edges idea worth exploring for
E2.
- 2015, code and a promise. Someone obtained source code from Elser
himself, with a worked 5×5 edge-matching example, and shared it in the
group files (message 9362).
In the "New Approach?" thread that summer, JSA recapped the method's
standing: it "has solved small model version[s] of Eternity II," and had it
solved the big one "we would have heard about it"
(message 9442). Juraj
Pivovarov asked for a concrete difference map written down for Eternity II
(message 9443); JSA promised
a short write-up (message 9446)
that never appears in the archive. In the same thread Dima sketched the
primal–dual transfer explicitly (carry an edge-coloring solution to the
nearest piece assignment with the Hungarian algorithm and back) and
reported his own dual-side annealer stalling at 48/49 correct tiles on
Brendan Owen's 7×7
(message 9445), while Mike
Pringle recalled the list's home-grown cousin, the SRD edge-swap approach
of 2007: capable of 8×8, never 10×10
(message 9447).
- 2025, a name and a shrug. The Douglas–Rachford thread
(message 11592) drew one
quick evaluation, useful for theory, "but not much else"
(message 11593), and JSA's
reflection that on a puzzle built to be optimally difficult, he'd expect
the iteration count to be "on the order of" a backtracker's node count
anyway (message 11594).
That is the whole record: no member ever reported running the difference map
or divide-and-concur on the full 480-edge puzzle, or even on the 10×10
benchmark ladder. The peer-reviewed literature is similar in shape. Elser's
group published the method's successes on coloring, SAT, packing and folding,
and kept Eternity II to talks, cover art and example code. Nobody has
published a difference-map result on the full puzzle, positive or negative.
Why so little uptake?
Partly timing (the 2014 thread landed in the archive's quietest years)
and partly Dima's data point, which took the shine off fast. But the deeper
reason is the one Don Milne gave in 2008 and JSA repeated in 2025:
stochastic continuous methods pay off when solutions are plentiful relative
to the space, and Eternity II sits at the
designed hardness peak where they are not.
The method is famous because edge matching illustrates it beautifully,
not because it solves edge matching at scale.
The gap between "discussed" and "measured" is narrow enough that one person
could close it. A modern attempt would:
- Fix the embedding. Per-cell one-hot vectors over 1,024 piece-rotations
(the two-set version), or divide-and-concur replicas per edge constraint.
This is the step Juraj asked for in 2015 and nobody wrote down for E2;
Elser's shared 5x5 code (message 9362)
is the natural starting template.
- Implement the two projections. Edge-agreement is a local average;
piece-validity is one Hungarian solve per iteration (256 cells x 1,024
candidates), or pure replica-averaging in the divide-and-concur form.
- Climb the benchmark ladder. Run against
Brendan Owen's puzzle suite, the same 7×7
where Dima's dual annealer got 48/49, then 8×8, 9×9, 10×10, with a plain
hill-climber and a restart-driven backtracker as controls, plotting
iterations-to-solution against instance hardness.
- Report the curve, not the anecdote. The interesting output is the
scaling exponent: Elser's own papers report iteration counts growing
steeply with instance hardness, and the open question JSA posed in 2014,
how does it scale to E2-class instances?
(message 9350), has never
been answered with a graph.
The realistic best case is not a solved puzzle. It is a characterized method:
either a scaling curve that crosses the backtracker's somewhere interesting,
which would be news, or a clean negative entry for the
dead ends ledger, which is also progress.
- Per iteration: two projections. The edge projection is linear in the
number of edges. The piece projection is the expensive one: an exact
assignment solve is O(n3) in the Hungarian algorithm, and at n=256
cells that is millions of operations per iteration, against a tuned
backtracker's tens of millions of placements per
second. Divide-and-concur
trades this for pure local averaging, at the price of a much larger
replicated state.
- No convergence guarantee. Douglas–Rachford convergence theory is
convex; both Eternity II sets are combinatorial scatter. On feasible
instances the map usually finds fixed points in practice (that is the
papers' empirical content), but nothing bounds the iteration count, and on
this puzzle JSA's expectation is that it matches backtracking's node count
(message 11594).
- Fixed point = solution, and nothing less. The method has no useful
partial output: until Δ→0 you have a wandering point in a
fractional space, not a scored board. There is no 460-edge consolation
prize along the way, which matters on the only puzzle where the
record ladder is denominated in partial scores.
- The scoreboard. One community test, lost to a hill-climber on
the method's own benchmark (message 9351);
small edge-matching models solved in Elser's materials; the full puzzle
untouched. Elegant, principled, unproven here, and, unusually for this
wiki, still unmeasured rather than measured-and-buried.