Strip any record solver to its skeleton and you find the same loop: place a
piece, check the edges, back up when stuck. The algorithm was settled by
2007. What the community has actually been competing on for twenty years is
the layer below the algorithm: the craft that decides whether visiting one
node of that tree costs about 26 clock cycles, as Mike Field measured on his
own engine (message 9003), or
a hundred times that in a naive interpreter. Same tree, same search, two
orders of magnitude apart in placements per second.
This page collects that craft, technique by technique, each with its primary
source in the mailing-list archive. The chronology of how one engine
compounded them for two decades is told on the
McGavin page; the anatomy of the engine
behind the record boards is on the
Blackwood page. Here is the shelf they
both draw from.
Every fast backtracker shares one load-bearing idea: never search for
candidate pieces, look them up. Fix the
fill order (a row scan, usually), and
each cell exposes exactly two known constraints when its turn comes, the
colour on its north edge and the colour on its west edge. So you precompute a
table keyed by that colour pair, and finding all pieces that could legally go
in the current cell becomes a single memory access. Field's 2007 recipe put
it first in the list, together with its corollary: a fixed search order
is what makes the two-edge key possible at all, and placing a piece then only
updates its south and east neighbours
(message 3098). The same
design was being dissected the same year around Marc Lebel's public C++
solver, the era's reference fast backtracker, in the thread that doubles
as the community's first engineering seminar
(message 1704).
The 2007 recipe holds a third table shape that is easy to miss: for the cell
directly above or beside a mandatory hint piece, key the lookup on three
edges (north, south, west), so candidates are pre-filtered against the
hint's fixed colour, at zero completeness loss
(message 3098). I rediscovered
why that variant matters two decades later, in my own notebook: on a hinted
board, the cells surrounding one hint turned out to be a throughput sinkhole,
with threads churning ~85M placements per second against the hint wall for
twenty minutes; the fix was exactly Field's three-edge table. The archive
already contained the answer.
Everything else on this page is a refinement of that table: making it
smaller, making its entries denser, or unrolling the code around it.
The lookup table has a size problem when you key on more than two edges. In
the Lebel thread, Nathan described the brute-force version: a 4-D array
indexed by all four edge colours, combo4[32][32][32][32]. A million
entries, mostly zeros, guaranteed cache misses. His fix adopted the
minimal-perfect-hash generator (Bob Jenkins's) that another member had
pointed the list to. Since the
256 pieces in 4 rotations produce only 1,024 distinct edge-quadruples, a
minimal perfect hash maps the packed 32-bit key to a 1,024-entry table with
no collisions: "small enough to fit in cache most of the time", with
near-zero hashing overhead, and absent keys simply read a count of zero
(message 1831). A million
entries down to a thousand, purely so the working set lives in L1. He drew
the boundary himself: the four-edge table only earns its keep when
the fill order can leave holes; a strict scan-line solver never needs it.
Field's cycle budget explains why so much of this craft is about memory
layout: at 75M tiles per second per core, over half the time was stalled on
memory access, not computation
(message 9003). The response
is to make every byte the search touches count. Pack a piece's four sides
into a single int (message 3098).
Keep the used-piece set as one 64-bit word per group and early-out a whole
candidate loop with a single mask test, an optimization Arnaud Carré and
Adam Miles discovered they had implemented independently, line for line
(message 9808,
message 9809). Size the
candidate-table entry so the whole table fits in cache. That is exactly
the design of Blackwood's six-byte RotatedPiece struct, already told on
the Blackwood page: piece number,
rotation, the two exposed sides, a break count and a heuristic count, and
nothing else.
These tricks still compound in 2026. On an otherwise identical plain
depth-first engine in my notebook, three micro-changes of exactly this family
added up to +27% (92–93M vs 72–73M placements per second, stable across
3, 5, 10 and 15 second budgets; one engine, one puzzle, one machine, so read
it as a shape rather than a universal constant). One:
sentinel-terminated candidate lists, ending each candidate bucket with an
impossible value so the scan needs one load and one compare instead of a
bounds counter, freeing a register. Two: the used-piece set as u64 bitset
words instead of a byte per piece; same byte count, but the test is a
single AND and the whole set sits in one or two cache lines. Three: a
single resume cursor per depth instead of a start/end pair, halving
backtrack bookkeeping. And the craft is not backtracker-specific: in a
constraint-propagating solver that keeps full per-cell candidate domains,
switching those domains to u64 bitset words turned arc-consistency revision
into a handful of word operations and bought +48 to +101% depending on the
propagator mix, with follow-on layout work (a precomputed rotation table,
O(1) piece lookup, arena-based undo) compounding to ~4.6× on the lightest
profile. Single-seed throughput readings, and a propagating solver does far
more work per node than the fast walkers on this page, so carry the ratios,
not the absolute numbers. The lesson carries whole: the domain
representation is the engine.
If one lookup gives you candidate pieces, why not precompose pairs into 1×2
"bipieces" and place two cells per node? Measured on Lebel's code in
August 2007, it worked: about 20–30% faster
(message 1734). But the trade
is steep and the archive documents both sides. Going to 2×2 blocks, one
member measured roughly 4.2× slower and rejected bigger pieces outright
(message 1730). No surprise
once the tables are counted: about 4 million distinct inner 2×2
combinations (message 3044).
Louis Verhaard reported bipieces helping "only very marginally" in his own
fast backtracker
(message 3061).
And in 2008 the list settled the theory question underneath: a metatile
solver visits essentially the same constraint frontier as a 1×1 solver
("in sync every 4 pieces"), so the gain is implementation-level, never a
reduction of the search space
(message 5842,
message 5899). Precomposition
is a speedup you buy with memory, and past 1×2 the price goes negative.
The inner loop's last indirections ("which cell am I on? what are its
neighbours?") can be removed by not having a loop at all. Field's recipe:
procedurally generate monolithic straight-line code, one block per cell,
each block knowing its own neighbours as constants; his generated code
compiled to about 33 instructions per cell
(message 3098). The idea
spread fast: by mid-2008, istarinz was generating a non-recursive C solver
per puzzle and per fill path, compiled with the Intel compiler
(message 5480,
message 5438), in the same
season the list compared notes on non-recursive backtrackers generally
(message 4683). Peter
McGavin's body.c is this idea compounded for twenty years: labelled
blocks like cell_9_2_next:, goto chains back into the previous cell on
exhaustion, the whole file regenerated for every puzzle and hint set
(message 11337,
message 11782). And it works
across languages: Jef Bucas's libblackwood, a Python generator emitting C,
made Blackwood's C# algorithm roughly twice as fast on the same machine
(message 10065,
message 10078).
The recipe also reproduces in a modern, mostly-safe language. In my
notebook, a Rust procedural macro expands the search loop into 256
per-cell specialised arms, with row, column and border facts becoming
compile-time constants: measured +21% alone, +25% combined with
profile-guided optimisation, and +30 to 35% once per-schedule constant
tables are folded in (spread ±1% across 4 runs; correctness gated on
identical maximum depth and score). The analytical estimate beforehand was
+5 to 10%; the surplus came from per-arm branch-prediction specialisation
and code layout, not from the constant folding itself. The bill: compile
time went from 5 seconds to 41. Field's recipe already flagged the cost
side in 2007: monolithic generated code loses about a third of its edge on
large working sets because the instruction cache overflows
(message 3098), which matches
that measured experience; part of what codegen buys is layout, and layout
is exactly what an overflowing I-cache takes back.
Below the source code, there is still throughput to harvest, in
instructions and flags rather than ideas. Adam Miles took his solver from 78 to 90
million placements per second with BMI's bextr and BMI2's pext
bit-extract instructions, while noting it was "getting increasingly
difficult" to reach further
(message 9796). McGavin's
2026 playbook is the accumulated folklore: try clang, icc and icx against
gcc; try versions (clang-15 beats clang-19 on his ARM boards); add
-march=native and -mtune=native; use profile-guided optimisation. None
of these tips is a silver bullet
(message 11751). His counter
trick from the same post is the genre in miniature: the 64-bit placement
counter is fed by a 16-bit register that rolls over, adding 0x10000 at a
time, because he timed both ways years ago on 32-bit hardware and the trick
won.
The playbook's PGO line can be given numbers. Measured on three Rust engines
in my notebook, on the same workload and machine, profile-guided
optimisation gained +14%, +12% and +4% (one workload per binary, so
these are single-workload figures), and the size of the gain tracked how
many unpredictable branches each inner loop had left for the compiler to
lay out; the standard references are the
Rust performance book
and the rustc PGO documentation.
Two practical notes travel with those numbers. The training run must be
representative: a PGO build trained on one branch pattern can come out
slower than the baseline out of distribution. And the post-link
optimisers the playbook points at next
(BOLT, via cargo-pgo)
handle ELF binaries only, so they are Linux-only in practice; anyone
following the community playbook on a Mac stops at PGO.
The same realism applies to hardware. Multithreading scales the obvious
way: multi-core solvers broke 100M placements/s in 2008
(message 5804), and a single
Core i7 hit 558M/s that December
(message 6212). Single-core
progress, though, mostly stopped. Posting his 2025 table of nine
CPU/compiler combinations (38–84M placements/s), McGavin noted that speeds
on the latest CPUs "are only a little faster" than on his 2010 Phenom II
(message 11643). The engines
hit Field's memory wall fifteen years ago and have been leaning on it since.
Field's cycle budget opened this page from 2007. Here is the remake from my
own notebook, on an Apple M1 performance core
(128-byte cache lines, 128 KB of L1 data cache;
the M1's latency tables are the
modern version of the numbers Field was fighting). One node of my unpruned
Rust backtracker costs about 90 to 145 cycles: clean, uncontended
readings, quoted as a range because a loaded machine pushed the same binary
well above it. The surprise is where the cycles go. The edge-checking
arithmetic is effectively free. The node is dominated by walking
already-used pieces off the candidate list: about 6.7 candidate reads per
node, of which about 5.9 (88%) are rejected solely because the piece is
already on the board. Each rejection is one L1 load plus a data-dependent
branch; the whole reject loop is ten instructions and a single load.
Three cross-checked instruments put the retired-instruction floor at about
75 to 90 instructions per node, which at the core's peak issue rate would
be roughly 12 to 15 cycles. The measured 90 to 145 sits 7 to 10× above
that floor, and the gap has one name: branch misprediction on the
used-piece test, whose outcome depends on which pieces the search has
placed and therefore cannot be predicted. In 2007 the wall was memory;
Field measured half his cycles stalled on loads
(message 9003). On the
2020s' wide out-of-order cores with generous L1 caches, the wall has moved
to branch entropy.
One more measurement completes the anatomy. Turning on a sound feasibility
prune of the kind record engines run multiplies the node cost roughly
13–24×, to about 2,180 cycles per node: the prune's test is invoked
about 8 times per node and, by rejecting candidates, forces the scan
roughly 10× deeper into the list (candidate reads jump from 6.7 to 67.6
per node). It is still overwhelmingly worth it, because the prune buys
orders of magnitude fewer nodes to the same depth. That is
the prune-versus-speed argument caught in
a single cost table: the engine deliberately runs ~15× slower per node
because nodes × cost-per-node is the product that matters. (Methodology:
node counts are bit-identical run to run, the checksum discipline described
below; throughput figures are medians over 7 repeats; one machine, one
board regime, so scope every number accordingly.)
With the anatomy in hand, the next question is what a rewrite recovers. I
rebuilt the hot placement kernel six ways in an isolated lab: packed
candidate entries, software prefetch, strict/relaxed loop splitting,
software pipelining, compacted side tables, and combinations, under one
hard rule: a variant's timing only counts if it reproduces the production
engine's exact node count, maximum depth, and a rolling trajectory hash
folded over every (depth, piece, rotation) commit. That gate is the
stronger sibling of the community's node-count checksum (it is also how the
portable-Rust experiment
below verifies its rungs); no speedup from quietly changed semantics can
slip through it. Every number here passed. The total for a semantics-exact
scalar rewrite: 1.2 to 1.4× robust, about 1.8× peak in the most
favourable region. Not 10×.
The load-bearing result is a negative. The two "obvious" cache
optimisations were near-null: packing colours into the candidate entry, to
kill two table gathers, gained 1.0 to 1.2× and sometimes regressed;
shrinking the 64 KB side tables to a 1 KB L1-resident form gained at most
1.26×. That is proof by null that the loads were already cache-served. The
residual cost is the mispredicting used-piece branch, and every variant
that preserves the search's exact trajectory must keep that branch. The
only variants that helped restructured control flow around it (loop
splitting, software pipelining), which is why they cap at 1.2 to 1.4× and
do not stack: they attack the same residual. A first attempt at a
bitset-based candidate stream on this design measured 16 to 25% slower,
same scoping.
The batching escape hatch got its trial too: fusing two horizontally
adjacent cells into one "domino" step, verified to produce identical
completion sets, exhaustively, up to 3,171-way branching. It bought 1.05
to 1.13× in a regime where 74% of cells could fuse, and was net neutral
(0.96 to 1.03×) in the regime the record-style search actually runs, where
only 27% fuse. The mechanism explains the ceiling: batching amortises the
per-cell loop shell, about 7% of a node, but the dominant used-piece scan
is per-cell-irreducible; the second cell still walks its own bucket
against the live used set, which no static pair table can encode. Sketched
arithmetic says larger blocks hit the same wall, though that extrapolation
is untested beyond pairs.
All of this is one engine design, one instruction set, one puzzle regime;
the fair phrasing is that for this design on this hardware, the scalar
ceiling is about 1.5 to 2×, and the wall has a name. Whether a
mispredict-free SIMD candidate stream can go further is an open direction,
not a result.
An engineering culture is only as good as its benchmarks, and the archive
had to build that discipline the hard way. In January 2008, comparing speed
claims forced the definitional question: Txibilis counted a node as every
valid piece committed to the board, no lookahead
(message 3843); others
counted attempted placements, or steps, and the thread concluded that a
metric everyone agrees on may not exist
(message 3946). The question
came back in 2017 and got the standard answer: the community's
"pieces per second" counts pieces placed per second, chess-style
(message 9739,
message 9740). The standard
objection came with it: the metric flatters scan-line fill orders and
says nothing about search-space coverage per unit time
(message 9746).
Two practical consequences. First: never compare two solvers' M/s figures
without checking what they count: a "faster" solver may simply have a more
generous definition. Second, the positive habit that grew out of it: publish
node counts alongside timings. A deterministic backtracker walking a
fixed tree must count the same nodes on any machine, so exact node counts
became the community's checksums, the way ports, rewrites and new hardware
prove they search the same tree before their speed means anything.
There is a third confusion worth naming once and for all, because it recurs
whenever these numbers reach a wider audience. "Fast" points at three unrelated
quantities, and no two of them convert:
- Placements per second (equivalently pieces/s or nodes/s) - how fast the
search walks, and it depends on the board as well as the engine. McGavin's C
does ~287M on an easy board but ~105M on a hard one; a
portable-Rust engine on this site
reaches ~110M on the same hard board - a tie there - and ~122M on the easy one.
- Matched edges out of 480 - how good a board is. This is the axis the
records live on (the ceiling is 470). It is independent of
walking speed: a slow engine routinely finds a better board than a fast one.
- Aggregate placements per second - a fleet total, many machines summed. The
"~300M/s" figure sometimes pinned on a single engine is in fact the
Eternity 2 Syndicate swarm, roughly
twenty machines added together, not one core.
A high number on the first axis says nothing about the second, and the third is not
an engine speed at all. When this site quotes a throughput, it is always
placements/s on one core unless it says otherwise; where the trade-off between
spending a solver's budget on speed versus on judgement is the point, that argument
lives on going fast.
The discipline extends below the benchmark, into the optimisation loop
itself. A profiling pass over my propagation-heavy solver (a sampling
profiler with inline-frame resolution) shipped seven flamegraph-directed
fixes worth +22 to 27% overall, each measured on its own: fusing an
emptiness check into the bitset loop was +27.5% on the lightest profile,
replacing a materialised work list with a stack bitmap walk +7%, a
popcount-based counter rebuild +4.3%. Meanwhile five statically
predicted optimisations were refuted by the same profile: each a
textbook 1 to 5% win on paper (inline hints, snapshot reuse, dispatch
lifting, struct reordering, a manual unroll), each either absent from the
top 200 samples or measured neutral, because the compiler was already
doing them. One fix was pure measurement hygiene: the timing call itself
was 12.4% of runtime at a 1-in-64 deadline-check rate, and throttling
the check to 1 in 4096 recovered it, the masked-deadline-check pattern in
its purest form.
Cache arithmetic without a profile misleads the same way, in both
directions. Replacing a 1 MB flat lookup table with a 16 KB L1-resident
compact one, predicted to be worth ~20% from latency arithmetic, measured
0% with a slight regression (three 10 second runs): the keys actually
touched clustered and were already cache-hot. panic = "abort" likewise
measured null once the hot loop had no panic edges left. These are
single-seed, single-machine, engine-specific percentages; the durable
pattern is that roughly half of the expert static predictions were wrong,
in each direction, and the flamegraph arbitrated every dispute. Measure,
don't model.
| Technique | What it costs | What it bought | Source |
|---|
| Per-position candidate tables (two-edge key) | memory for tables; a fixed fill order | candidates in one memory access, the baseline every fast solver shares | 3098 |
| Minimal perfect hashing | offline hash construction | 1M-entry lookup → 1,024 entries, cache-resident | 1831 |
| Bit-packing, cache-sized structs | code contortions | fewer stalls where >50% of time is memory; 64-bit used-mask early-outs | 9003, 9808 |
| Bipieces (1×2 precomposition) | tables grow fast; no search-space reduction | +20–30% at 1×2; ~4.2× slower at 2×2 | 1734, 5899 |
| Code generation (per-cell straight-line code) | a build pipeline; regenerate per puzzle | ~33 instructions/cell (2007); ~2× from libblackwood's C (2020) | 3098, 10065 |
| BMI/BMI2 bit-extract instructions | portability | 78 → 90M placements/s | 9796 |
| Compiler shopping, native flags, PGO | trial and error, per machine | "significant" but unquantified single-digit-percent-to-tens gains | 11751 |
| Counter tricks (16-bit rollover feed) | obscurity | measurable only on 32-bit-era hardware | 11751 |
Now zoom out. Field's 2007 recipe already did 60–80 million placements per
second per core (message 3098).
Twenty years of craft since have widened that range rather than uniformly
multiplied it. On portable code the gain is modest, though the two 2025
figures are not on the same puzzle: 72.7M/s from a tuned C++ solver on an 8×8
board and 68.4M/s from a Rust descendant of Blackwood's on 16×16
(message 11633,
message 11634), barely above the
2007 baseline. The ~4× only appears with per-cell generated C on the newest
hardware: around 225–295M/s for McGavin's on small puzzles
(message 11751 notes the rate
roughly halves on 16×16, the size E2 actually is;
message 11750), so it mixes a
codegen gain with a hardware gain, not craft alone. Over the same twenty years,
the record moved three edges: 467 to 470.
My own notebook replayed that twenty-year ledger in one afternoon. This
site's first solver was propagation-heavy and walked about 370k placements
per second; the community's generated-C record engine does about 295M on
comparable hardware, an 800× gap. Porting the C engine's shape into
safe-leaning Rust (border-aware flat candidate tables, a four-word
used-piece bitset, sentinel-terminated candidate lists, per-depth
precomputed flags) closed about 180× of it in a day: 65 to 68M placements
per second single-thread, median 67M over 4 seeds with about 5% spread, on
one machine, landing at ~22% of the C engine before any per-cell
specialisation. At that stage the port had not been verified to walk the
identical tree, so read it as a throughput-shape result rather than a
verified port; the verified comparison is the experiment below. But the
lesson already stands: every technique in that port is one on this page's
shelf, the shelf applied together is the hundred-fold, and the gap was
architecture, not language. (Those 65 to 68M are this notebook's engine;
the community's 68.4M Rust figure above is a different program, a
coincidence of ranges.)
A 2026 experiment on this site
separates those two gains directly. It takes a portable, safe Rust backtracker
and applies the same craft - per-cell generated code, packed cells, a byte-array
used-set, cell fusion - then measures it against McGavin's C on one machine, same
board, both built headless, back to back. Holding the hardware fixed, the portable
engine ties the C on hard, deep boards (≈105–110M search-nodes/s each) while the
C stays ~2.3× faster on easy low-branching ones (≈287M vs ≈122M) - every rung verified
to walk the identical tree. The lesson cuts both ways: the codegen craft is real and
reproducible in a modern language - enough to match hand-tuned C where the search is
hard - and it is still only the constant factor this page keeps describing. The same
engine, pointed at the real puzzle, plateaus in the high-300s of 480, exactly where
speed alone always leaves you.
Two more notebook measurements close the accounting. First, the constant
factor caught in the act: a +25% single-thread throughput gain from
per-depth generated code did not change the board quality reached at a
fixed 5 minute multi-thread budget. Identical partials at 444 of 480
matched edges, and the same 450 to 451 matched edges after a repair pass,
stable across 3 seeds with about 0.5% spread (one machine, one budget
point; matched-edges scoring, and see the records page
for how any such number sits against the community's). The search converges
on the same trajectory; faster walking only reaches it sooner. Second, the
multithreading caveat 2008 never had to face: on an 8-core part with a
shared memory system, 4 threads ran at 52M placements per second each
while 8 threads dropped to 22M each, a near-flat aggregate, and both
reached the same score at the same budget. Multithreading scales the
obvious way until the memory system saturates.
The practitioners said it themselves. Joshua Blackwood, cataloguing his dead
ends after the 469 (SAT solvers,
GPUs, cached 2×2 blocks, all measured
and dropped), found that only refining the heuristics ever paid, worth another
~2× (message 10056). And
when the 2025 speed thread wound down, Razvan wrote its epitaph: regardless
of how fast we can check, "we will not make a dent" in the E2 search space
(message 11657). The craft
on this page is real, measurable and worth learning; it is why a hobbyist
farm can walk 10¹⁷ nodes. But a constant factor is a constant factor.
Why shrinking the tree beats speeding up the walk
is the arithmetic of that sentence; this page is its engineering ledger.