# Late filters: every check that works, works too late

> A filter added to the row scan can save at most the bits its depth allows, and the checks that refute nearly all wrong boards only start to bite at depths 144 to 192, past the widest level of the tree (158). A perfect free cut at depth 144 would save 2.4 bits of the 134.4 the scan costs, so no late filter closes the gap. The ceiling table is derived arithmetic on a measured profile, not an experiment.

- Canonical page (with interactive figures/demos): https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/late-filters/
- Updated: 2026-11-14
- Topics: search-space, backtracking
- Reproduce: `just experiments approach-pricing`
- Source: Approach pricing: ceiling script, level profile and notes (https://github.com/raphael-anjou/eternity2/tree/main/research/experiments/approach-pricing)
- Source: Prefix statistics: census tilt and arc-consistency follow-up (https://github.com/raphael-anjou/eternity2/tree/main/research/experiments/prefix-statistics)
- Source: Real-puzzle profile: size of the row-scan tree by depth (https://github.com/raphael-anjou/eternity2/tree/main/research/experiments/real-puzzle-profile)

---
Can a cheap check, added to the row scan, cut enough of the tree to matter? The
answer depends on one number per check: the depth at which it starts to remove
wrong boards. Nothing a filter does before that depth counts, and the tree is
thin there. The checks tried bite late, so the answer is no.

## The setup

The exact row-scan tree on the real pieces with all five clues holds 10^40.457
nodes, or 2^134.4 (95% interval 10^40.440 to 10^40.473, five repetitions at a
million particles each; see [the measured size](/research/lab/experiments/raphael-anjou/full-solve/price-of-a-full-search/)).
Its widest level sits at free depth 158 (free depth counts placed non-clue
cells). About 10^15 nodes are affordable for a modest run, so the gap is about
84 bits; against the larger efforts priced on the
[series hub](/research/lab/experiments/raphael-anjou/full-solve/) it is 56 to 73
bits.

Take a filter that removes every wrong node from free depth d onward, for free
and with no false cuts. It cannot do better than the share of the tree that sits
at depth d or deeper. The saving in bits is log2 of the total over the nodes
above that depth.

## The ceiling of a perfect free cut

| Free depth | 52 | 64 | 80 | 96 | 112 | 128 | 144 | 158 |
|---|---|---|---|---|---|---|---|---|
| Most it can save (bits) | 57.1 | 44.8 | 29.8 | 17.1 | 10.7 | 6.8 | 2.4 | 0.5 |

**Status: derived arithmetic from the measured level profile, recomputed by a
second analysis. It is not an experiment.** The profile is measured and
independently checked; the table is a sum over it, with no run of its own. It
bounds the gross gain of any filter that removes nothing before depth d. It
ignores what the filter costs, so a real gain is smaller still. A filter that
also acts earlier is bounded by the ceiling at its earliest depth, not its
latest.

## Where the tests bite

Two measurements on generated 16x16 boards with the official colour census
(toy boards, never Eternity II progress) put the checks on that axis.

**Arc consistency.** Run alone, with no search, on prefixes sampled from the row
scan at each depth. This follow-up was **not independently checked**, and the
engine was changed after the experiment it extends was judged. It covers 15
boards, four scan directions each (60 trees).

| Free depth | 96 | 112 | 128 | 144 | 152 | 160 |
|---|---|---|---|---|---|---|
| Sampled wrong prefixes still consistent | 0.427 | 0.096 | 0.179 | 0.064 | 0.007 | 0 |
| Refuted (percent, derived) | 57 | 90 | 82 | 94 | 99 | 100 |

It never refuted the true prefix. The coarser observation in the main
experiment, which was independently reproduced, covers 192 board-direction rows:
arc consistency refutes every sampled prefix in 189 of them at depth 160 and in
all 192 at depth 176. The share unrefuted counts sampled prefixes, not work, so it
is not the saving. The saving priced for arc consistency is about 5.5 bits of
nodes, while one check costs about 13 bits per node (not independently checked), so it does not pay.

**Colour census.** A statistic of the multiset of used tiles and the frontier
colours (a first-moment estimate of the number of completions, 33 ns per
evaluation) tilts toward the planted prefix by about 2 standard deviations at
depths 144 and 160 (48 boards; +1.96 [1.53, 2.42] at 144). This one is
**independently re-checked**. It is what a size-bias model predicts, times 1.5 to
1.8. As a prune at depth 144 on one scan direction it gains 1.02 bits [0.72,
1.27], against a ceiling of 2.35 there. With two directions the gain is -0.04
and with four -1.88. The values printed at depths 96 and 128 rest on too few
effective samples and are not gains. No transfer to the real pieces is claimed.

## What it means for a full solution

The ceiling at 144 is 2.4 bits and the measured gain there is about 1. Against a
gap of 84 bits for a modest run and 56 to 73 bits for the hub's two budgets, a late filter is a constant factor (2 for 1 bit, 5 for the 2.4-bit
ceiling), and the largest gain priced anywhere is about 5.5 bits of nodes. The tests that
refute nearly all wrong boards act in the thin tail of the tree. A filter that
paid would have to bite before depth 96 (17.1 bits of ceiling) and cost almost
nothing; none was found, and arc consistency on the generated boards leaves
43 percent of depth-96 prefixes standing.

The same table prices one loophole: a coarse stratified colour prior (quadrants)
would be worth 23.6 bits under row scan in a first-moment model. That is derived,
nothing was measured on the real pieces, and it stays closed. See
[approaches priced out](/research/lab/experiments/raphael-anjou/full-solve/approaches-priced-out/).

## What was not run

- No filter was built that bites before depth 96 on the real pieces.
- Both tilts and shares come from generated boards with a planted solution; the
  real puzzle's prefix is unknown.
- Pruning at several depths at once was not measured.
- Depths beyond about 190 are not measured; the sampler's population dies there,
  and the profile argues the tail is negligible (10^-4 of the total).

## Reproduce

```
just experiments approach-pricing
```

This reprints the ceiling table in seconds. The census and arc-consistency
numbers reproduce with `just experiments prefix-statistics analyze` and the
`ac_followup.py` script in that folder.

## Related

- [The price of a full solution](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/): An exact search of the 16x16 with five clues costs about 2^134.4 nodes, and no route examined closes the 56 to 73 bit gap against budgets of 2^78 and 2^61.5 nodes. The work is parked, with stated conditions for reopening. This page holds the fixed numbers and indexes the ten pages behind them.
- [The price of a full search](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/price-of-a-full-search/): Exhausting a plain row-scan search of the real Eternity II pieces with five clues takes about 10^40.457 nodes (2^134.4), measured, and the random-model prediction lands within 0.04 digits of it. The official piece set is an ordinary member of the boards painted with the same colour counts on this statistic. This prices the full search; it finds no way to shorten it.
- [Seven families of approaches priced out against the row-scan tree](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/approaches-priced-out/): None of seven families of approaches (search that learns, lossy representations, the shape of the tree, adaptive orders, tile-set structure, algebraic and search-space reformulation), nor the far ideas, frame nogoods or alternative fill orders, is priced at 10 bits or more with a mechanism behind it. The largest surviving gain is about 5.5 bits, against a gap of 56 to 73 bits; a few closures rest on one reader or one solver family and are marked as such.
- [What a known tile is worth under row scan](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/worth-of-a-known-tile/): Under a row scan, one known tile removes between 1 and 10 bits of the full search tree depending only on where its cell sits in the scan (median 5.8 bits, on painted 16x16 boards), and several tiles together are worth less than the sum. On those boards, 10 spread tiles leave the tree above 10^15 nodes and 16 to 24 bring it under, a figure checked end to end only. Nothing here is a measurement of the real puzzle beyond two transfer checks.
- [Clause learning against propagation: a negative result](https://eternity2.dev/research/lab/experiments/raphael-anjou/full-solve/learning-against-propagation/): Clause learning gave no growing lead over plain arc-consistency propagation on wrong prefixes of the real pieces: the pre-stated stop line fired on summed work, and in counts learning is worth 0 bits over arc consistency. The toy boards (5x5 to 7x7) lean the same way but do not establish it. Nothing here is Eternity II progress.
- [Records & solvers](https://eternity2.dev/research/records/): Eternity II has never been solved, but nearly two decades of community effort have pushed the best board to 470/480. Who holds what, how they did it, and why some headline "480" boards are not actually the real puzzle.
- [Open problems](https://eternity2.dev/research/open-problems/): The open frontier of Eternity II in one place: every angle still worth a run, the wall it attacks, what has been tried and where it stopped, and whether it is a newcomer-tractable target or a hard, well-mapped one.
- [Dead ends and untested claims](https://eternity2.dev/research/build/dead-ends/): Approaches that did not move the score on Eternity II, each graded by the strength of its evidence. Twenty verdicts rest on committed data, a named public report or a derivation; twenty-two more are stated without evidence a reader can open, and are listed separately with the experiment that would settle each, and one measured negative result on clause learning.
