Hard search problems have a difficulty knob. Loosen it and there are many
solutions, so a search trips over one fast. Tighten it and there are none,
which is often easy to prove. In between sits a narrow band where solutions
are scarce but real, and that's where search blows up. People call it a phase
transition, like water freezing.
For edge-matching puzzles the knob is the number of colors. Too few and pieces
fit together countless ways; too many and they barely fit at all. The
published analysis
puts the peak at around 17 interior colors, the setting where a puzzle this
size has about one solution. Eternity II uses 17.
The community had that number within weeks of launch: in August 2007,
Brendan Owen derived I=(196!⋅4196)1/392≈17.14
interior colours from the "about one expected solution" criterion, exactly
the published parameters, years before the academic analyses
(Design the hardest puzzle, msg 1947).
▶Interactive: the colour-count difficulty peakExplore →
This is the same data the Algorithms page charts: the median work to solve a generated puzzle, by board size and number of colors. The y-axis is logarithmic, so each gridline is ten times the one below. Read it as the puzzle's difficulty knob.
Board size:
Loading chart…
On a 7x7 board the work climbs past sixty million around five or six colors, then falls away by a factor of a hundred thousand as colors increase. The bigger the board, the sharper and further-right the spike. The full 16x16 lives far up and to the right of anything you can chart here, which is why its 17-color setting sits squarely in the hard region.
Work is the number of placements the solver makes; values are medians over many generated puzzles. Points at the scarce-color end are lower bounds where a run was stopped early.
The chart above is precomputed. This one isn't: the engine solves fresh
puzzles live, one per colour count, and draws the peak from real runs in your
browser.
▶Interactive: solve across the difficulty peak liveExplore →
The colour-count argument says where the peak is. In March 2008 Brendan Owen
went and watched a phase transition happen, directly, on the actual pieces. He
took a thin 2-by-L interior rectangle and tiled it with random sets of E2's
interior pieces, four hundred random sets at each length, and recorded how many
could be completed with no mismatch
(msg 4909).
Loading chart…
The shape is the phase transition in miniature. A 2-by-1 or 2-by-2 strip is so
short that random pieces often just fit: 58% solvable at length 1. Then it dies
completely. From length 4 through 15, not one random set out of four hundred
tiles the rectangle at any length: solutions are so scarce they effectively do
not exist. And then they come back. At length 16 one set in four hundred works,
by 19 it is 8.5%, by 21 it is 57%, and by 22 nearly nine in ten. The region
where solutions are vanishingly rare but not yet impossible is exactly the hard
band, and it is not a story or a model here, it is a count. It is also why a
14-cell-wide interior is so punishing: it sits in the steep part of that climb,
where a solution exists but almost no random arrangement is one.
This is the clearest single sign that Eternity II was made hard on purpose.
Board size, piece count and color split all aim at the same target: a puzzle
with about one solution, placed at the worst possible spot for any search to
find it. The difficulty was chosen, the way a good exam is neither trivial nor
impossible.
How do we know the peak is real and not just a story? Two ways meet here. The
published analysis
derives it:
for framed edge-matching puzzles, the color count where you'd expect about one
solution falls near 17, and that is the hardest setting to search. And you can
watch a piece of it yourself in the demo above: build real puzzles, count the
work, and see it explode when colors are scarce. The impact is concrete. It
means the gap to a solution isn't a tuning problem you can grind away with a
faster machine; the puzzle was placed where search is worst on purpose, so
beating it needs a genuinely better idea, not just more effort.