There are three classic roads into Eternity II. Backtracking walks the tree.
SAT and CSP encodings hand the
logic to an industrial solver. The third road belongs to the optimizers:
write the puzzle as an integer program (variables, linear constraints, an
objective) and call CPLEX. It is the road every operations-research person
tries first, because it comes with a move the other two don't have:
relaxation. Delete the requirement that variables be whole numbers and the
NP-hard integer program becomes a linear program, solvable in polynomial
time. Solve the easy version, hope the answer is nearly integral, repair the
rest.
The community walked this road repeatedly between 2007 and 2025, with
solvers from glpsol to CPLEX to hand-rolled Newton–Raphson, and the
outcome was measured precisely enough to be worth a page: the relaxation
solves fast and reports a nearly perfect board, one made of fractions of
pieces. Force the pieces whole and the score collapses onto a plateau around
420–440 of 480 edges. The gap between the fractional optimum and the integer
one is not a technicality. It is the exact place where the puzzle lives.
One binary variable per placement, exactly as in the SAT encoding: let
xc,p,r∈{0,1} mean "piece p sits at cell c with rotation r".
Two families of assignment constraints and one per-seam accounting give the
whole model:
maxs.t.s∑ysp,r∑xc,p,r=1c,r∑xc,p,r=1ys≤k∑min(fs,k1,fs,k2)(matched seams)∀cell c∀piece p∀seam s
where fs,ki is the colour flow, the total weight of placements on
side i of seam s that show colour k across it,
fs,ki=∑(p,r)showingkxci,p,r. The min is
linearized with one auxiliary variable per seam and colour; for the
feasibility version you instead demand equal colour flow on both sides of
every seam. Community models land exactly where the arithmetic
says they should. Benjamin's 2009 LP had ~50,000 variables (placements
pruned to valid positions) and 7,952 equations: 256 per-cell, 256
per-piece, and 60×5+420×17=7,440 seam-colour balance
constraints (message 6910).
Vlasta's 2008 model carried 160,254 binaries
(message 5602); Jimmy
Timmermans's AMPL/CPLEX binary program, 272,704 variables and 24,566
equations (message 6728).
Günter Stertenbrink had already posed the equivalent graph form in 2007:
make the 262,144 placements vertices, join compatible pairs, and ask for a
clique of size 256 (message 627),
the framing the academic literature returned to a decade later.
Relaxation means one edit: replace xc,p,r∈{0,1} with
0≤xc,p,r≤1. That single change moves the problem across the
most important boundary in optimization. The integer program is NP-hard:
0–1 integer programming is one of Karp's original 21 complete problems. The
linear program is solvable in polynomial time (ellipsoid, interior-point),
and in practice simplex dispatches these model sizes almost instantly.
Benjamin measured it: his 50,000-variable system reached an error below
0.01 in about ten seconds
(message 6913).
Two properties make the relaxation genuinely useful, not just fast. Every
integer solution is also a fractional one, so the LP optimum is a bound:
no real board can ever score more than the relaxation says. And LP solvers
return certificates (dual values, infeasibility proofs) that integer-free
methods don't. The whole question is how much of that speed survives the
return trip to whole pieces.
Here is what the LP optimum actually looks like, in the words of the person
who computed it. Benjamin's system "converged relatively fast to zero
error" (a perfect board, as far as the constraints could see), and the
upper-left corner held "30% piece 1, 20% piece 2, 10% piece 3, 40% piece 4"
(message 6905). Andrew's
parallel experiment ran the same idea as an iterated ascent over a
256×256×4 grid of weights: "every piece is everywhere"
(message 6911).
The relaxation is happy because a superposition can hedge. A quarter of a
blue-edged piece plus three quarters of a pink-edged one presents a blend
that simultaneously part-matches a blue neighbour and a pink one, a match
no physical board can realize. Linear constraints can price how much of
each piece sits where; they cannot express "exactly one of these is real,"
because one-of is not a linear fact. It takes a quadratic constraint (or
an integrality one) to say it. Benjamin used
(∑vi)2−∑vi2=0, which forces all but one variable in a
group to zero (message 6913),
and the moment he added it, convergence died: the system "stalls at higher
values which resemble results like 420-440 / 480 correct edges"
(message 6905).
There is clean theory underneath the observation. The two assignment
families alone define a polytope whose vertices are all integral (that is
Birkhoff–von Neumann, and it is exactly why the Hungarian algorithm solves
pure assignment in polynomial time). Add the seam constraints and that
integrality property is destroyed: the polytope grows fractional vertices,
and the LP optimum sits on one of them. David Munjak's retrospective
compresses this into one line, listing among his tried approaches
"Assignment problem (integral solutions)" followed by "Assignment problem
with side constraints (not necessarily integral solutions)"
(message 8791). The side
constraints (the edges, the actual puzzle) are precisely what breaks the
guarantee. Eternity II is an easy assignment problem welded to a hard
coupling, and the relaxation quietly optimizes only the easy half.
The whole gap fits in two cells. Take two adjacent cells and two pieces,
one showing colour 1 on every side, one showing colour 2. Any whole-piece
arrangement scores 0: the seam always sees colour 1 against colour 2. The
LP scores exactly 1.0: put half of each piece in each cell, and the seam's
linearized match variables collect 0.5 of credit for colour 1 plus 0.5 for
colour 2, with the fractional optimum sitting precisely at the 50/50
point. We verified it both by hand and with an LP solver (the integer
program returns 0, the relaxation returns 1.0). It is Benjamin's
30%-piece-1 corner reduced to its minimal algebra, and it isolates the
mechanism: the seam variables actively reward cell-fractional
assignments, so the LP prefers superpositions.
The example also sharpens the Birkhoff–von Neumann story. At that
fractional optimum the assignment constraints are satisfied exactly;
nothing about the assignment polytope is strained. It is the min-of-sums
seam objective alone that pulls the optimum off the integral vertices. The
assignment half of the model was never the problem.
Every few years someone new drove the road, with better solvers and more
memory, and hit the same three walls: the full ILP is unsolvable past toy
sizes; the LP is solvable and fractional; rounding or constraining toward
integrality lands in the mid-400s. The campaigns, in order:
| Year | Who | Model | Where it stopped | Msg |
|---|
| 2007 | Günter Stertenbrink | Max-clique, 262,144 vertices | Framing only; never scaled | 166, 627 |
| 2007 | dmitri_ulitski | ILP (glpsol) on rotation sets | Solved in ~5 s per set; the subproblem is easy | 3320 |
| 2008 | Vlasta | ILP, 160,254 binaries | "Applicable only for 8x8 puzzles"; switched to SAT, reached 428 | 5602 |
| 2008–09 | Andrew (bozmo2004) | Continuous ascent, Newton–Raphson over ~250k weights | ~800,000 days projected with his VBA prototype | 5304, 6911 |
| 2009 | Benjamin (okifinoki) | LP, ~50,000 vars, 7,952 constraints | Zero error in ~10 s, fractional; forced integral: stalls at 420–440/480 | 6905, 6913 |
| 2009–10 | Jimmy Timmermans | Toric ideals; AMPL/CPLEX BIP, 272,704 then 153k vars | Singular's 32k-variable limit; a 12x12 "solved" at 5.3% infeasibility (converges, integrality doesn't) | 6716, 6728, 6745, 8077 |
| 2010 | Vlasta | MILP (164,256 booleans) converted to SAT | 8x8 in ~1 min; parity with backtrackers, no further | 7858 |
| 2008–10 | David Munjak | Side-constrained assignment, fractional values as probabilities | 200–224 pieces placed, then a detected dead end; never backtracked | 8791 |
| 2012 | Wauters group | Hyper-heuristic (peer-reviewed) | 461/480 in one hour (the academic line) | 9023 |
| 2012 | Tony Wauters | MILP for rotation sets | Milliseconds; again, the easy subproblem | 9071 |
| 2017 | Salassa, Vancroonenburg, Wauters et al. | MILP + Max-Clique formulations | "Computationally intractable for medium and large sized instances"; recycled as heuristic decompositions | 9683, arXiv |
| 2025 | Marcus Garvie | Modern ILP | 10x10 with 6 colours in ~19 min; full E2 out of reach | 11502 |
Three readings of the table. First, notice where ILP wins: rotation sets,
where you fix only each piece's orientation so the directional edge counts
balance, fell to glpsol in five seconds in 2007 and to CPLEX in milliseconds in
2012. When the integer structure is genuinely easy, the solver says so
immediately; the full puzzle's silence is a verdict, not a tooling problem.
Second, the plateau numbers agree across totally different machinery:
Benjamin's 420–440 by penalized LP, Munjak's 200–224 pieces placed
mismatch-free by iterated assignment, the Wauters group's 461 with an hour
of metaheuristic repair on top. Everything optimizer-shaped lands in the
same mid-400s band that plain
local search reaches without
any LP at all. Third, the 2017 paper, the strongest academic treatment,
with both a MILP and a Max-Clique formulation, concedes intractability in
its abstract and pivots to using the formulations inside heuristics. The
road's own builders posted the detour sign.
The bound side of the story has the same shape and lives on the
dead-ends ledger: this project's measured LP
ceilings sit at 477 to 479 while the boards behind them sit near 458, a
gap far too wide to certify anything, for exactly the fractional-hedging
reason above. The anatomy of those bounds gets its own section below.
One literature fact belongs next to the table. The strongest academic
treatment, the 2017 MILP and Max-Clique paper, solves integer instances
only up to roughly 7×7 or 8×8 and never reports an LP-relaxation bound for
the 16×16 instance (arXiv:1709.00252).
As far as the public record goes, nobody has published a sound LP or MILP
bound below 480 for full Eternity II. The 477 to 479 numbers measured
below are conditional (they assume a fixed border), so the unconditional
question stands open: proving any sound bound below 480 by convex
relaxation would be new.
We tried one relaxation of our own, built from the other end of the model.
Instead of asking which piece sits in which cell, list the 1,024 piece sides
(256 pieces, 4 sides each) and ask which sides pair up: two sides may meet
only if their colours match, and a finished board is a pairing of the 960
non-border sides into the 480 interior seams. That count is exact by
construction: 4 corner pieces contribute 2 non-border sides each, 56 edge
pieces contribute 3, 196 interior pieces contribute 4, and
8+168+784=960=480×2. The instance has zero slack; every
non-border side must find a partner.
The LP over this pairing graph tells its story in three steps. Freeze every
piece in one fixed orientation and the bound is 307.00, integral and matching
a closed-form count, but unsound for the real puzzle because rotations are
disallowed. Let sides pair freely across rotations (21,636 pairing variables,
one degree constraint per side) and the LP reaches 480.00 exactly, with 132
fractional pairings; adding per-piece pairing budgets changes nothing. Add
rotation consistency, one relaxed rotation variable per piece coupled to the
pairings so a piece's matched sides must agree on a single orientation
(262,900 variables, about 503,000 constraints, minutes of solver time): still
480.00, now with every pairing fractional and not one piece holding an
integer rotation. The LP keeps 480 feasible by placing each piece partly in
all four rotations at once, the side-level twin of the 30%-piece-1 corner
above.
So the colour ledger balances perfectly at every level of the relaxation we
could afford to solve, and a bound that pins at the maximum is a negative
result of a specific, useful kind: it localises the hardness. Nothing in
which sides can pair with which obstructs a 480. The obstruction lives
entirely in what these relaxations cannot see, that each piece occupies one
whole cell and that the pairing must lie flat as a 16×16 grid. Same verdict
as the cell-side model, reached from the opposite direction.
Three later measurements close the supply question completely. First, the
simplest counting bound of all, each colour c with mc half-edges
allows at most ⌊mc/2⌋ matched seams, evaluates on the
real piece set to 5⋅12+5⋅24+12⋅25=480 exactly,
because every one of the 22 colour counts is even. The global colour
budget is vacuous by construction of the puzzle; any scarcity argument
has to be local or conditional. Second, whole rotations do not restore the
obstruction. Give each piece a single integer rotation variable and ask
the per-colour supply model whether rotation commitments alone block 480:
they do not. The LP optimum is 480.0 and, this time solved to integer
optimality as well, the integer optimum is also 480.0: for every colour
there is a whole-rotation assignment putting its edges on the right sides
to spend the full ⌊Nk/2⌋ budget. That adds a fourth rung
to the ladder above (fixed rotations 307, free pairing 480.00 fractional,
rotation-consistent 480.00 fractional, and now even integral rotations
480 at the supply level). Rotation flexibility is never the binding
constraint; the obstruction is positional, which cell, next to which
cell. Third, the supply view cannot even rank partial boards. A
per-colour supply-capped seam LP (0.1 seconds per border) returns 480 for
all six borders we fed it, the border hosting the community 469-edge
board (matched edges, scored outside the strict five-hint convention;
conventions on the records page) and five freshly
generated borders alike. As a discriminator of border quality the
supply-level LP is useless; the positional, per-cell LP of the next
section demonstrably separates them.
The unconditional bound pins at the ceiling, so we conditioned it. Fix a
complete border (all 60 perimeter pieces) and solve the LP relaxation over
the 196 interior cells: the optimum is a valid upper bound for that
border. One convention note before the numbers: every score in this
section is matched edges out of 480 on the canonical 16×16 puzzle with the
five official hint pieces pinned, and the boards measured are this
project's best boards at the time of measurement, not records; community
bests sit higher, with the full context on
the records page.
The first surprise is how many different borders share one ceiling. Four
boards from our archive with four distinct borders, scoring 458, 457, 455
and 454 matched edges, all return exactly the same conditional LP bound:
478. Two of those borders are structurally unrelated to the others:
one 457 board shares the entire 56-piece top four rows with the 458 board,
but the 454 and 455 boards share only 8 or 9 of 256 placements with it,
about 3%. So the bound is a coarse invariant that genuinely different
boards have in common, not a fingerprint of one solution family. Local
search agrees the boards themselves are stuck: pushes on the three
non-458 boards (8, 4 and 4 seeds at ten minutes each) lifted them by +0,
+0 and +1; each basin sits at its own local optimum well below the shared
478 ceiling.
Two smaller measurements sketch the landscape around that ceiling. The 458
board's border behaves like a local maximum of the bound itself: all 13
random border perturbations we tried (5 single swaps and 8 three-piece
permutations, one RNG seed) lowered the conditional bound, by 2 to 5.5
points. Thirteen trials from one seed is a sketch, not a theorem. And
projecting the border of the community 469-edge board into the five-hint
convention (overlay the five hints, refill the displaced pieces) drops
its conditional ceiling to 477, one point below our 458 board's border: a
structural hint, not a proof, that the five-hint ceiling may sit below the
hint-free one.
With a border fixed, the bound decomposes over the three seam types: 60
border-ring seams (fully determined by the border), 56 border-to-interior
seams, and 364 interior-interior seams, for a combinatorial maximum of
60+56+364=480. Many different borders present the same multiset of
inward-facing colour demands, which is why so many share one LP value. On
the 458 board's border the split reads 478=60+54.02+363.98. Read
it slowly: the interior-interior part is essentially tight, the LP
conceding only 0.02 of 364 interior seams; the entire loss against the
maximum sits at the border-to-interior seam. The LP's verdict on this
border is that 2 of its 56 inward-facing seams are structurally
unmatchable by any interior completion. The board itself leaves 4 of them
unmatched, so at most 2 are theoretically repairable, a maximum in-border
lift of +2 to 460. We tested that headroom once: an exact integer re-solve
freeing 84 cells (the bottom perimeter plus the bottom five interior
rows; 30 minutes, one solver, one run) returned delta 0. Either the +2 is
not integer-feasible or it needs a larger window.
A second border trades the other way: its decomposition is
477=60+54.17+362.83, slightly more border-interior headroom but
about 1.15 fewer interior seams. No single colour dominates either gap;
the coupling is diffuse. Reaching 480 needs both parts maxed at once, and
no border we measured has both. One micro-fact of the puzzle's colour
design falls out of the same tables: the five rare colours (24 half-edges
each) contribute exactly 0 to the interior-interior part, because they
appear only on the inward-facing sides of border pieces; a rare-colour
interior-interior match is impossible by piece taxonomy.
The highest conditional ceiling in our archive is 479, one short of
perfect, and it sits on a board scoring only 457. Its border came out of
barely a minute of local search, versus hours behind the 478 borders. Yet
eight independent local-search seeds at one hour each all plateau at 457,
and an exact integer re-solve of the union of all its mismatch clusters
(28 cells freed) proves no local improvement exists: delta 0 in 0.46
seconds. The three decompositions line up as 478=60+54.02+363.98,
477=60+54.17+362.83 and 479=60+55.48+363.52, and the
LP-to-integer gap per board reads 20, 20 and 22: near-constant across
every border we tested (479 is also the highest ceiling seen across 18
conditional-LP runs on diverse borders). So the conditional bound ranks
borders by structure, but it does not predict which border yields the best
whole-piece board; the 479-ceiling border is integer-locked lower than
the 478-ceiling one. The mechanism is the page's own: the extra headroom
is fractional-hedging slack, and a higher ceiling only means the colour
ledger is closer to balanceable, not that any integral board realizes
it. One conjecture is worth writing down as a conjecture: a perfect
board's border must have conditional bound exactly 480, both parts maxed
at once, and the 479 border shows the LP gets within one of that
necessary condition.
A last caution about reading these decompositions: per-colour LP
allocations are not per-colour bounds. On the 458 board, one colour's
actual integer match count (21) exceeds the floor of its LP allocation
(20.89, which floors to 20). The LP optimum is a joint allocation across
colours; reading its per-colour rows as individual ceilings is a category
error. The full anatomy on that board: the interior-seam LP total is
363.96 against 346 seams actually matched, an interior gap of 17.96, of
which 5.96 is fractional slack and 12 is the LP allocating colours
differently than any whole-piece board can.
The textbook answer to a loose LP is to tighten it: lift the bilinear
terms, add cutting planes, climb the relaxation hierarchy. We tried one of
each and measured what happened. None closed the gap, and two of the
failures are instructive enough to be the point.
McCormick lifting: valid in theory, intractable at full size. The
standard cure for products of variables is one auxiliary variable per seam
per matching placement pair, sandwiched by z≤x1, z≤x2 and
z≥x1+x2−1. On small instances our implementation reproduces
the standard bound: a 6×6 needs 22,000 pair variables and 2.5 seconds, an
8×8 with 4 colours 300,000 and 60 seconds. It stops scaling immediately
after: an 8×8 with 6 colours and a 10×10 with 6 colours (1.25 million pair
variables) both timed out at 60 seconds on our LP solver, and the full
puzzle needs an estimated 5 to 20 million pair variables with about three
constraints each, beyond what that solver handles. The two obvious
shortcuts both produced invalid bounds, in opposite directions, and each
refutes itself on arithmetic alone. Restricting pair variables to
placements with LP mass above 0.05 under-counts and returns 402, below a
known feasible 458 board; an upper bound below a feasible point is a proof
of unsoundness. Keeping both the pair variables and the original seam
variables double-counts and returns 479.58, above the un-lifted 478;
adding constraints can only lower an LP optimum, so that one is
self-refuting too. The correct pattern, cutting-plane generation of
violated McCormick inequalities with exact reduced costs, needs
lower-level solver access than we built: untried, not impossible.
Cutting planes on colour scarcity: valid or vacuous, never both. We
implemented branch-and-cut with one cut family, supply-clique cuts on the
colour-conflict graph ("if a set of seams is forced to colour k, at most
⌊supplyk/2⌋ of them can match"), single-threaded,
one configuration; the verdict below is about this cut family, not about
all cuts. The plain, cut-free tail LPs on one of our 459-edge boards
(matched edges, five-hint convention) are sound but 4 to 22% loose:
freeing the last 1, 2, 3 and 4 rows gives LP bounds of 27, 58, 90 and 124
against achieved 26, 49, 74 and 104, never certifying anything. The cut
as stated is worse than loose, it is invalid: on the one-row tail it
drives the LP to 20, below the feasible 26, so the inequality cut off
the true optimum (colour-k half-edges are also consumed outside the
forced set, and by the other three sides of each piece). Every accounting
loose enough to be valid collapsed back to the vacuous no-cut bound. The
through-line matches the rest of the page: the puzzle's hardness is
global distinctness, each piece used exactly once, not local colour
scarcity, and the colour-conflict graph's cliques are tiny and
uninformative.
One level up the hierarchy: the SDP is just as blind. The next rung
above LP is the level-1 semidefinite (Shor) lift of the quadratic
formulation, provably sound: any true solution stays feasible at the same
objective value. We built it exactly on 3×3 planted instances with
certified optima of 12, 11 and 11 out of 12. On both non-trivial
instances the SDP certifies 12.000: it cannot see a unit-size obstruction
that elementary counting (5 half-edges of a colour allow at most 2
matches) resolves instantly. A sound McCormick LP control returns the
same 12.000, so the blindness is already present at the linear level; the
positive-semidefinite constraint adds nothing here. And the cost explodes
immediately: the full rotation-aware lift at just 9 cells (324 variables,
a 325×325 semidefinite block) failed three independent attempts under a
280-second single-core budget. Whether the rotation-joint lift would
recover tightness is open, not refuted. These are computational findings
on tiny instances with one SDP solver, not theorems.
- The LP: polynomial, genuinely fast. Interior-point methods solve
linear programs in polynomial time; on models of this size (50k–270k
variables, thousands to hundreds of thousands of constraints) modern
solvers finish in seconds to minutes. This is the one genuinely cheap
object on the page.
- The ILP: NP-hard, and not abstractly. Branch-and-bound is
backtracking with an LP bound at every node: worst-case exponential, and
an instance built at the hardness peak
is engineered to realize the worst case. The measured form of the cost:
a solver that handles 8×8 (64 pieces) returns nothing on 16×16, because
the tree under the root is squared, not doubled.
- The integrality gap is the real currency. The whole method's value is
the distance between the LP optimum and the best integer solution. Here
that distance is roughly 478 versus 458-and-stalling: the relaxation
spends its polynomial budget answering a question about a different,
fractional puzzle. Cutting planes exist to buy the gap down; nobody has
reported cuts that close a dent of it on E2, our own three measured
attempts above included, and the per-seam structure that fakes matches
regenerates the slack everywhere.
- Branch-and-bound prunes with the bound it has. A node is cut only
when its LP bound falls below the incumbent. With the bound floating ~20
edges above anything real, almost nothing prunes: the exact analogue of
wide, useless learned clauses in
CDCL, one road over.
The fair conclusion is relocation, not dismissal, the same one the
SAT page reaches for CDCL.
- Bounds, stated with their error bars. The relaxation is a valid
ceiling, computed in polynomial time; it is just a loose one here. The
dead-ends entry records the verdict so
nobody re-derives it expecting a certificate.
- A caution: not every relaxation is a bound. One tempting cheap
"relaxation", refilling the board cell by cell with the locally best
piece while allowing piece reuse, is not a valid ceiling of any kind:
it is a greedy heuristic whose fixed point depends on the starting
board. From one of our 457-edge boards (matched edges, five-hint
convention) it converges to 461; from a 456-edge board to 461; from a
440-edge board all the way to 469. The sound use is as a room
indicator: when the greedy relaxed score equals the board's own score,
the board is provably a strict local maximum even with piece-uniqueness
relaxed, a stronger dead-end certificate than operator-based tests. On
that 457 board the +4 gap was proven unclosable by any permutation
chain up to length 11 (40 million permutations, zero improvers). The
rule: only LP or MIP-derived values are ceilings; greedy relaxed scores
are diagnostics.
- Assignment subproblems, where integrality is free. Inside repair
loops, refilling k pairwise non-adjacent holes is a pure k×k
assignment problem: Birkhoff's polytope, integral vertices, Hungarian
algorithm in O(k3). That is Schaus's Eternity II neighborhood, and it
is the one place on this wiki where the optimizer's machinery runs at
full power: see
local search and ALNS.
- Easy integer subproblems, dispatched instantly. Rotation sets by MILP
in milliseconds (message 9071)
is the pattern: when a sub-question has tractable structure, a MIP solver
is the fastest reliable way to settle it, including settling that the
answer doesn't help.
- Infeasibility as a theorem. An ILP that comes back infeasible on a
pinned region proves the same impossibility a SAT UNSAT call does: the
certificate currency behind the
rigidity wall. This project mints those
certificates with SAT, which is faster on this encoding; a MIP solver is
a legitimate second mint, and Munjak's placer used exactly that signal,
"identifying an issue that would prevent all 256 pieces from being
placed" (message 8791).
- Formulations as neighbourhood generators. The 2017 paper's lasting
contribution is methodological: MILP-based constructive methods seeding a
multi-neighbourhood local search, plus new hard benchmark instances for
the community (arXiv:1709.00252).
The formulation survives as a part, inside a heuristic that owns the
integrality problem instead of relaxing it away.
- The formulation is the algorithm. We measured two MIP encodings of
the same task, recombining a small corpus of good boards into a better
one, and they behave night and day apart (one solver, CBC, single
runs). Encoding A, "each cell picks a source board", carries seam
variables quadratic in corpus size: fine at 4 or 5 boards (integer
optimum found in 17 to 86 seconds), but at 9 boards (about 50,000 seam
variables and 100,000 constraints) the solver found no feasible integer
solution in 30 minutes, and its LP bound of 1,094, over double the 480
ceiling, meant nothing. Encoding B, "free a region, one variable per
cell-piece-rotation, pin the rest", is 10 to 50 times smaller (about
800 variables), solves in under a minute, and its LP is tight against
the integer optimum: it proves local optimality instead of guessing.
The mechanism: encoding A's variables carry no geometric meaning the LP
can exploit, so fractional board-mixes earn credit no rounding
preserves, while encoding B's variables are placements, so its polytope
stays close to the integer hull. The 2017 paper recycling its
formulations inside heuristics is the same lesson from the other side.
The optimizer's road, walked to its end, teaches one clean fact about
Eternity II: the puzzle is exactly the integrality constraint. Everything
linear about it, the flows, the balances, the assignment skeleton, is
polynomial and was solved by 2009, to zero error, in ten seconds. What
remains is the requirement that every piece be somewhere whole, once. The
relaxation's cheerful fractional board is the sharpest picture anyone has
drawn of what the easy 99% looks like without the hard 1%.