# Iterated maps and divide-and-concur

> The physicist's attack on constraint satisfaction: split the puzzle into two constraint sets that are each easy to project onto, then iterate a map whose fixed points are solutions. Veit Elser's method made the cover of PNAS, yet on the Eternity II list it remains a road admired, tested once, and never marched down.

- Canonical page (with interactive figures/demos): https://eternity2.dev/research/build/exact/iterated-maps/
- Updated: 2026-07-02
- Topics: exact-methods, learning
- Source: Elser, Rankenburg & Thibault, Searching with iterated maps (PNAS 104:418, 2007) — https://doi.org/10.1073/pnas.0606359104
- Source: Gravel & Elser, Divide and concur: a general approach to constraint satisfaction (Phys. Rev. E 78, 036706, 2008) — https://doi.org/10.1103/PhysRevE.78.036706
- Source: Gravel & Elser, Divide and concur: open preprint (arXiv:0801.0222) — https://arxiv.org/abs/0801.0222
- Source: Aragón Artacho, Borwein & Tam, Recent results on Douglas–Rachford methods for combinatorial optimization problems (arXiv:1305.2657) — https://arxiv.org/abs/1305.2657
- Source: JSA formalizes the dual problem and introduces Elser's work to the list (groups.io message 9347) — https://groups.io/g/eternity2/message/9347
- Source: JSA on the divide-and-concur papers and the open scaling question (groups.io message 9350) — https://groups.io/g/eternity2/message/9350
- Source: Dima's test: a simple hill-climber beats the difference map on the paper's own benchmark (groups.io message 9351) — https://groups.io/g/eternity2/message/9351
- Source: Elser's ICCOPT-MOPTA 2007 slides uploaded to the group files, "Eternity II mentioned in last 3 slides" (groups.io message 9349) — https://groups.io/g/eternity2/message/9349
- Source: Source code from Veit Elser, with a 5×5 example puzzle, shared in the group files (groups.io message 9362) — https://groups.io/g/eternity2/message/9362
- Source: JSA's 2015 recap: small model versions solved, the big one not (groups.io message 9442) — https://groups.io/g/eternity2/message/9442
- Source: Dima's primal–dual transfer sketch with Hungarian matching (groups.io message 9445) — https://groups.io/g/eternity2/message/9445
- Source: The SRD edge-swap precedent: solved 8×8, never made 10×10 (groups.io message 9447) — https://groups.io/g/eternity2/message/9447
- Source: Douglas–Rachford named on the list, via Wikipedia's TetraVex note (groups.io message 11592) — https://groups.io/g/eternity2/message/11592
- Source: JSA connects Douglas–Rachford back to the Elser lineage (groups.io message 11594) — https://groups.io/g/eternity2/message/11594

