- If you want to understand the wall
- Start with Demaine & Demaine (the NP-completeness proof) and Ansótegui–Béjar–Fernández–Mateu — together they explain why no fast general algorithm is known and, crucially, why Eternity II's exact parameters were chosen: the puzzle sits at the SAT/CSP phase transition (≈17 interior colors) where instances have about one expected solution and are hardest to find.
- If you want ideas that make a solver faster
- Benoist & Bourreau's O(1)-per-node global filtering and Schaus & Deville's CP + very-large-neighborhood search are the lineage behind most record boards. Wauters et al.'s hyper-heuristic and Salassa et al.'s MILP + max-clique formulations are the strongest published metaheuristics. Harris/Vanstone/Gepp lean on structural knowledge and the uniform color distribution rather than generic forward-checking, reporting up to three orders of magnitude over earlier solvers.
- The constraint-propagation core
- If you implement real pruning, Régin's AllDifferent filtering (generalized arc consistency via bipartite matching) is the cornerstone — Eternity II's bounded per-color piece supply makes a per-color AllDifferent the most powerful global propagator. Compact-Table is the algorithm to reach for if you ever encode precomputed patch tables.
- A different paradigm worth knowing
- Kovalsky–Basri–Glasner solve jigsaw assembly as one global linear program instead of sequential placement. It does NOT transfer to E2 directly (image compatibility is real-valued; E2 edges are discrete) — the authors say as much — but the global-optimization framing is a useful contrast to backtracking and the seed of any SDP-relaxation attempt.
- A practical trick the papers under-sell
- Precomputing legal two-piece pairs (corner+edge, edge+interior, interior+interior) and searching over pairs instead of single pieces is a recurring community speedup: it front-loads the cheapest constraint check and shrinks the branching factor. It's folklore as much as literature, but worth knowing before you reinvent it.
- Where the literature stops
- No published method actually solves the 16×16 board. SAT/CSP encodings empirically cap around 10×10 sub-puzzles; the best heuristics plateau well short of 480 matched edges. The community record (470/480, Blackwood 2021, using his own solver; tied since) beats every academic-published solver. The frontier today lives in the community (groups.io, Discord) and in open lab notebooks like this one — not in a paper.