How do you solve Eternity II with a computer?

2 · The exponential wall

How big is "everything"? For an n×n puzzle there are roughly n²! ways to order the pieces times 4 rotations each. The chart below shows the number of digits in that count. Notice it's a straight-ish line: every step up in size multiplies the work by an astronomical factor. The 16×16 box on your shelf sits at ≈560 digits.

The blue line is the first lesson in algorithm design: deductions shrink worlds. Just noticing that corner pieces must go in corners and border pieces on the rim removes ~100 digits. Real solvers stack many such deductions. And it's still not nearly enough.

"Digits" stay abstract, so let's make it personal:

3 · Measured difficulty: size and colors

We generated hundreds of mini-puzzles and let the engine solve each one, counting nodes (candidate piece placements tested) until the first solution (median of 10 random puzzles per point; log scale!). Three things to see. Each extra row of board multiplies the work: the lines sit decades apart. More colors often make a puzzle easier, because wrong placements get rejected sooner instead of luring the search into deep dead ends. And every line shows something famous: a sharp hardness peak. Very few colors → tons of solutions, easy to stumble on one. Many colors → so constrained the search barely branches. The peak sits right in between — and, crucially, it slides to the right as the board grows: the 6×6 line peaks at 4 colors, the 8×8 line at 6 colors, roughly one extra color per added row. At its peak the median 8×8 puzzle needs over 2 billion piece placements, and most seeds there ran so long we had to stop measuring them (the flat tops are those censored points). One color either side and it collapses by a hundredfold. Extrapolate that one-color-per-row trend out to a 16×16 board and the peak lands right around 22 colors — exactly where Eternity II was built to sit. It isn't an accident past the peak; it's tuned to land on it.

4 · The order you search in matters. A lot.

Same puzzles, same solver. The only change is the order in which squares get filled. Orders that keep new placements glued to already-placed neighbors (snake, spiral) constrain each step and prune early. Orders that scatter placements (random) leave pieces unconstrained and pay for it later. This is a real research topic, and you can design your own order and race it. Here is what the classic orders actually look like; follow the arrows (red = first cell, green = last):

A subtlety worth naming (thanks to Dan Karlsson): row-major and column-major are the same order up to flipping the board across its diagonal, so over many puzzles they should cost the same — any gap between them here is sampling noise, not a real difference. The orders that genuinely differ are the ones with a different shape: a spiral, a diagonal, border-first. One caveat: the random-order bar is a lower bound, not a measured median — every sampled run hit the search cap without finishing, so its true cost is higher than shown.

The same question, taken all the way on the full 16×16 puzzle, is the DFS study: it measures what each fill order, heuristic and break rule buys, and finds the wrong order can cost more than 300 points of score.

5 · Why computers think in binary here

A piece is just four small numbers (up, right, down, left motif). No pictures, no geometry. These four demos run live; watch them for a few seconds each:

Stored as numbers, the entire official set is about 1 KB. Serious solvers go further with bitsets: one 64-bit number carries a yes/no answer about 64 pieces at once, so a single CPU instruction filters 64 candidates simultaneously. That's how the fastest engines reach hundreds of millions of nodes per second. Representation, not just the algorithm, is part of the craft.