Forward checking looks one move ahead; arc consistency makes every cell's candidate list defend itself against every neighbour's, to a fixed point. Mackworth's AC-3, the optimal refinements that followed, and what the whole family actually measured on this puzzle, including where it is unsound.
AC-3 O(e·d³) · AC-2001 O(e·d²) (optimal for arc revision)
Space
AC-3 O(e) · AC-2001 O(e·d)
On the 16×16 board e = 960 directed interior arcs and d ≈ 764 candidate tuples per cell, so the worst-case gap is ~4×10¹¹ vs ~5.6×10⁸ checks, but real propagations touch only a few cells, and the cost is paid at every search node.
A backtracker on Eternity II spends most of its effort not placing pieces but
ruling them out. Since no cell is ever forced
(every interior position keeps dozens of live candidates deep into the
search), the only leverage available is shrinking those candidate lists as
hard and as cheaply as possible. Arc consistency is the standard machine for doing
that, and it has a fifty-year paper trail.
Give every empty cell a domain: the set of piece-and-rotation candidates
still allowed there. On the full puzzle that starts at roughly 764 tuples per
interior cell. Forward checking is the one-step discipline: when a piece
is placed, delete it from every other domain and delete every candidate that
clashes with the newly exposed edges. Cheap, and every serious solver does at
least this.
Arc consistency demands more. For every pair of adjacent cells, every
candidate in one domain must have at least one compatible partner in the
other, a support. When a deletion anywhere leaves a candidate
unsupported, that candidate goes too, and the check ripples outward until
nothing more can be removed. For edge-matching this is exactly "a piece may
stay in a cell only if each neighbouring cell can still answer its colours".
Alan Mackworth's AC-3 (1977) is the coarse-grained way to reach that fixed
point: keep a queue of directed arcs, revise one arc at a time (scan a domain,
delete unsupported candidates), and whenever a domain shrinks, requeue the
arcs that point at it. It is short, correct, and easy to make incremental
inside a search, which is why it is still the default everywhere. Worst case
it costs O(ed3) for e arcs and domain size d; on the 16×16 board e
is e=960 (the 480 interior adjacencies, both directions) and d≈764.
Its known flaw: every revision searches for supports from scratch, so the same
support gets rediscovered thousands of times as the search dives and
backtracks.
Descriptions of worklist algorithms all sound alike; watching one settle is
what makes it click. Below is AC-3 on a toy version of the problem: a 4×4
board, 3 edge colours, every cell starting with all 64 candidates (16 tiles ×
4 rotations). Place a piece and follow the queue: which arcs enter it, what
each revision deletes, how a deletion re-arms the arcs pointing at the
shrunken domain, and how the ripple dies out. The counters compare AC-3's
work against the naive fixed-point loop (AC-1: re-sweep every arc until a
full pass is clean) running on the exact same positions.
▶Interactive: watch AC-3 settle to a fixed pointExplore →
Watch AC-3 propagate — one arc at a time
A 4×4 edge-matching toy with 3 colours: each cell starts with all 64 candidates (16 tiles × 4 rotations). Place a piece and watch the worklist: arcs aimed at the changed cell enter the queue, each revision deletes unsupported candidates, and every deletion re-enqueues the arcs pointing at the shrunken domain — until the queue runs dry.
Number = candidates left in the cell's domain. Arrows = arcs waiting in the queue (the bold arrow is the arc being revised).
0/16 placed0 arcs in queue
AC-3 (worklist)
0arc revisions
0support checks
naive re-sweep (AC-1)
0arc revisions
0support checks
Fresh board: every cell keeps all 64 candidates. Nothing has changed yet, so the queue is empty.
The counters are the whole point: AC-3 only revisits arcs whose far domain actually changed, while the naive fixed-point loop re-sweeps all 48 arcs until a full pass is clean. Same deletions, wildly different work — and AC-2001 would cut the support checks further by remembering where each search stopped.
Two things are worth noticing. Early placements barely ripple: one ring of
neighbours shrinks and the wave stops, because the second ring still finds
supports for all three colours among the survivors. Late placements ripple
much further: domains are tight, and single deletions strand candidates two
and three cells away. That is exactly the behaviour on the real puzzle: arc
consistency earns its keep in the endgame, not the opening.
Start. Every cell holds a domain of 64 candidates. The arc queue is
empty; with no deletions yet, there is nothing to check.
A piece lands on B2. Its domain collapses to the single placed
candidate. Every arc aimed at B2 enters the queue, one per neighbour:
here (B1→B2), (C2→B2), (B3→B2), (A2→B2). Nothing else does: no other
domain changed, so no other arc can have lost a support.
Pop an arc, revise it. Take (B1→B2): scan B1's 64 candidates, and for
each one search B2's domain for a compatible partner, a support. B2
now holds one piece, so only candidates whose south edge matches its north
colour survive: roughly a third. The rest are deleted.
Deletions re-arm arcs. B1's domain shrank, so candidates elsewhere
that leaned on the deleted ones may be stranded: every arc pointing at B1
re-enters the queue, except the one from B2 that just fired. This is the
ripple.
No deletion, no requeue. When a revision removes nothing, the arc is
simply dropped. Early in the game the second ring almost always survives
intact, and the queue drains in a handful of revisions.
Fixed point. The queue is empty: every candidate everywhere has a
support in every neighbouring domain. No order of processing changes this
final state: the fixed point is unique, and the queue discipline changes
only how fast you reach it.
The AC-1 comparison in the demo is the entire argument for the worklist: the
naive loop re-revises all 48 arcs per sweep until one sweep is clean, doing
the same deletions for several times the checks, and the gap widens as the
board grows.
The literature spent two decades fixing that redundancy. AC-4 (Mohr &
Henderson 1986) counts supports explicitly: optimal O(ed2) time, but
O(ed2) memory and painful state restoration on backtrack. AC-6 and AC-7
(Bessière; Bessière, Freuder & Régin) store supports lazily and exploit
bidirectionality, keeping optimal time with O(ed) space at the price of
fine-grained bookkeeping.
The version worth knowing today is AC-2001/AC-3.1, found independently by
Bessière & Régin and by Zhang & Yap in 2001: keep AC-3's simple loop, but
remember for each candidate-arc pair the last support found, check that it
is still alive before searching again, and resume the scan from where it
stopped rather than from zero. That one integer per pair delivers the optimal
O(ed2) bound with only O(ed) memory; on this puzzle that is about
367,000 small integers, negligible. The 2005 journal study measures 1.5–9× less CPU
than AC-3 in maintained-arc-consistency search, and shows the advantage over
AC-6 growing with the domain size on the far side of the arc. Eternity II
has huge domains on both sides of every arc, which makes AC-2001 the
textbook fit.
Arc consistency checks pairs of cells. The next rung up, path consistency,
checks triples: it removes any pair of assignments that no third cell can
support, propagating a much stronger condition. It shrinks the search tree
enormously, and the community measured exactly how much, and exactly why nobody
uses it. In March 2008 Geoff ran the ladder on Brendan Owen's beginner puzzles
(msg 4827):
On the 6×6, plain nodal consistency leaves a search tree of over 40,000
nodes. Partial path-1 consistency drops it to about 10,000. Partial path-2
consistency drops it to 138 nodes, the bare minimum needed to walk to all
eight solutions. But the runtime goes from 0.25 seconds to over 10 seconds.
On the 8×8 the trade gets worse. Arc consistency alone solves it in under
6 million nodes and about 36 seconds. Adding path-1 preprocessing cuts the
tree to roughly 1 million nodes but costs about 14 minutes of
preprocessing; path-2 preprocessing was still running after 7 hours.
The pattern is unambiguous: each stronger level of consistency really does cut
the tree by orders of magnitude, and each one costs more than it saves. Geoff's
own conclusion was that path consistency is "simply not a cost-benefit positive
effect" on this puzzle. That is prune versus speed
stated in the language of a real algorithm: the prune is genuine and large, but
here the machinery to compute it is more expensive than the search it removes,
which is why the record engines stop at arc consistency (or below) and spend the
saved time on raw placements instead.
The accounting, with e the number of directed arcs and d the maximum
domain size:
AC-3 runs in O(ed3) time worst case: each arc can be re-enqueued up
to d times (once per deletion in its far domain), and each revision costs
up to d2 support checks. Its working memory is just the queue, O(e).
AC-2001 runs in O(ed2) time, which is optimal for any algorithm
based on arc revision: there are ed candidate–arc pairs and each may
need its support walked once across a domain of size d. The price is the
last-support table: one integer per candidate–arc pair, O(ed) space.
On Eternity II's scale those symbols are: e=960 (480 interior adjacencies,
both directions) and d≈764 candidate tuples per interior cell. So
the worst-case bounds sit near ed3≈4×1011 elementary
checks for AC-3 against ed2≈5.6×108 for AC-2001, three
orders of magnitude apart on paper. Worst cases are pessimistic (real
propagations touch a few cells, as the demo above shows), but the ratio is
why the literature calls AC-3's bound the thing to fix, and the fix costs
only O(ed) integers of memory. The catch on this puzzle is not the
propagation cost per node; it is that inside a search this cost is paid at
every node, millions of times per second, which is why constant factors and
cache behaviour end up mattering as much as the exponent on d.
On this project's engine (measured here; not independently replicated):
A plain backtracker propagating AC-3 together with the
per-colour matching filter
reaches 449 of 480 edges on the canonical puzzle in about 44 seconds
single-threaded, around 2.5 seconds on 8 cores.
The best algorithmic speedup found inside AC-3 itself was mundane: a
precomputed table of which rotations of the same piece share edge colours,
so revisions stop re-deriving it, worth a 2.9× throughput gain on the
engine's reference benchmark.
The unbuilt part: AC-2001 was recommended twice in this project's notes and
never actually built, so its projected 2–5× win here is a reading of the
literature, not a measurement. And the belief that AC-3 dominated the
runtime profile was itself never confirmed by a profiler. Measure before
porting.
Arc consistency assumes every edge must match perfectly. The record engines
do not: Blackwood-style searches allow a
budget of deliberate mismatches at late depths, and under that regime AC is
unsound: it prunes boards that a licensed mismatch would make perfectly
legal. On this project's engine the whole AC family is switched off in
break-tolerant runs for exactly that reason. The one strong propagator that
survives the mismatch regime is piece-level all-different; see
Régin's filter.
For any exact-matching search, arc consistency is mandatory and cheap: it is
the difference between a backtracker that thrashes and one that reaches the
440s. Forward checking alone leaves prunings on the table; AC-3 collects
them; AC-2001 collects the same ones for less CPU, if you first verify that
propagation is where your cycles actually go. For mismatch-tolerant record
hunting, leave it out; soundness comes first.