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.
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.
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.
Eternity II uses 22 colors. They split 17 interior to 5 frame-only, and that 17 is exactly where this kind of puzzle is hardest to solve.
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.
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.
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.
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.
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.
On a 16×16 puzzle built like Eternity II, eighteen hints scattered across the board solve it in minutes, while the same puzzle needs eighty or more hints piled into contiguous rows to be as easy. Position, not count, is the lever, and it points straight at the endgame.
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.
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.
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 has two rules: edges must match, and each piece is used once. The first is generous. All the hardness lives in the second.