This page answers a question that keeps surfacing on Math and CS Stack
Exchange and tops the dispute list on Wikipedia's Talk page for the puzzle:
edge matching is NP-complete in general, so does that tell us anything about
this fixed 16×16 board, and concretely, how would you hand Eternity II to a
solver? The short answers are: no, not directly, here are three encodings, and
a measurement at the end shows how much the choice among them can matter.
NP-completeness is a property of a problem, which in complexity theory means
an infinite family of instances indexed by a size parameter n. "Edge-matching
puzzles" is such a family: given n, a set of square tiles, and a colour
alphabet, decide whether the tiles tile an n×n frame with all abutting
edges agreeing. That decision problem is NP-complete
(Demaine & Demaine 2007), which
means both that a proposed solution is checkable in polynomial time and that
every problem in NP reduces to it.
A single fixed board is not a family. The Eternity II instance has a definite
answer, "yes, it is solvable" (the designers built it from a solution) or in the
5-clue competition form "yes, with exactly this arrangement". That answer is a
single bit. A single bit is a constant, and "is this constant NP-complete?" is
not a well-formed question: there is a constant-time algorithm that prints the
answer (return true), it just has the answer baked in. Asking whether one
instance is NP-complete is the same category error as asking whether the
number 17 is polynomial-time.
So the family is hard and the instance is a constant. What, then, is actually
true and useful about the difficulty of the board on your desk?
Two separate statements, kept apart:
- Worst-case hardness of the family. Because the general problem is
NP-complete, no algorithm is known that beats exponential time in the worst
case as n grows, and finding one would prove P=NP. This
bounds what any general edge-matching solver can promise. It says nothing
about how a specific input behaves.
- Empirical hardness of this instance. Hardness you can measure. The 16×16
board has on the order of 1.115×10557 distinct piece-and-rotation
arrangements, and the puzzle appears to admit very few solutions (the 5-clue
form is designed for essentially one; see
complex theory for the expected-count
estimate). A backtracking search therefore threads an astronomically wide
space toward a near-empty solution set, so it spends almost all of its time
exploring dead ends. That is why the puzzle is hard in practice, and it is a
claim about this board, not about the family.
The worst-case theorem and the empirical difficulty point the same way here,
but they are different kinds of statement and only one of them is a theorem. A
family can be NP-complete while a given instance is trivial (many are), and an
instance can be brutally hard to solve in practice even inside a family that is
polynomial. Ansótegui et al. made exactly the empirical case for Eternity II,
building solver benchmarks from it and measuring the difficulty directly rather
than appealing to the general theorem
(CCIA 2008).
The one-line version
"Is Eternity II NP-complete?" No: an instance has no complexity class. "Is the
edge-matching problem NP-complete?" Yes. "Is this instance hard to solve?"
Empirically yes, because the search space is ~10557 wide and the solution
set is nearly empty, so search drowns in dead ends.
The rest is practical: how do you write the board so a solver can chew on it?
All three encodings below share the same skeleton. Number the cells
c=1…256, the pieces p=1…256, and the rotations
r∈{0,1,2,3}. A placement is a triple (c,p,r): piece p dropped
into cell c turned by r quarter-turns. Every encoding has to say three
things:
- each cell gets exactly one placement,
- each piece is used exactly once,
- wherever two cells touch, the colours on the shared edge agree.
The encodings differ only in how they express constraint 3, the colour match,
and that difference is the whole story. The sketches below use a 2×2 or 3×3
board so you can see all the clauses; the 16×16 is the same shape at scale.
Introduce a Boolean variable xc,p,r, true when piece p sits at cell c
in rotation r. On the full board that is 256×256×4≈262,000 variables before any constraint. Then:
- Exactly one placement per cell. For each cell c, an at-least-one clause
over all its placements, ⋁p,rxc,p,r, plus at-most-one clauses
forbidding any two, ¬xc,p,r∨¬xc,p′,r′ for distinct
placements.
- Exactly one cell per piece. The mirror image: for each piece p, one
at-least-one clause over the cells it could occupy, plus at-most-one clauses
so it is placed only once.
- Edge match. For every interior adjacency and every placement whose exposed
edge shows colour k, forbid every placement in the neighbouring cell whose
facing edge is not k: a binary clause ¬xc,p,r∨¬xc′,p′,r′ for each conflicting pair.
A 2×2 sketch makes the third family concrete. Cells A (top-left) and B
(top-right) share a vertical edge; A's east edge must equal B's west edge.
For each placement (A,p,r) showing east colour k, and each placement
(B,p′,r′) whose west colour is not k, add ¬xA,p,r∨¬xB,p′,r′. Do the same for A/C vertically and the other two interior
adjacencies. That is all constraint 3 is: a large pile of "these two placements
cannot both be true" binary clauses.
The catch is that the pile is enormous. The conflict clauses dominate, the
at-most-one encodings add their own blowup (naive pairwise is quadratic; ladder
or commander encodings trade it for auxiliary variables), and the result is a
formula with millions of clauses whose structure gives conflict-driven search
almost nothing to learn from. This has been tried since 2008 and complete SAT
solvers stall on the full board; Blackwood, among others, reported that SAT did
not help. The encoding is clean, the solver is not the bottleneck, the
instance is. See SAT and CSP encodings
for the benchmark history and where SAT verdicts still earn their keep as
small-region impossibility proofs.
The exact-cover view is tidier, and it hides a trap that trips up almost
everyone who reaches for Knuth's dancing links.
Set up 512 items: one per cell ("cell c is filled") and one per piece
("piece p is used"). Each option is a placement (c,p,r), and it covers
exactly two items: cell c and piece p. A set of options covering every item
exactly once is a board with every cell filled and every piece used once. That
is a clean exact-cover instance, and Knuth's Algorithm X with dancing links
solves exact cover beautifully.
Here is the trap. Constraints 1 and 2 are cover-once conditions, which is
exactly what exact cover expresses. But constraint 3, the colour match, is not a
cover-once condition at all: a shared edge is not "used once", it is "assigned a
colour that both neighbours agree on". Plain Algorithm X has no way to say this.
People encode it, run it, and get boards with mismatched edges, or they try to
bolt on extra items and find the cover-once semantics fight them. This exact
confusion has its own question on the CS Stack Exchange.
The fix is Knuth's own extension, Algorithm C, for XCC, exact covering with
colours (TAOCP Volume 4B). Alongside the primary items (covered exactly once)
you add secondary items that may be covered any number of times, provided all
options covering a given secondary item assign it the same colour. Give each
interior edge of the grid one secondary item. A placement that exposes colour
k on a shared edge assigns colour k to that edge's secondary item. Two
placements can then coexist across the edge only if they colour it identically,
which is precisely the edge-match constraint, now expressed natively.
A 3×3 sketch: 9 cell items and 9 piece items (primary), plus 12 interior-edge
items (secondary, one per horizontal or vertical join). The centre cell's
placements each touch four secondary edge items and must colour-agree with all
four neighbours; a corner cell's placements touch two. Algorithm C threads this
without ever emitting a mismatched board. The takeaway students miss:
exact-cover-DLX for Eternity II needs Algorithm C, not Algorithm X. The
exact cover and dancing links page
walks the full XCC construction and where DLX genuinely shines (small boards,
exhaustive solution counting) versus where it stalls on the 16×16.
Two more framings, useful mainly as pointers:
- Integer linear programming. Reuse the SAT variables as 0/1 integers
xc,p,r. Constraints 1 and 2 become equalities ∑p,rxc,p,r=1
per cell and ∑c,rxc,p,r=1 per piece. The edge match becomes, for
each interior edge and each colour k, a linking condition tying the two
neighbours' colour-k placements together (one clean form: a fresh binary
edge-colour variable ye,k with ∑kye,k=1 and each side's
placements implying the matching y). It is a feasibility ILP, no objective,
and the LP relaxation is weak, so branch-and-bound behaves much like the SAT
search. See LP relaxations.
- Max clique. Build a graph whose vertices are legal placements and whose
edges join any two placements that are mutually compatible (different cells,
different pieces, and agreeing on any shared edge). A full board is a clique of
size 256. This is elegant on paper but the graph is huge and clique solvers
fare no better; it is worth knowing as a reduction, not as a practical attack.
The sections above end on a deflating note: the encoding is clean, the
instance is the wall. That claim deserves a number, and putting one on it
sharpened it in an unexpected direction. The bench is a family of planted
boards: framed, colour-balanced instances built from a known solution, five
solution cells pinned as clues, scored with the rim-excluding matched-edges
convention (a full solve at size N is exactly 2N(N−1) matched edges: 264
at 12×12, 480 at 16×16). Planted boards are not canonical Eternity II; they
plausibly admit very many solutions where the real puzzle is designed for
essentially one. What they offer is a ladder of guaranteed-solvable instances
that two different search paradigms can attack side by side.
On this bench, at 22 colours, a restarting depth-first search that places
only exact matches full-solves four of five 10×10 seeds (the fastest in
4 ms) and two of five 11×11 seeds, then zero of five at 12×12 and zero at
every size above. The failure is not a budget problem. The 12×12 seed-1
instance scores 127 of 264 after 20 seconds, after 45 seconds, and after
120 seconds, while the visited node count grows from 22 million to 132
million; a 14×14 instance creeps from 236 to 240 of 364 across the same
sixfold budget stretch. The search is not slowly converging; it is pinned.
Hand the identical instances to CP-SAT with a structured model (one integer
variable per cell ranging over piece ids under an AllDifferent constraint,
piece-and-rotation indices channelled through Element tables into per-side
colour variables, posed as a decision question) and the wall moves. Four of
the five 12×12 instances fall in 31.7 to 88.1 seconds (the fifth times out
at 300 seconds), and one of the two 13×13 instances tried falls in 74
seconds, with every returned board re-verified independently: piece
distinctness, clue conformance, recomputed edge count. Those are verified
full solves of boards that no DFS seed touches at any budget. The cliff
belongs to the search paradigm, not to the boards.
The original round of this measurement ran on a generator that allowed 26
interior colours, a setting the packaged bench cannot produce (its generator
caps interior colours at 22, the real puzzle's count). At 26 colours the
contrast was starker still: CP-SAT full-solved 25 of 25 instances at sizes
10 through 14 with median times from 0.10 to 0.84 seconds, half a second at
13×13, and finished a planted 16×16 in about 15 seconds, while the DFS
cliff sat one rung higher, at 13×13. That round also measured the
formulation gap in isolation: on one 12×12 instance, a generic MIP over
placement binaries with sum-to-one rows, run through HiGHS branch and
bound, returned 11 of 264 matched edges after 300 seconds; CP-SAT returned
the full 264 on the same instance in 0.42 seconds. Same problem, same
machine, roughly three orders of magnitude, and the entire difference is
how the constraints were written down.
Putting the two settings side by side surfaces a second finding: the cliff
moves with the colour count, for both paradigms at once. At 26 colours, DFS
dies at 13×13 and CP-SAT cruises through a planted 16×16 in seconds. At 22
colours, DFS dies one rung earlier at 12×12, and CP-SAT itself slows by
roughly two orders of magnitude between 11×11 and 12×12 and starts timing
out from 12×12 up: the 14×14 and 16×16 probes both hit a 120-second cap.
(The larger rungs were single-seed probes, and the 22-colour CP-SAT times
carry some inflation from a DFS arm sharing the machine, which does not
come close to explaining the gap to the sub-second 26-colour medians.) More
colours means a more constrained board and an easier search for everyone;
fewer colours drags both paradigms down together, so measurements taken at
26 colours flatter every solver in the race. The planted 16×16 the probe
timed out on is worth seeing, shown here as its constructed solution:
planted 16×16, 480/480.
One witness, counted ten times
The 26-colour round also tried ten heuristic families on the cliff, from a
naive row-major filler to AC-3 propagation and Hall-deficit pruning: six
full-solved 12×12 and none solved 13×13. Ten solvers agreeing looked like
ten pieces of evidence that the instances were the wall. It was one. All
ten commit chronologically and greedily on local information, so they fail
together for the shared reason, and the first solver from a genuinely
different paradigm overturned the conclusion in half a second. Agreement
across N solvers of the same family is one witness with N voices.
If you came asking whether the theory of NP-completeness makes this instance
provably hard, the answer is that it does not, and cannot: complexity classes
describe families, and this board is a fixed input with a fixed answer.
The general edge-matching problem is NP-complete, which caps what any solver can
promise as n grows, but the difficulty you actually feel is empirical, a
10557-wide space over a nearly empty solution set. Every encoding above
faithfully captures the puzzle, and at the full 16×16 none of them makes it
easy; but the planted-board cliff shows the choice of formalism is anything but
neutral below that scale, where the same board can be untouchable for one
paradigm and a one-minute solve for another. Once the board is
encoded, the leverage that remains is
arc consistency and smart search
order, which is where the rest of this section picks up.