# The rigidity wall

> Every record board we have is frozen in place. You cannot nudge your way from a great board to a perfect one, and we can prove it.

- Canonical page (with interactive figures/demos): https://eternity2.dev/research/why/rigidity-wall/
- Updated: 2026-07-10
- Topics: structure, local-search, exact-methods
- Source: Local rigidity theorem (project paper, 2026-05-16): ≥13 MIP proofs of halo-optimality across 3–4 basins, out to halo-4 — https://github.com/raphael-anjou/eternity2/tree/main/research
- Source: Land & Doig 1960, branch and bound, the exact method behind every region solve — https://doi.org/10.2307/1910129
- Source: benj39100: GPU annealing on the strict-5-clue board hits the same frozen core; best score grows with distance from the incumbent (groups.io msg 11902) — https://groups.io/g/eternity2/message/11902
- Source: William Millilaw's independent halo SAT-residual and replica freeze tests, reproduced here on the public record boards (all UNSAT out to a two-cell halo) — https://github.com/raphael-anjou/eternity2/tree/main/research/topics/rigidity-sat-halo

---
Here is the intuition almost everyone starts with: get close, then tidy up
the last few mismatches. Swap a couple of pieces, rotate a few, and surely
the score creeps up to 480.

It doesn't. On every top board we have tested, the last mismatches are
locked. Move anything nearby and the score stays the same or drops. The good
boards aren't almost-solutions waiting for a polish; they're isolated points
with nowhere better to go next door.

## Watch the region grow
> **[Interactive: RigidityHalo]** Rendered on the canonical page (link above); not shown in this markdown export.
## Try to beat it yourself

A real perfect small board. Swap any two pieces, or let the engine try every
swap. Nothing beats it; that's rigidity, live.

> **[Figure]** Interactive: swap pieces and watch the score refuse to rise — interactive: RigidityLab. Rendered on the canonical page (link above); not shown in this markdown export.

## How this is known

The result does not rest on trying a lot of swaps and giving up. It comes from
an exact question put to an integer-programming solver: take a region of the
board, free every piece inside it, and find the single best way to fill it back
in. The solver searches that whole local space exactly, not by sampling.

The answer keeps coming back the same: the best arrangement is the one
already there. We proved it for region after region, across three different
record boards, and out to a radius of four cells, which is a block of dozens
of cells at once. Every time, no improvement exists.

## Method: the MIP proof

The exact question, stated precisely. Around each defect cell take the
*halo-$r$* region: every cell within $r$ steps. Free all pieces inside it,
keep the rest of the board fixed as a boundary, and solve an integer program
for the best legal refill. Binary variables $x_{c,p,\theta} \in \{0,1\}$ place
piece $p$ at rotation $\theta$ in cell $c$; one-piece-per-cell and
one-cell-per-piece constraints make it an assignment problem; the objective
maximizes matched edges, counting the fixed boundary. A 64-cell region is about
18,700 binary variables. Branch and bound then either finds a strictly better
refill or proves, with a dual bound, that none exists.

It never finds one. The proofs, region by region:

| Region | Board | Cells | Solver time | Result |
|---|---|---:|---:|---|
| halo-2, per-component (×8) | 3 basins (469, 459, 458) | 2–32 | seconds each | all Δ = +0, **proven** |
| halo-1 joint | McGavin 469 | 37 | 895 s | Δ = +0, **proven** |
| halo-1 joint | Local 459 | 59 | 1800 s | Δ = +0, **proven** |
| halo-3, per-component | McGavin 469 | 42 + 47 | 929 s | Δ = +0, **proven** |
| halo-4, component 0 | McGavin 469 | 57 | 1200 s | Δ = +0, **proven** |

Across four basins and ≥13 regions the answer is invariant: the incumbent
board is locally MIP-optimal, out to halo-4 for McGavin's 469. The one region
left with a gap, the top-four rows, 64 cells, still gives a *sound* result:
a dual bound of 123 against the incumbent's 116, so even the unclosed case
cannot exceed the wall by much (it implies a board-wide bound of ≤ 476).

The badge says *proven* rather than *conjectured* for the regions actually
closed; the general statement over *all* boards remains a conjecture, supported
by every region tested to date.

## Why it matters

This reframes the whole gap to 480. The distance from the best known board to
a solution is not a pile of small fixes waiting to be found. If it were, this
kind of local search would have found them. The barrier is that the good
boards sit at the bottom of their own little valleys, and the valley walls
are exact, not approximate.

