Local search and ALNS · Eternity II

Once you hold a strong board, single-piece moves stop paying almost immediately. Large-neighborhood search takes the opposite bet: rip out a whole region (dozens of cells) and rebuild it with something smarter than the greedy pass that put it there. The idea is Paul Shaw's (CP 1998); the adaptive version, ALNS, is due to Ropke and Pisinger (Transportation Science 2006), who added a portfolio of destroy and repair operators and a learning rule that steers effort toward the operators that have recently succeeded.

The loop#

One ALNS iteration on a board:

Destroy. Pick a destroy operator, unplace the $k$ cells it selects.
Repair. Refill the hole (greedy fill, constraint propagation, or an exact solve of the small subproblem).
Accept. Keep the new board if it scores better, or sometimes anyway under a simulated-annealing rule.
Adapt. Reweight the operators by their recent success, so the roulette wheel favours what has been working.

Eternity II is unusually friendly to step 1, because a partial board tells you exactly where it hurts: the mismatched edges.

Watch it run#

Reading the loop is one thing; watching it learn is another. Below, a real solved 8×8 from the engine has been deliberately damaged, and the full ALNS loop runs on it in slow motion: destroy, greedy refill piece by piece, accept or revert, reweight. Force an operator by hand and watch its weight bar respond; or just let the roulette drift toward whatever has been paying.

Interactive: the destroy-and-repair loopExplore →

Loading the engine…

Step by step#

One iteration, exactly as the lab executes it:

Draw an operator. Roulette-wheel selection: operator $o$ is picked with probability $w_o / \sum_j w_j$ . All weights start equal; the wheel is uniform until results arrive.
Destroy. The operator returns $k$ cells and their pieces come off the board. Picking random cells or a fixed shape is $O(k)$ ; conflict-guided operators (worst row, most-conflicted cells) also need the mismatch map, which costs a linear scan unless the engine maintains it incrementally. Ours does, precisely so that destroy stays $O(k)$ .
Repair, greedily. Until the hole is full: take the empty cell with the most placed neighbours (most-constrained first), try every lifted piece in all four rotations, keep the placement that matches the most seams. Each of the $k$ placements scans the remaining candidates, so the pass costs $O(k \cdot |C|)$ where $|C|$ is the candidate pool (free pieces × 4 rotations).
Accept or revert. Score the rebuilt region; only the seams touching the $k$ cells changed, so re-evaluation is $O(k)$ . Keep the board if $\Delta \geq 0$ , else keep it anyway with probability $e^{\Delta/T}$ ; on rejection, restore the snapshot.
Adapt. Update the winner's weight, $w_o \leftarrow \lambda\, w_o + (1 - \lambda)\, \psi$ , where the reward $\psi$ is tiered: new global best > improvement > accepted sideways move > rejection. That exponential smoothing is the whole "adaptive" in ALNS. Ropke and Pisinger's original does the same bookkeeping over segments of a few hundred iterations.

What it costs#

Per iteration, with $k$ destroyed cells:

\underbrace{O(k)}_{\text{destroy}} \;+\; \underbrace{O(k \cdot |C|)}_{\text{greedy repair}} \;+\; \underbrace{O(k)}_{\text{evaluate}} \;+\; \underbrace{O(|\mathcal{O}|)}_{\text{adapt}}

Three refinements worth knowing:

Optimal refill is an assignment problem (sometimes). When the freed cells are pairwise non-adjacent, each hole's cost depends only on its fixed neighbours, so the refill is exactly a $k \times k$ assignment problem: the Hungarian algorithm solves it optimally in $O(k^3)$ . That is Schaus's Eternity II neighborhood. The moment two holes touch, their choices couple, and optimal repair becomes a small CP/exact search, worst-case exponential in $k$ , which is why large destroys stop paying.
Anytime, and nothing more. ALNS improves a feasible answer and can be stopped whenever; the best board so far is the output. It carries no completeness or optimality guarantee: it can never certify that no better board exists. On this puzzle that certificate has to come from elsewhere (the SAT oracle behind the rigidity wall).
At Eternity II scale the loop is cheap; the escape is not. With $k = 20$ – $80$ of 256 cells and a few hundred candidates per hole, an iteration costs microseconds to milliseconds, and improvement curves flatten within dozens of iterations. The binding cost is therefore not the arithmetic but the probability that a $k$ -cell neighbourhood contains the one interlocking σ-cycle that leads upward, and that probability is what collapses near the top.

An operator portfolio for boards#

The destroy operators this project shipped are mostly geometry- and conflict-aware: random cells as a baseline, cells incident to mismatched edges, the top- $k$ most conflicted cells, the worst row or band of rows, a connected component of the mismatch graph (optionally with a one-cell halo around it), rectangles, and concentric rings. Two findings from tuning the portfolio, both measured on this project's engine and not independently replicated:

Curation beats coverage. A curated set of five operators outperformed the full set of eleven; spreading the adaptive weights across too many operators dilutes the learning signal.
Temperature is not the lever. Across a tenfold range of acceptance temperatures the end scores were identical, because near the top the landscape is dominated by equal-score plateaus where essentially every move is accepted at any temperature.

That destroy-and-repair suits this puzzle is an old observation: Schaus and Deville hybridized constraint programming with large-neighborhood search on Eternity II back in 2008, using CP as the repair step, the same division of labour that works here.

What it reliably buys#

Final polish. On this project's engine, ALNS is the step that turns constructive output into record-class boards: beam builds that land in the mid-450s consistently gain several edges under a refinement pass, and the project's strongest boards all carry an ALNS lift as their last stage. On smaller generated puzzles the effect is dramatic and repeatable: destroy-and-repair closes most of the distance between a random placement and the best reachable score, across a wide range of puzzle tightness, before saturating on the very hardest instances. (All of this is measured here, hedged accordingly.)

Just as characteristic: the gains arrive early. Improvement curves flatten within the first few dozen iterations, and letting a run go ten times longer reproduces the same final score. When ALNS stops, it has stopped.

The wall it hits#

Why it stops is the interesting part, and this site has two full pages on it. On every top board, the remaining mismatches are provably locked: freeing a generous neighbourhood around them and searching it exhaustively finds nothing better; that is the rigidity wall. And moving from one top board to a better one requires relocating a large set of pieces in one interlocking loop, where every partial application of the loop scores worse than doing nothing: the σ-cycle structure.

ALNS is exactly the wrong shape for that. A destroy neighbourhood of 20–80 cells almost never covers the one cycle that matters, and when the destruction is large enough to cover it, the repair step faces a subproblem nearly as hard as the puzzle itself and gives back less than was torn down. Destroy-and-repair explores a basin superbly and escapes it essentially never. The summary this project's measurements support: ALNS is the best last mile we have, and it is only a last mile.

The loop#

Watch it run#

Step by step#

What it costs#

An operator portfolio for boards#

What it reliably buys#

The wall it hits#

Keep exploring

The loop#

Watch it run#

Step by step#

What it costs#

An operator portfolio for boards#

What it reliably buys#

The wall it hits#