# Reduce the search

> Everything that throws away hopeless states before the search wastes time on them: propagation to a fixed point, the all-different matching filter, learned no-goods, and the edge-slipping invariant.

- Canonical page (with interactive figures/demos): https://eternity2.dev/research/build/reduce/
- Updated: 2026-07-13

---
Everything that throws away hopeless states before the search wastes time on them: propagation to a fixed point, the all-different matching filter, learned no-goods, and the edge-slipping invariant. These prune hard on small boards; the recurring lesson here is how far that pruning reaches on the full 16×16, and where it fades.

The pages below go technique by technique: what each is in a line, what it
actually reached on the real 16×16 board, where it stops, and the labs and
measurements to back it. For the whole territory at once, start with
[a map of every known approach](/research/build/approaches-map).

## Pages in this section

- [Arc consistency, from AC-3 up](https://eternity2.dev/research/build/reduce/arc-consistency) — 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.
- [All-different, Régin's matching filter](https://eternity2.dev/research/build/reduce/alldiff-regin) — No piece may be used twice: one global all-different constraint over 256 cells. Jean-Charles Régin showed in 1994 how bipartite matching filters it completely in polynomial time; its per-colour cousin is the strongest propagator anyone has measured on edge matching, with one sharp caveat about mismatch-tolerant searches.
- [Edge slipping](https://eternity2.dev/research/build/reduce/edge-slipping) — Louis Verhaard's prize-winning move: let the backtracker place a mismatched piece, but only at chosen depths near the end of the board. Each allowed slip costs one point of score and multiplies the number of target boards astronomically. That is why his 467 was found more than fifty times, and the direct ancestor of Blackwood's breaks.
- [No-good learning: remembering why you failed](https://eternity2.dev/research/build/reduce/nogood-learning) — A failed subtree is a theorem: this partial state can never extend. Store it and never re-enter. The community tried both flavours: chess-style transposition tables over the search frontier, and mined constraints about the puzzle itself. The full ledger of what memory buys at E2 scale, and the small boards where it genuinely pays.

## Related

- [A map of every known approach](https://eternity2.dev/research/build/approaches-map) — The survey the community keeps asking for and never finds: every family of attack tried on Eternity II, what each one actually reached, where it walls out, and a link to the deep page. One organising insight runs through all of them.
- [The techniques](https://eternity2.dev/research/build/techniques) — The technique shelf: the algorithms and pruning ideas that recur in every serious Eternity II solver, each with what it is, what it costs, and what it actually bought when measured on this puzzle.