Faster Search: Flattening State and Backjumping

In the first two posts of this series, I packed live domains into bitsets and moved constraint propagation to bulk bitmasks. Once those stopped dominating the CPU profile, the spotlight moved to everything wrapping the propagation loop: variable map lookups, mutexes, undoing prunings, and backjumping state.

I touched on backjumping briefly when I first introduced the solver, without really getting into how it works. Since a good chunk of this post is about making backjumping fast, let’s start there.

In plain backtracking, whenever a variable’s live domain wipes out (hits 0 remaining candidates), search always steps back to the most recent decision, even if that decision had nothing to do with the failure. On a crossword grid, that gets wasteful fast. Suppose search places 1-Across = “como” in the top-left corner at depth 0, moves over to the bottom-right corner to place 25-Across = “crane” (depth 1) and 28-Down = “orbit” (depth 2), and then returns to the top-left at depth 3, where 6-Across wipes out 2-Down:

Plain backtracking vs. conflict-directed backjumping Plain backtracking vs. conflict-directed backjumping

Plain backtracking steps back to depth 2 and tries other candidates for 28-Down, then steps back to depth 1 and tries other candidates for 25-Across - exploring thousands of bottom-right combinations that all walk straight into the exact same top-left wipeout.

Conflict-directed backjumping avoids that thrashing by tracking which earlier decisions actually caused each candidate to be pruned:

  • Whenever a decision or constraint propagation prunes a value from a variable’s domain, search attaches a nogood to that pruned value: the set of tree depths whose decisions ruled it out (for instance, {0} when depth 0 pruned “ibex” from 2-Down, and {3} when depth 3 pruned “onyx”). There’s a bit more to what a nogood actually is, which I’ll get to further below.
  • Each variable stores the nogoods for all of its currently pruned values in a conflict set, removing a value’s nogood whenever backtracking restores that value.
  • When a variable wipes out, combining all the nogoods in its conflict set gives every ancestor depth involved in the wipeout ({0, 3} above). Once depth 3 itself runs out of options, the only remaining culprit depth is {0} - neither depth 1 nor depth 2 played any part in the failure. Search therefore undoes depths 2 and 1 directly without trying their other candidates, and jumps straight back to depth 0 (carrying any even earlier culprit depths along in case depth 0 also runs out of options).

When a problem is constructed, variables are now sorted by name and given dense integer IDs (0 through N - 1). That one change replaces map[*Variable] lookups across the solver (for looking up a variable’s constraints, tracking which variables are queued for arc consistency, and storing per-variable state) with direct slice indexing. Replacing the propagation map with a slice queue also made arc consistency run in a predictable order instead of Go’s randomized map iteration order.

The solver’s state tracker (a listener attached to every variable that records current assignments, conflict sets, and snapshots for live UI updates) also dropped the maps it used to maintain for unbound, forced, and wiped-out variables. Previously those maps locked a mutex on every single prune and restore just so background websocket goroutines could read solver progress safely. Search now checks domain counts directly without locks, and the mutex only runs when a variable is actually assigned or cleared.

Similarly, instead of allocating a fresh map at every search node to remember what propagation pruned, search now appends (variable ID, value) pairs onto one shared slice and records each node’s starting offset. On backtrack, it walks back to that offset in reverse order before clearing the node’s own decision. Doing it in that order matters when assigning a variable immediately triggers a wipeout on that same variable: restoring the propagated prunings first clears its pruned flag while it is still marked assigned, keeping the restore and clear checks consistent.

Shared pruned-values slice Shared pruned-values slice

Strictly speaking, a nogood is a partial assignment: a combination of decisions that cannot be extended to form a valid solution, where in a binary-branching solver those decisions can also include unassignments (like A != 2) alongside assignments. Because each depth along the current search path corresponds to one active decision (assigning or unassigning a value), referencing tree depths is a compact way to represent that partial assignment. I’ll keep referring to nogoods simply as sets of depths below, since that’s how they’re implemented and it’s much more concise.

Originally, nogoods were map[int]bool sets of tree depths, and each variable’s conflict set was a map[int]*Nogood keyed by domain value. You can probably guess how merging 15,000 maps felt whenever a word in the crossword puzzle wiped out (the exact count depends on the word’s length and the dictionary).

Because tree depths are small non-negative integers (0, 1, 2, …), a nogood is now a bitset too, backed by a fixed [4]uint64 array right inside the struct:

