Skip to content
Eternity II

Backtracking

Depth-first search done seriously: fill orders, candidate ordering, break indices, restarts. This is the family behind every record backtracker.

Why it's hard

finding
Why a faster computer doesn't help
finding
Complex theory: counting the search before you run it
finding
Where you place the hints beats how many

Build a solver

reference
The community's benchmarks
page
How the record solvers search
concept
Fill orders
concept
Restarts and heavy tails
concept
Distributed solving: swarms, syndicates, and core farms
concept
Decoding records
reference
Reference numbers

The lab

experiment
Single-core benchmark
experiment
CSP presets, measured
page
The reference engine behind this site
experiment
REPLAY
experiment
The JIT backtracker: portable Rust that ties hand-tuned C on hard boards
concept
Going fast: when a solver spends its budget on speed
experiment
CLOISTER
page
The DFS study
page
How the study is built
page
What each idea buys
page
The hint study
page
How the study is built
page
What the study found
experiment
McGavin's C backtracker: the throughput story, built here
experiment
Blackwood's solver, decoded and run here
page
Verhaard's eii: the solver that won the only prize

Neighbouring roads

All nine roads
Reduce the search

Throw away hopeless states before the search wastes time on them.

Go faster

Bit tricks and cache, and why raw speed alone won't crack it.