The sibling of the DFS study, for the other way people attack Eternity II: destroy part of a board, rebuild it, keep the change if it helps. One question, asked carefully. What does each decision in that loop buy: which region to destroy, how to rebuild it, when to keep a move, when to restart, and what board to start from?
There are two ways people actually attack Eternity II. One is to build a board
cell by cell and backtrack when it fails; the DFS study
takes that apart. The other is to hold a whole board and repair it: rip out a
region, rebuild it, keep the change if it helped, and repeat. Repair is the last
stage of the construct-then-refine pipelines behind this project's own
record-approaching boards, and it is the method the literature reaches for once a
board is too good for a single-piece move to improve. This study takes the repair
loop apart the same way its sibling took backtracking apart: one decision at a
time, on the same ten corner-pinned variants, single core, sixty seconds a run.
The maximum score is 480 matched edges.
The loop itself is short. One iteration, walked through below.
Loading…
The point is not to win. Most variants finish in the 360s and 370s, and the one that
does best (446) does so by starting from a strong backtracked board rather than a
constructed one, which is itself the study's central lesson. Repairing a plain
greedy board on one core for a minute is a small thing next to the pipelines the
records use; what the study measures is what each decision in the
loop is worth by changing one at a time and measuring the result with the same
canonical scorer the DFS study and the rest of the site use.
Five families, laid out so that neighbours differ by a single decision, all
branching off one plain anchor loop (greedy start, destroy the mismatched cells,
greedy refill, keep the result unless it loses score, never restart). Starting
board changes where the loop begins. Destroy operator changes which cells
each iteration lifts. Repair changes how the hole is rebuilt. Acceptance
changes when a non-improving move is kept. Restart changes what happens once
the loop stalls.
The leaderboard — mean final score by variant
Mean matched-edge score of the board each variant finished with, over ten corner-pinned variants of the official puzzle, single core, 60 s per run. Colour marks the family; the family is named on every bar, so colour is never the only signal.
The same runs, but showing only the lift: the mean gain each variant made over the board it started from. This isolates the repair loop's own contribution from the construction it began with — a variant that starts high can add little and still finish high.
Drawing…
mean lift (matched edges)
Where improvement stops
For four representative variants, the best score so far against the iteration count (sampled every 200 iterations, medians over the ten instances). The point of the study in one picture: on a strong starting board the conflict-driven loop flattens within a few thousand iterations and the remaining hundreds of thousands move nothing, while blind random destroy keeps finding gains far longer.
Every variant is the same destroy-and-repair loop declared as one change over its parent. This table is generated from the engine registry, so it always matches the code that ran. `last best` is the mean iteration the global best last improved; compare it to `iters` to read how early each run stalled.
variant
family
the one change it adds over its parent
mean
lift
last best
iters
accept
START-RANDOM
starting board
start from a random board instead of a greedy construction
325.6
+307.6
2K
17.3M
0.147
START-RARE
starting board
start from a rarest-color-first greedy construction (Selby/Riordan rarity)
373.3
+15.6
1K
19.4M
0.136
START-DFS
starting board
start from a 20 s break-DFS board, then repair it (construct-then-refine)
446
+6.6
3K
12.7M
0.309
GREEDY-MISMATCH
destroy operator
the plain loop: greedy start, destroy mismatched cells, greedy refill, keep if not worse
365.5
+17.3
2K
21.0M
0.199
RANDOM-DESTROY
destroy operator
destroy random cells instead of mismatched ones (geometry-blind control)
402
+53.8
6.1M
16.7M
0.741
BAND-DESTROY
destroy operator
destroy the worst band of two rows instead of scattered mismatched cells
348.6
+0.4
0
5.4M
0
COMPONENT-DESTROY
destroy operator
destroy one connected mismatch component plus a one-cell halo
351.8
+3.6
66
4.8M
0.017
REPAIR-JITTER
repair
break greedy-refill score ties with a seeded coin (controlled exploration)
364.9
+16.7
455
18.7M
0.252
REPAIR-SMALL
repair
destroy at most six mismatched cells instead of twelve (small-hole baseline)
362.9
+14.7
3K
33.4M
0.651
REPAIR-EXACT
repair
rebuild the small hole exactly by bounded assignment instead of greedily
359.6
+11.4
620
5.0M
0.997
ACCEPT-STRICT
acceptance
keep only strict improvements (no sideways moves)
360.6
+12.4
13K
18.2M
0
ACCEPT-ANNEAL
acceptance
accept worsening moves under a cooling simulated-annealing temperature
376.6
+28.4
15K
22.7M
0.69
ACCEPT-LATE
acceptance
accept against the score 40 iterations ago (late-acceptance hill climbing)
369.4
+21.2
2K
20.8M
0.303
RESTART-KICK
restart
after 400 stalled iterations, randomly kick 24 cells to escape the basin
364.9
+16.7
524
15.3M
0.186
RESTART-REVERT
restart
on a stall, revert to the best board so far instead of kicking (softer perturbation)
Starting from a strong backtracked board wins the whole study. The variant
that spends its first twenty seconds running the DFS study's break-DFS, then
repairs the resulting low-440s board, finishes highest of all, at a mean of 446
(best 449). Repair adds only a handful of edges on top of that board, but the board it
starts from is a hundred points better than a greedy construction, and that
carries through. This is the construct-then-refine division of labour the records
use, reproduced end to end on one core in one minute.
Among the greedy-start variants, random destroy wins and targeting the breaks
backfires. A geometry-blind destroy that lifts twelve random cells finishes
at a mean of 402 (best 409) and keeps improving deep into the run. Every operator
that targets the broken cells finishes below it, and the more precisely it
fixates, the worse it does: the mismatched-cells anchor lands at 366, a larger
connected-component destroy at 350. On a mediocre board there is improvement
available everywhere, so exploring beats attacking where it already hurts. That
inverts on a near-record board, where the few remaining mismatches are the only
thing left to fix.
The starting board sets the floor. A greedy construction starts around 348;
a random one starts near 18, and although the loop lifts it a spectacular 308
points, it still finishes below where the greedy start began. Construction is
the lever, repair is the polish.
The acceptance rule is the other real lever.Simulated annealing, which
steps downhill occasionally to leave a plateau, is the strongest acceptance rule
by a clear margin (mean 377, best 394), well
ahead of a strict hill-climb (361). How much a non-improving move is allowed is
worth a sixteen-point swing on the same loop.
The clever refinements buy nothing here. A whole-band destroy is inert (zero
improvements on nine of ten instances). A bounded exact refill of a small hole
does not beat a plain greedy refill of the same hole, a clean negative result:
its locally-perfect rebuilds cost enough iterations that more, cheaper greedy
rebuilds reach just as far. Neither a random kick nor a revert-to-best on a stall
moves the score off the no-restart baseline.
Each of these has its own treatment: how the engine is built and what every
raised statistic means is on the method page,
and the destroy, repair, acceptance, restart and starting-board comparisons are
worked through on the findings page.
Every board is re-scored by the one canonical scorer, and no engine's
self-reported score is trusted. The loop maintains its score incrementally as it
places and lifts pieces, but the published number is always a fresh canonical
re-score of the output board. Throughput is reported in repair-iterations per
second and is never compared across families, because an iteration that runs
an exact refill is not the same unit of work as one that runs a greedy fill.
The axis to watch is the stall: the iteration at which the global best last
improved, against the total iterations run. When the first is a few thousand and
the second is hundreds of thousands, the run found its answer early and then
ground the same basin for the rest of the minute. That gap is the measured form
of a long-standing observation about this puzzle, that destroy-and-repair is a
superb basin-explorer and essentially never escapes the basin it lands in.
The whole apparatus (the engine, the ten variants, the committed per-run results
and the grid scripts) lives under the study's
backing directory,
and just experiments repair-study rebuilds the engine and reruns the whole
grid. The board, scorer and IO layer come from a
shared library
the DFS study uses too, so a repaired board and a backtracked one are scored by
exactly the same code.