---
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](https://doi.org/10.1073/pnas.0606359104)).
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](https://groups.io/g/eternity2/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.

## Two easy sets, one hard intersection

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:

- $C_1$, **pieces used once**: every cell holds exactly one piece-rotation,
  and every piece is used exactly once. Edge colors are ignored.
- $C_2$, **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 $C_1 \cap C_2$. 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:

- $P_1(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](/research/build/local-search/local-search-alns).
- $P_2(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 \mapsto P_1(P_2(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](https://groups.io/g/eternity2/message/6184)), and JSA
immediately recognized it as the *dual problem*
([message 6185](https://groups.io/g/eternity2/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.

## The difference map

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 $\beta = 1$, one step is

$$
x \;\mapsto\; D(x) \;=\; x \;+\; P_1\!\big(2P_2(x) - x\big) \;-\; P_2(x),
$$

and the general-$\beta$ family interpolates around this using inner "estimate"
points $f_i(x)$ built from the projections
([PNAS 2007](https://doi.org/10.1073/pnas.0606359104)). Three properties do
all the work:

1. **Fixed point = solution.** If $D(x^\ast) = x^\ast$, then
   $P_1(2P_2(x^\ast) - x^\ast) = P_2(x^\ast)$: the same point lies in both
   sets. You read the solution off as $P_2(x^\ast)$, not as $x^\ast$ itself:
   the iterate is a *searcher*, not a board. Termination is detected when the
   displacement $\Delta = \lVert D(x) - x \rVert$ falls below a threshold, and
   the candidate is then verified exactly.
2. **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](/research/build/local-search/local-search-alns) are places it
   visits and leaves. This is the "tunneling" the physicists prized.
3. **The iterate lives outside both sets.** $x$ need not satisfy either
   constraint while searching. Like the fractional boards of the
   [LP relaxation](/research/build/exact/lp-relaxations), 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 $\beta = 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 $C_1$ 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](https://groups.io/g/eternity2/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](https://groups.io/g/eternity2/message/11594)). The
optimization literature had indeed adopted the method for exactly this family
of puzzles
([Aragón Artacho, Borwein & Tam](https://arxiv.org/abs/1305.2657)).

## Divide and concur: the replica trick

The two-set picture above needed a global projection ($P_1$ is one big
matching). Gravel and Elser's follow-up,
[*Divide and concur*](https://doi.org/10.1103/PhysRevE.78.036706)
([open preprint](https://arxiv.org/abs/0801.0222)), 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](https://groups.io/g/eternity2/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](/research/build/dead-ends) page (survey propagation,
belief-propagation move ordering) flattened out and died.

## What the archive actually shows

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](/research/why/complex-theory)
  ([message 5479](https://groups.io/g/eternity2/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](https://groups.io/g/eternity2/message/9347)), with
  pointers to the PNAS paper and the divide-and-concur Physical Review paper
  ([message 9350](https://groups.io/g/eternity2/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](https://groups.io/g/eternity2/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](https://groups.io/g/eternity2/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](https://groups.io/g/eternity2/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](https://groups.io/g/eternity2/message/9442)). Juraj
  Pivovarov asked for a concrete difference map written down for Eternity II
  ([message 9443](https://groups.io/g/eternity2/message/9443)); JSA promised
  a short write-up ([message 9446](https://groups.io/g/eternity2/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](https://groups.io/g/eternity2/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](https://groups.io/g/eternity2/message/9447)).
- **2025, a name and a shrug.** The Douglas–Rachford thread
  ([message 11592](https://groups.io/g/eternity2/message/11592)) drew one
  quick evaluation, useful for theory, "but not much else"
  ([message 11593](https://groups.io/g/eternity2/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](https://groups.io/g/eternity2/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](/research/why/complex-theory) where they are not. The method is famous *because* edge matching illustrates it beautifully, not because it solves edge matching at scale.

## What an attempt today would look like

The gap between "discussed" and "measured" is narrow enough that one person
could close it. A modern attempt would:

1. **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](https://groups.io/g/eternity2/message/9362))
   is the natural starting template.
2. **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.
3. **Climb the benchmark ladder.** Run against
   [Brendan Owen's puzzle suite](/research/build/benchmarks), 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.
4. **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](https://groups.io/g/eternity2/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](/research/build/dead-ends) ledger, which is also progress.

## What it costs

- **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(n^3)$ 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](/research/build/faster/solver-engineering). 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](https://groups.io/g/eternity2/message/11594)).
- **Fixed point = solution, and nothing less.** The method has no useful
  partial output: until $\Delta \to 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](/research/records) is denominated in partial scores.
- **The scoreboard.** One community test, lost to a hill-climber on
  the method's own benchmark ([message 9351](https://groups.io/g/eternity2/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.

## Related

- [Dead ends](https://eternity2.dev/research/build/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.
- [LP and ILP relaxations: half a piece everywhere](https://eternity2.dev/research/build/exact/lp-relaxations) — Write Eternity II as an integer program, drop the integrality, and a linear solver reaches zero error in seconds, with 30% of one piece and 20% of another sharing a corner. Eighteen years of community campaigns measured where the fractional comfort ends: a plateau at 420–440 edges the moment the pieces must be whole, an ILP wall at 8×8, and an academic best of 461-in-an-hour. What the optimizer's road teaches, and where LP still earns its keep.
- [SAT and CSP encodings](https://eternity2.dev/research/build/exact/sat-csp-encodings) — Write the puzzle as clauses and hand it to an industrial solver: the obvious move, tried since 2008. Why complete solvers stall on the full board, and where their verdicts still earn their keep as impossibility proofs.