Predictive Algorithms
A short book and a small C99 library on trails, sparse sets, constraint solving, and exact cover.
About 1800 lines of C99 · about 50 pages
Predictive algorithms make tentative commitments, propagate the consequences, and walk back when a branch fails. The book explains four pieces of infrastructure that share this shape — a trail, a sparse set, a finite-domain constraint solver, and a Dancing Links exact-cover solver — and the library implements them in under two thousand lines of C99 you can read in an afternoon.
Every algorithm in the book has working code in the library. Every chapter ends with something you can compile.
In the library
trail — 80 lines
A flat array of (address, old value) pairs. trail_mark() snapshots the current length; trail_restore(mark) rolls back every save newer than the mark. O(k) restoration in the number of changes since the mark, never proportional to state size.
Briggs sparse sets
A two-array structure for sets drawn from a small known universe. O(1) membership, O(1) removal, dense iteration, no zero-fill. Exactly three word-writes per mutation — which is what keeps the trail tight.
CSP — about 1000 lines
Finite-domain constraint solver. Watch-list propagation to fixpoint, depth-first search with first-fail branching. Built-in constraints: neq, eq, alldiff, table constraints, and bounds-consistent linear arithmetic.
DLX — about 650 lines
Dancing Cells exact-cover solver with primary items, secondary items, and XCC colours. The doubly-linked node structure carries its own undo information — no separate trail, just inverse pointer rewiring on the way out.
A taste of the API
/* SEND + MORE = MONEY in a dozen lines. */
csp_t *csp = csp_new();
var_t S = csp_var(csp, 0, 9), E = csp_var(csp, 0, 9);
var_t N = csp_var(csp, 0, 9), D = csp_var(csp, 0, 9);
var_t M = csp_var(csp, 0, 9), O = csp_var(csp, 0, 9);
var_t R = csp_var(csp, 0, 9), Y = csp_var(csp, 0, 9);
var_t vars[8] = { S, E, N, D, M, O, R, Y };
int32_t coeffs[8] = { 1000, 91, -90, 1, -9000, -900, 10, -1 };
csp_alldiff (csp, vars, 8);
csp_linear_eq(csp, vars, coeffs, 8, 0);
csp_neq_c (csp, S, 0);
csp_neq_c (csp, M, 0);
csp_solve(csp, print_cb, vars); /* finds 9567 + 1085 = 10652 */Worked tutorials
Each tutorial in the book ships with a complete program in the library. Compile it, run it, modify it.
CSP examples
- Cryptarithmetic — SEND + MORE = MONEY
- Graph colouring on the Petersen graph
- Bin packing with linear arithmetic
- Magic squares, scheduling, register allocation
DLX examples
- Sudoku — the canonical exact-cover puzzle
- N-queens with secondary items for diagonals
- Pentomino tiling
- Crossword filling using XCC colours
Building
$ unzip predictive-algorithms.zip
$ cd predictive-algorithms
$ make # build all demos and tests
$ make test # run the unit tests
$ ./csp_cryptarithmetic
$ ./dlx_sudoku- C99 compiler (clang or gcc)
- POSIX
make - No external dependencies, no build framework
- macOS, Linux, BSD — anything POSIX