Treat mismatches as energy and temperature as tolerance for making things worse. Annealing holds the puzzle's longest-standing record; parallel tempering crosses barriers annealing can't. Both stop at the same wall.
Simulated annealing reads a board as a physical system: unmatched edges are energy, moves that lower the energy are always accepted, and moves that raise it are accepted with probability . Run hot and the search wanders; cool it and the board settles into a low-energy arrangement, ideally a deep one, not merely the nearest one. The catch is the schedule: cool too fast and you freeze into a mediocre local optimum, cool slowly enough for a puzzle this size and you wait forever.
Parallel tempering (replica exchange) dissolves the schedule problem by running the whole ladder at once. The method comes from spin-glass physics: Swendsen and Wang's 1986 replica Monte Carlo paper is the precursor, replica exchange in its modern form is usually credited to Geyer (1991) and Hukushima and Nemoto (1996), and Earl and Deem's 2005 review is the standard modern survey. copies of the board run simulated annealing at fixed temperatures ; periodically, adjacent replicas propose to swap states, accepted with the Metropolis rule
with , and . Read it once with concrete signs: if replica is the colder one () and the hotter replica holds the lower energy (), the exponent is positive and the swap is accepted with certainty: the good state always gets handed down the ladder for free. Hot replicas roam across barriers; cold replicas exploit; the swaps shuttle promising configurations down the ladder to be refined. No single chain ever has to survive a cooling schedule.
The claim worth seeing is the comparison: the same cold chain, with and without a ladder above it. Below, four replicas explore a rugged synthetic landscape whose global minimum hides behind barriers; a grey ghost runs the identical cold dynamics alone. Watch the swap flashes (green for accepted) carry the right-hand basin down to the cold rung, while the ghost sits in the starting well forever. Then drag the spacing slider to both extremes and reproduce the two classic ladder failures.
A rugged energy landscape with a shallow basin on the left (where everything starts) and the global minimum on the right, behind barriers. Four replicas run Metropolis at geometrically spaced temperatures; adjacent pairs periodically propose to swap states. The grey ghost is the control: the same cold chain, alone. The cold replica escapes through the ladder — hot rungs cross the barriers, swaps hand the good states down. The ghost never leaves.
The landscape is synthetic, the mechanism is exact: Metropolis proposals within each rung, and the true replica-exchange rule between rungs. Drag the spacing to its extremes to reproduce the failure modes the page describes: too tight and every swap is accepted (adjacent rungs are redundant), too wide and none are (the ladder falls apart). Deterministic seed — Replay reruns the identical trajectory.
One round of parallel tempering, as the lab runs it:
This project's measurements (on our own engine; not independently replicated) give an unusually concrete reason. Between one strong board and a better one, the connecting move is a single interlocking relocation of dozens of pieces in which every strict subset of the move loses edges: the σ-cycle structure. One measured transition required a 76-cell move whose intermediate states sat about 21 edges below the start: at the acceptance is on the order of , hopeless. With the ladder's top temperature raised to roughly 30, the crossing actually happened, and produced what was then the project's best cold-start board. Temperature, used correctly, is a real lever against real barriers.
Ladder design is where practice bites. When we spaced the temperatures too closely, replica exchange accepted every swap. A 100% acceptance rate sounds healthy and means the opposite: adjacent replicas saw effectively the same landscape, and the ladder added nothing. Geometric spacing with a genuinely hot top rung, tuned so that swaps are frequent but not free, is the standard advice in Earl and Deem, and it matched what we observed.
Annealing has a distinguished history on this puzzle. The longest-standing record on the canonical piece set (Louis Verhaard's 467 of 480 in 2008, unbeaten until the Blackwood-era backtrackers of 2020) came from an annealing method, and an unusual one: as he described it on the community mailing list, he annealed the composition of a piece subset, swapping pieces in and out of a candidate group under a tilability score, rather than annealing positions on the board. The lesson generalizes: on Eternity II, the choice of what to anneal mattered more than the annealing itself.
From this project's measurements, hedged accordingly: parallel tempering is a better barrier-crosser than plain annealing, and on the mid-range of the climb that difference is real and bankable. Near the top it dissolves. The plateaus up there are iso-score: ties everywhere, so acceptance no longer depends on temperature at all, and cranking the heat instead of climbing just randomizes the board, which then never finds its way back to record territory. Replicas launched from a top board plateau at the seed's score, every chain, every ladder we tried. Tempering moves you between hills; it does not repeal the rigidity wall.