Glossary
The words the wiki leans on, defined once: community jargon, the loaded computer-science terms that mean something specific here, and the notation the boards are written in, each with a link to the page that goes deep.
A
- all-different (Régin's filter)
- The global constraint that each of the 256 pieces is used exactly once, filtered completely in polynomial time by a bipartite-matching check that deletes any piece no longer placeable. See →
- ALNS
- Adaptive Large Neighbourhood Search: destroy part of a board, rebuild it better, and learn which demolitions pay. The most reliable board polisher measured here. See →
- annealing (simulated annealing)
- Local search that treats mismatches as energy and temperature as tolerance for getting worse, cooling slowly toward a good board. Holds the longest-standing record in its family. See →
- arc consistency (AC-3)
- Propagation that makes every cell's candidate list defend itself against its neighbours to a fixed point, going beyond one-move-ahead forward checking. Prunes hard on small boards, fades about two cells out on the full one. See →
B
- backtracking
- Depth-first search that places pieces one at a time in a fixed or computed order, undoing a placement when it leads to a dead end. Every record engine lives in this family. See →
- beam search
- Keep the K most promising partial boards alive and grow each by one cell, then truncate back to K. The workhorse behind this project's from-scratch builders; breadth alone stalls in the deep interior. See →
- border (frame)
- The outer ring of the board: the four corner and 56 edge pieces, which show a grey (unscored) edge outward. The rest are interior pieces. See →
- branching factor
- How many candidate placements a cell offers on average during search. On Eternity II it stays high deep into the board, which is why the search tree never collapses. See →
- break index
- The number of mismatched (broken) edges on a board. A full solution has zero; the community record leaves ten. The cheap score every solver optimises, and a poor guide to how close a board really is. See →
- Bucas notation
- The community's shared text format for a board, from Jef Bucas's viewer: rows A to P, columns 1 to 16, each cell a piece id and rotation. The lingua franca every solver reads and writes. See →
C
- candidate list
- The set of piece-and-rotation options still legal for a cell after propagation. Shrinking it is the whole point of constraint propagation. See →
- cell
- One of the 256 squares of the 16×16 board. See →
- clue puzzle
- One of four optional companion puzzles (two 6×6 and two 12×6) that each revealed one piece placement on the main board when solved. See →
- comb search
- A fill order that scans most rows horizontally, then sweeps the remaining rows vertically, with the tooth length tuned to a target score. Verhaard's ordering. See →
- constraint propagation
- Automatically deleting candidates that can no longer lead to a legal board, cascading the effect until nothing more can be removed (a fixed point). See →
D
- dancing links (DLX)
- Knuth's data structure for exact cover: doubly linked lists that cover and uncover a column in O(1) by pointer surgery, so backtracking is cheap. See →
- dead end
- A partial board that provably cannot extend to any complete board. Recognising them early is what pruning is for. See →
- deficit (border balance)
- An imbalance on the seam between the border ring and the interior. A completable board needs it to be zero, giving a cheap necessary condition. See →
- domain (of a variable)
- The set of values a variable may still take. Here, the piece-and-rotation options left for a cell. See →
E
- edge (seam)
- A shared boundary between two adjacent cells. The 16×16 board has 480 interior edges, all of which must match in a full solution. See →
- edge slipping
- Deliberately placing a mismatched piece on a depth-gated schedule so the search can pass a barrier it otherwise stalls at. The lever behind Verhaard's 467. See →
- encoding
- Rewriting the puzzle in another solver's input language, e.g. as SAT clauses or CSP constraints, to borrow a decade of that solver's engineering. See →
- entropy (area law)
- How rich the matching grammar is per cell. The raw 2D entropy is modest, and the all-distinct rule collapses it exponentially, which is why near-solutions are so scarce. See →
- exact cover
- The problem of choosing options so every item is covered exactly once. Eternity II states cleanly as exact cover with colours (XCC), Knuth's Algorithm X being the classic machine for it. See →
F
- fill order
- The sequence in which a backtracker visits the 256 cells. Its one free choice, and it moves the search-tree size by orders of magnitude at no runtime cost. See →
- forbidden pattern
- A small local configuration that can never match, so no solution contains it. On Eternity II almost every 2×2 arrangement of pieces is forbidden. See →
- forward checking
- The lightest propagation: when a piece is placed, remove it and any now-incompatible pieces from neighbouring cells' candidate lists. See →
G
- grey edge
- A border-facing edge, coloured grey and never scored. Interior pieces have none; border and corner pieces show one or two. See →
H
- heavy tail
- A runtime distribution where a few unlucky runs take orders of magnitude longer than the median. It is what makes restarts pay. See →
- heuristic
- A rule that guides search without any correctness guarantee, e.g. visit the most-constrained cell first, or break ties by piece rarity. See →
- hint
- A cell whose piece and rotation are given in advance, whether the mandatory centre clue or one revealed by a clue puzzle. Where the hints sit matters more than how many there are. See →
I
L
M
- matched edge
- An edge showing the same colour on both sides. The score is the count of matched edges, out of 480; a mismatch is the opposite. See →
- meet in the middle
- Enumerate two halves of the board and join them on a shared interface, trading memory for half the exponent. Real on bands, measured to stop paying at full size. See →
- mismatch-tolerant search
- A backtracker that permits a budget of deliberate mismatches, aiming for a high partial score (467, 469, 470) rather than a perfect 480. See →
- motif
- The printed glyph standing for each edge colour on the physical tiles. This site can render boards in the real motifs. See →
N
- no-good learning
- Recording that a particular partial state cannot extend, so the search never re-enters it. Pays on small boards; the number of distinct no-goods outruns memory at 16×16. See →
- node
- One state in the search tree. Node cost, the time to evaluate one, is what solver engineering drives down. See →
P
- parity argument
- Counting something on the board twice, once from each side; the totals must agree, which yields one-pass impossibility proofs. See →
- phase transition
- The difficulty peak where solutions are scarce but do exist. Eternity II's 22 colours place it right at that peak by design. See →
- piece
- One of the 256 square tiles, each with four coloured edges. Also called a tile. See →
- piece theft
- Spending a scarce piece in the wrong place early, so a later cell that needed it has nothing to fill it. Where many searches quietly die. See →
- placement
- An assignment of a particular piece at a particular rotation to a particular cell. See →
- propagation
- See constraint propagation: removing candidates forced dead by a placement, cascading to a fixed point. See →
- pruning
- Discarding a whole branch of the search without exploring it, using a constraint, a bound, or an impossibility proof. See →
R
- relaxation (LP/ILP)
- Dropping the whole-piece requirement so a linear solver can place fractions of pieces and reach zero error, then paying for it when integrality is restored. See →
- restart portfolio
- Running the same solver many times with different random seeds, cutting each off early. Every record solver since 2007 is one. See →
- rigidity wall
- The proven fact that record boards are locally frozen: freeing and re-optimising the halo around the mismatches finds no improvement. The central barrier of the puzzle. See →
S
- SAT
- Boolean satisfiability: is there an assignment satisfying every clause? Complete SAT solvers stall on the full board but still prove sub-boards impossible. See →
- score
- The number of matched edges on a board, out of 480. A perfect solution scores 480; the community record scores 470. See →
- search tree
- The exponential tree of all placement sequences a backtracker could explore. On Eternity II it is astronomically large and barely shrinkable. See →
- solver engineering
- The craft below the algorithm: lookup tables, cache-sized structs, generated code. It decides whether a node costs 26 cycles or 2,600, and it is why the record engines run at all. See →
- solver speed (nodes per second)
- Throughput: how many placements a solver evaluates per second. It changes which boards you reach, not the ceiling you hit. See →
- strict-5 (strict-canonical)
- A board that honours all five official clues: the mandatory centre piece plus the four placements the clue puzzles reveal. Most records honour only the centre. See →
T
- tempering (parallel tempering)
- Run several annealing chains at different temperatures and periodically swap their states, so the search crosses barriers a single chain cannot. See →
- transposition table
- A hash table of already-evaluated states, so identical subtrees are not re-explored. Its hit rate is low on Eternity II. See →
U
- URDL
- Up, right, down, left: the order in which a piece's four edge colours are written, and the sense of a clockwise rotation. See →
V
- void
- A corner colour-pair that no interior piece can present, so a cell demanding it is a dead end before any piece is placed. See →
W
- wall
- A barrier that stops a solver at a score: the rigidity wall (no local improvement), the σ-cycle wall (no basin hop), the depth wall (breadth search stalls). Different methods die on different walls. See →
X
- XCC (exact cover with colours)
- Knuth's extension of exact cover with coloured secondary items, which models edge matching faithfully. The clean statement of Eternity II as exact cover. See →
Σ
- σ-cycle (sigma cycle)
- An interlocking loop of piece moves connecting two board configurations. Because every partial application scores worse, you cannot walk between basins gradually. See →