It also tells you what won't work. Polishing, hill-climbing, and most
local-repair heuristics are trying to walk uphill from a frozen point. There
is no uphill. Reaching a solution needs a move that rearranges a large region
all at once, or a different starting point entirely, not a better polish.

## Someone hit the same wall from the annealing side

The MIP proof approaches the wall analytically. In June 2026 another researcher
ran headlong into it empirically. Working the strict five-clue board with a GPU
simulated-annealing solver (4096 parallel replicas), benj39100 reported two
things that read like a restatement of this page. First, the best score a run
could reach *increased with distance from the current best board*: to climb
from 429 toward 432 the winning perturbations had to migrate steadily further
out, because near the incumbent there was no improving move to find. Second,
across all their best boards the same roughly forty-two broken edges formed a
frozen "hard core" that local search never touched, so they had to add an
explicit term that *rewarded* prying that core open. A locally frozen incumbent
with no nearby gradient, and a small locked set of defects nothing local will
move: that is the rigidity wall, seen from a completely different method.

## And again, from a SAT solver

A third researcher reached the same conclusion with a third tool. William
Millilaw, working the ceiling independently, ran two tests. The first was a
freeze test: perturb the root of a top board, re-optimize, and see which cells
come back. On his best boards 93 to 100 percent of the cells returned to exactly
where they were, a frozen core the search could not move. The second was a
decision question for a SAT solver. Free the cells around the mismatches, demand
that every freed edge match, and ask whether any arrangement of those pieces
satisfies it. His solver answered UNSAT.

We [reproduced that SAT test](https://github.com/raphael-anjou/eternity2/tree/main/research/topics/rigidity-sat-halo)
on the public record boards, with our own encoder and a positive control to make
sure a matched region comes back satisfiable. Every record board we tried, from
Verhaard's 467 up to Blackwood's 470, is UNSAT out to a two-cell halo: no local
rearrangement of a record board's own pieces closes a single mismatch. Integer
programming optimizes and bounds; annealing runs into the wall by hand; SAT
decides and returns a refutation. Three methods, one answer.

His earlier snake-and-local-search work put a number on why. The largest patch
any of his repair operators could rewrite in one move was about 48 cells, while
two of the known good boards, both near the ceiling, differ across roughly 225
cells. A move that can only touch 48 cells cannot cross a 225-cell gap, so no
sequence of them reaches a different basin. He looked for a chain of small
improving moves that would tunnel out and found none: zero improvements across
twenty-eight million four- and five-move combinations at the plateau. That is
the same wall stated as a budget. Local repair rewrites too little at once to
leave the valley, which is why escaping needs a move that rearranges a large
region all at once, exactly as the proof section above concludes.

> **The next piece of the picture**
>
> If you can't improve a board locally, maybe you can hop from one good board to another. That fails too, for a related reason: [see why basin-hopping is impossible](/research/why/sigma-cycles).

*The proofs use integer programming on regions of each board; they run for
minutes per region on a solver, so they aren't reproduced live here. The
boards themselves are bundled and checkable in the viewer.*

## Related

- [Why basin-hopping looks impossible](https://eternity2.dev/research/why/sigma-cycles) — If you can't improve a great board by polishing it, maybe you can jump to a different great board. On every record pair tested, you can't, and the structural reason why is worth seeing.
- [Which wall stops which method](https://eternity2.dev/research/why/walls-and-methods) — The research section has two halves: the structural walls that make Eternity II hard, and the algorithms built to climb them. This page is the bridge: each method lined up against the wall it actually attacks, and the score where that wall stopped it.
- [Why a faster computer doesn't help](https://eternity2.dev/research/why/prune-vs-speed) — The single most important idea in hard combinatorial search: shrinking the space you search beats searching it faster, by an exponential margin. Eternity II is engineered so you can barely shrink it at all.
- [PALIMPSEST](https://eternity2.dev/research/lab/experiments/raphael-anjou/learning/palimpsest) — Read every strong board to find the habits that quietly hold a board back, then break them. This experiment produced the project's best board: 463 of 480.
- [MIDDEN](https://eternity2.dev/research/lab/experiments/raphael-anjou/pipelines/midden) — Decide in advance not when a board may break, but where: confine every mismatch to a chosen shape of cells, and search for the best shape.
- [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.