Why it's hard
Eternity II is not accidentally difficult. It was designed to resist cleverness, and the measurable structural walls (rigidity, entropy, forbidden patterns) explain why no search, however clever, has reached the end.
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.
Measure the official 256 pieces with no solver in sight and every structural door is shut: no rotation-symmetric piece, 5 twin pairs in 32,640 pairings, a 307-of-480 matching cap if nothing rotates, colour budgets that pair to exactly 480 with zero slack, and a 17+5 palette sitting at the one-expected-solution point.
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.
Edge matching is NP-complete as a family, but that says nothing about one fixed 16×16 board: a single instance is a constant, not a problem. What is true is the family's worst-case hardness and this instance's empirical hardness, and how to write the puzzle for a SAT, exact-cover, or ILP solver with small worked sketches. A measurement on planted boards puts a number on the choice of formulation: a solvability cliff one search paradigm hits and another crosses, and that moves with the colour count.
Brendan Owen's complex theory estimates how wide the search tree is at every depth, and even how many solutions exist at all. Many in the community consider it the single most important thing to understand about Eternity II.
A counting argument on the official piece set forbids a score of exactly 479/480: every color's half-edges come in even numbers, and a single broken joint would leave two odd counts. The floor below perfect is 478, and at most 76 one-move near misses can surround any solution.
Eternity II uses 22 colors. They split 17 interior to 5 frame-only, and that count of around 17 lands near where this kind of puzzle is hardest to solve (the transition is a band, not a single integer).
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.
The community plateau in the high 460s reads as an entropic phase boundary of the instance, not a limit of solver engineering: exact computation on the official set gives a constraint density near 0.0094, an annealed landscape that collapses above 470 and crosses 1 only at 480, and an expected 10 to 20 mutually near-orthogonal perfect solutions. The instance-side numbers are exact; the 16x16 overlap-gap picture is a stated conjecture.
Eternity II has two rules: edges must match, and each piece is used once. The first is generous. All the hardness lives in the second.
Almost every small patch of pieces you could build is impossible. For a 2×2 square, 99.72% of the ways to place four pieces can never be made to match.
The usual way to crack a logic puzzle is to find a spot where only one piece fits, place it, and repeat. That lever doesn't exist here: every interior piece has between 73 and 137 possible neighbours, and not one is ever pinned to a single option.
Five of the 22 colors never touch the 196 interior pieces. The piece list forces every valid solution to spend all 120 frame half-edges on the border ring: a self-contained sub-puzzle at exactly zero slack (120 = 120), an Eulerian circuit on five vertices, coupled to the interior through just 56 inward edges.
Weight every edge color and read each piece as a signed vector, east minus west on one axis, south minus north on the other. Summed over any region the interior seams cancel and only the boundary survives, so the whole board totals zero. A quarter turn rotates the vector by a right angle, making the law algebra in the Gaussian integers.
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.
Borrow the physicist's trick that makes crystal defects solvable and try to turn a mismatched joint into a dislocation with a conserved charge. It fails three ways: a scalar height is blind to breaks, the break set is open strings rather than closed loops, and the oriented per-color current is not conserved. Only an unsigned parity bit survives.
A near-perfect board doesn't scatter its few errors evenly. It packs them into one band of five rows and leaves all the rest flawless. Which band is decided by the direction the search filled the board, and you can see the mirror on the real record boards.
Fill a board in any fixed order and the top three quarters go in freely while the difficulty piles into whichever band you finish last. Across forty generated boards the entire leftover sits in the bottom half every single time; shuffle the fill order and it scatters, so the hard region is made by the sweep, not hidden in the board.
Sum, over any visit order of the 16x16 board, the number of already-placed neighbours each cell faces at the moment it is filled: the total is exactly 480, for every order. A fill order cannot add restriction; it only chooses when each restriction binds. What separates orders is immediacy, the distance between a decision and its refutation, and only the extremes of that ranking are properties of the puzzle rather than of the engine.
A solver fills a few rows for free, then hits a wall in the middle of the board. Here's the mechanism: a scarce piece spent in the wrong place, rows ago.
Read a full board as a codeword whose 480 internal joints are parity-like checks, and the matched-edge score becomes 480 minus the number of failed checks. It is a clean lens with one load-bearing identity underneath it, and it is worth being exact about what the coding view buys and what it only renames.
On a 16×16 puzzle built like Eternity II, eighteen hints scattered across the board solve it in minutes, while piling hints into contiguous rows needs a hundred just to bring the search down to tens of billions of placements. Position, not count, is the lever, and it points straight at the endgame.
Joining clue pairs with early piece corridors feels like adding constraints. Counting says otherwise: a 1-wide corridor between even the two closest clues admits about two quadrillion distinct fillings, so it excludes almost nothing while spending pieces the endgame will need. In a controlled A/B, every corridor arm lost to its own control at every board size.
Five of Eternity II's 22 colors appear only along the border ring, each on exactly 24 edges, never once in the interior. A structural split that shapes how every solver treats the frame.
The border ring is the most constrained part of the puzzle, so a different strong border ought to pin a different high interior. It does not. Many distinct fully-matched borders, each completed by one fixed interior producer, give tops that are near-maximally different from each other yet uniformly low, none near the record band. The border diversifies the board without predicting its ceiling.
A solved board hides a simple bookkeeping law: every colour the border hands to the interior, the interior hands straight back. Break it and you know instantly the board is wrong; obeying it, though, guarantees nothing.
Eternity II follows a recipe for the hardest possible edge-matching puzzle: compact shape, no symmetric or duplicate pieces, split palettes, flat frequencies, one expected solution. The community reverse-engineered every ingredient in the launch year.
One research arc, thirteen families of structural theorems: ring purity, the 479 parity floor, the 470 wall as a phase boundary, flux invariants, the entropy area law, and the impossibility results that price every standard shortcut. This page is the map.