# Predictive Algorithms

A small C99 library implementing four pieces of combinatorial-search
infrastructure, with a tutorial book that explains them.

## What's in this package

```
.
├── Makefile                       build everything with `make`
├── README.md                      this file
├── src/                           library and example sources (~1800 lines C99)
│   ├── trail.{c,h}                trail: cheapest-possible undo log
│   ├── csp.{c,h}                  finite-domain constraint solver
│   ├── csp_naive.c                  reference implementation (AC-3 fixpoint)
│   ├── dlx.{c,h}                  dancing-links exact-cover solver
│   ├── csp_*.c                    CSP demos and tests
│   ├── dlx_*.c                    DLX demos and tests
│   ├── bench.c                    benchmark harness
│   └── *_test.c                   unit tests
├── practical-book/                the tutorial book in plain TeX (~97 pages)
│   ├── typesetting.md             how the book is built and what it overrides
│   ├── book.tex                   entry point with book-local extensions
│   ├── build.sh                   two-pass xetex compile -> book.pdf
│   ├── add-crops.sh               adds crop marks -> book-crops.pdf
│   ├── macros/                    plain-TeX macro library
│   └── chapters/                  preface, four parts, fifteen chapters
└── md-book/                       original Markdown source, kept for reference
    └── predictive-algorithms.{md,pdf}
```

## Quick start

```sh
make            # build all demos and tests
make test       # run the unit tests
./csp_cryptarithmetic   # solve SEND + MORE = MONEY
./dlx_sudoku            # solve a sudoku via Dancing Links
```

To run the benchmarks:

```sh
make bench
./bench_naive
./bench_queued
```

## Reading order

If you're new to this material, read the book in `practical-book/`
first — it walks you through the four pieces in order, with worked
tutorials for cryptarithmetic, graph colouring, bin packing, sudoku,
and n-queens. After the book, the headers (`src/csp.h`, `src/dlx.h`,
`src/trail.h`) are the API reference; the example programs in
`src/csp_*.c` and `src/dlx_*.c` are the practical guide.

The book references the source code throughout; you can read either
one first, but the prose is most useful with the source tree open
beside it.

To rebuild the book from source:

```sh
cd practical-book
./build.sh              # writes book.pdf at 7.5x9.25" trim
./add-crops.sh          # writes book-crops.pdf for press
```

The book is self-contained: the plain-TeX macro library lives in
`practical-book/macros/` and is loaded directly by `book.tex`. See
`practical-book/typesetting.md` for the macro reference and a
description of the book-local extensions in `book.tex`.

## Library overview

### `trail.{c,h}` — 80 lines

A flat array of (address, old-value) pairs that records word-sized
mutations as they happen. `trail_mark()` snapshots the current length;
`trail_restore(mark)` rewinds every save newer than `mark`, replaying
old values in reverse. O(*k*) restoration where *k* is the number of
saves since the mark, regardless of how big the underlying state is.

This is the foundation everything else is built on.

### `csp.{c,h}` — about 1000 lines

A finite-domain constraint solver. Variables have integer domains
stored as Briggs sparse sets (O(1) membership, removal, and dense
iteration). Constraints are propagated to fixpoint via a watch-list
queue (AC-3-flavoured); search is depth-first with first-fail variable
selection.

Built-in constraint types:

```
csp_neq(x, y)              x != y
csp_eq(x, y)               x == y
csp_neq_c(x, c)            x != c
csp_eq_c(x, c)             x == c
csp_alldiff(vars, n)       pairwise distinct
csp_allowed_pairs(...)     binary tuple whitelist
csp_forbidden_pairs(...)   binary tuple blacklist
csp_linear_le(...)         Σ coeff·var ≤ bound (bounds-consistent)
csp_linear_eq(...)         Σ coeff·var == target (bounds-consistent)
```

Search via `csp_solve` (with a callback per solution); pure propagation
without search via `csp_propagate`.

### `dlx.{c,h}` — about 650 lines

A Dancing-Cells exact-cover solver supporting primary items
("must be covered exactly once"), secondary items ("at most once"),
and XCC colours ("multiple options may share a secondary if they
agree on a colour value").

```
d = dlx_new()
for each item:    dlx_primary / dlx_secondary
for each option:  dlx_option_begin / dlx_option_add ... / dlx_option_end
dlx_solve(d, callback, ud)
```

Same lifecycle and callback shape as the CSP API. The standard
sudoku, n-queens, and polyomino-tiling encodings are in
`src/dlx_sudoku.c`, `src/dlx_queens.c`, `src/dlx_pentomino.c`.

## What's deliberately not here

- **Optimisation.** The solver counts and enumerates solutions; it
  does not maximise an objective directly. Run `csp_solve` with a
  callback that compares each solution to a running best, return 0
  when an upper bound is reached. Standard technique, no built-in
  helper.
- **Strong all-different.** `csp_alldiff` decomposes to pairwise
  disequality. The matching-based version (Régin's algorithm) is
  stronger but considerably more code.
- **Reified constraints, soft constraints, weighted CSP.**
- **Distributed / parallel search.** Both solvers are single-threaded.

These omissions are deliberate. The code base is small enough to
hold in one head, and that property is worth preserving.

## License

Copyright © 2026 by Streck.ai. All rights reserved.