type Nogood struct {
	depthBuckets   []uint64
	depthBucketBuf [4]uint64 // depths 0..255 fit inline with no heap slice allocation
	invalid        bool
}

Merging two nogoods is just bitwise OR across those buckets, and depths up to 255 never allocate a backing slice on the heap.

Each variable’s conflict set also swapped its map[int]*Nogood for a flat []*Nogood slice indexed by domain value (offset by the start of the domain). Recording or removing a single value’s nogood is now a direct slice lookup, though a catch remains: whenever a variable wipes out (or arc consistency propagates through its narrowed domain), search needs the combined nogood across all currently pruned values of that variable. Even with bitset nogoods, bitwise-ORing 15,000 slice entries on every wipeout adds up fast.

It’s tempting to maintain one running ORed bitset as values are pruned, except you can’t “un-OR” a bit on backtrack: a value pruned deeper in the tree can blame an earlier depth alongside its current depth. For example, suppose val 1 was pruned at depth 1 with nogood {0, 1}, and later at depth 3 a constraint involving both depth 1 and depth 3 prunes val 6 with nogood {1, 3}. When search backtracks out of depth 3, it restores val 6 while val 1 stays pruned - so depth 3 should clear, while depth 1 must stay set.

To handle that cleanly, the conflict set maintains a small slice of per-depth reference counts (activeConflictsAtDepth), tracking how many currently pruned values blame each tree depth:

Per-depth conflict counts and cached combined nogood Per-depth conflict counts and cached combined nogood

  • On prune (+1): for each depth bit set in the pruned value’s nogood, increment that depth’s count.
  • On restore (-1): when backtracking restores that value, decrement those same depth counts.
  • Building the combined nogood: a tree depth is in the conflict set if and only if its count is greater than 0. Instead of scanning 15,000 pruned candidates, it only scans depths 0 .. maxDepth (usually a few dozen integers) and sets bit d wherever count > 0.
  • Caching: better yet, that combined nogood only changes when a depth’s count crosses between 0 and 1 (leaving depth 3 in the diagram restores the value pruned at that depth, dropping depth 3 from 1 -> 0 and flipping bit 3 off, while depth 1 drops from 2 -> 1 and keeps bit 1 set). Pruning or restoring another 500 candidates caused by the same ancestor decisions leaves the cached nogood valid with zero work.

Testing these changes also smoked out a sneaky backjumping bug. When a constraint prunes a value and involves the current node’s decision variable, it is tempting to blame only the current node’s decision depth for that variable. That is valid on the variable = value branch, where the variable is assigned to a single value. On the variable != value branch, however, the variable is unassigned: if arc consistency propagates away from it and loops back through another constraint touching it, its narrowed domain depends on every value pruned from it so far (its full conflict set), not just the latest unassignment. Dropping those older conflicts over-generalized the wipeout, causing search to occasionally jump right past valid solutions.

Going the other way - blaming too many depths - doesn’t break correctness, it just stops backjumping from skipping innocent decisions. On scored crosswords, I tightened objective nogoods by skipping any assigned 0-cost (maximum-score) words, since unassigning a 0-cost word can never lower total cost.

Two smaller cleanups rounded things out:

  • Word-score and letter-frequency value heuristics used to rescore every live word in a variable’s domain on each decision. Candidate word indices are now pre-sorted by score once per word length, along with a lookup slice mapping each word index to its rank. When at least an eighth of the domain is still live, search walks the sorted list from the top and picks the first word whose bit is still set (usually hitting one within a few checks); when very few words remain, it scans the live bits directly and picks the best-ranked one.
  • Bipartite all-different used to copy graph structures whenever Supported() tested whether a variable-value pair could still belong to a maximum matching. Now the matcher reads edges straight from each variable’s live domain bitset and temporarily pins that pair in place on top of the incremental matching.

Across all three parts, almost every win came from the same basic move: trading general-purpose Go maps and per-value loops for dense integer indices and 64-bit bitset operations.

Once live domains became bitsets and variables got dense integer IDs, the rest of the pieces fit together naturally: bitwise domain filtering on crossword overlaps, 26-bit arc consistency checks, cost-tier bitmasks, a single shared slice for undoing prunings, and bitset nogoods backed by per-depth counts. Inner loops that used to touch tens of thousands of map entries now come down to a handful of bitwise instructions. My poor E2 micro VM is breathing much easier, and if you’ve made it this far, thanks for reading!