Faster Search: Bitmask Constraint Propagation

In the previous post, I replaced map-backed live domains with []uint64 bitsets. That makes checking and flipping individual domain values cheap, which is great, except the original propagation loop was still polling Supported() on every single remaining value one at a time.
When a word has 15,000 candidates, calling Supported() 15,000 times just to cross off a single candidate is a lot of wasted work. In this post I’ll flip that around: letting constraints push prunings directly in bulk, and using precomputed bitmasks (bit patterns stored in uint64 slices) to filter thousands of candidates at once.
Polling vs. pushing prunings
In the original propagator, whenever a variable changed, the solver looped over every constraint on that variable, every other unassigned variable in the constraint, and every live value in that variable’s domain, pruning values where Supported() returned false.
That interface is tough to beat for simplicity, so it stays around as a fallback. On large domains, though, constraints usually know much faster which values just became invalid. Constraints can now implement an optional Propagate method to prune unsupported values directly through a small helper interface provided by search:
type ValuePruner interface {
PruneFromVar(v *Variable, val int, culprit *Variable) bool
PruneWithConstraintReason(v *Variable, val int, c Constraint) bool
}
Routing prunings through ValuePruner instead of mutating variables directly keeps search in charge of three things: logging pruned values so they can be restored on backtrack, queuing affected variables when arc consistency is enabled, and recording why each value was pruned for backjumping.
Notice the two methods on that interface:
PruneFromVarblames a single variable. If a sparse all-different constraint covers 20 words and assigning one of them to “crane” removes “crane” from another, only that newly assigned variable is to blame, not the other 18 variables in the constraint. Keeping blame narrow matters a lot for backjumping.PruneWithConstraintReasonblames all variables involved in the constraint, when the pruning genuinely depends on several variables together.- In both cases, if a single constraint check prunes 4,000 candidates at once, they all share the exact same reason, so the pruner builds that explanation once and reuses it across the batch.
Crossword overlaps
In the crossword model, each word in the crossword puzzle (like 2-Across or 1-Down) is a variable. The number of candidates depends on the word’s length and the dictionary; say the dictionary has 15,000 5-letter words. Then every 5-letter word in the grid has domain [0, 14999], where each integer is an index into that 5-letter word list (0 for “aback”, 1 for “abase”, 2 for “abate”, and so on). So a 5-letter variable’s live domain bitset has 15,000 bits - one bit per 5-letter candidate in the dictionary. Wherever two words cross, an overlap constraint requires both chosen words to put the same letter in their shared cell.
Precomputing letter bitmasks
With live domains stored as bitsets, I didn’t want overlap checks looking up strings and comparing characters one candidate at a time. Instead, when the dictionary loads all words of a given length (say length 5), it precomputes a lookup table of bitmasks (ByPosAndLetter[pos][letter]) shared by every 5-letter word in the grid:
- For each character position (0 through 4) and each letter (‘a’ through ‘z’), it builds a
[]uint64bitmask of 15,000 bits, matching the exact layout of a 5-letter live domain bitset. Bit i is 1 if candidate i has that letter at that position, and 0 otherwise. For example,ByPosAndLetter[2]['a']marks every 5-letter candidate whose 3rd letter is ‘a’ (“aback”, “abase”, and “abate” are 1; “abbey”, “abbot”, and “abhor” are 0). Across 5 positions and 26 letters, that is 130 static bitmasks for all 5-letter words, built once and reused across the puzzle (and likewise for each other word length). - Alongside those candidate bitmasks, the dictionary also stores one 26-bit
uint32per character position, where bits 0 through 25 record whether any dictionary word of that length has ‘a’ through ‘z’ at that position at all.
It helps to keep those two sizes straight, since both show up below: each ByPosAndLetter[pos][letter] entry is a []uint64 bitmask over thousands of dictionary candidates, whereas the per-position alphabet summary is a single 26-bit integer over ‘a’ through ‘z’.
When one of the crossing words is assigned
Suppose 2-Across and 1-Down cross at position 2 of each word, and search assigns a word to 1-Down that puts ‘a’ into that shared cell. Now 2-Across can only keep candidates that also have ‘a’ at position 2.
The overlap constraint grabs the precomputed ByPosAndLetter[2]['a'] bitmask for 2-Across’s word length - call it allowedBits - and scans liveBits & ^allowedBits bucket by bucket across 2-Across’s live domain:
Candidates with ‘a’ at position 2 (allowedBits is 1) and candidates that were already pruned earlier (liveBits is 0) both evaluate to 0 and are skipped in a single instruction per 64-candidate bucket. Only live candidates with some other letter evaluate to 1 and get visited for pruning.
When neither word is assigned (arc consistency)
Previously, crossword overlaps relied on a listener that updated string patterns like "__a_e" whenever a word was assigned or cleared, and ignored individual candidate prunings. Aside from allocating strings on every assignment, that meant pruning candidates from an unassigned word never propagated across its crossings until a word was actually placed. Put differently, “arc consistency” on crosswords was quietly slacking off, and poking closely at this code made me feel bad enough to fix it properly.
Now suppose neither 2-Across nor 1-Down is assigned yet, and some other constraint just pruned a batch of candidates from 2-Across. Under arc consistency, propagation needs to prune any candidates in 1-Down that no longer have a valid crossing partner in 2-Across.
Comparing thousands of remaining candidates in 2-Across against thousands in 1-Down sounds expensive, until you remember that the two words only interact through their one shared cell (here position 2 of both words, though in general each word uses the table for its own length and crossing position). A candidate in 1-Down with letter c at that cell is still valid if and only if 2-Across still has at least one live candidate with c at that cell:
That breaks propagation into two steps:
-
Find which letters are unsupported for 1-Down. First (not shown in the diagram), for each letter ‘a’ through ‘z’, the constraint checks whether 2-Across still has at least one live candidate with that letter at position 2 by testing whether 2-Across’s live domain bitset has any 1 bit in common with 2-Across’s precomputed bitmask for that letter at position 2 (
liveBits & mask != 0). Because that scan stops at the very first non-zero bucket, confirming a supported letter usually takes just one or two bucket checks. Packing those 26 yes/no answers into a 26-bit integer gives supported (the first row in the diagram): the letters 2-Across can still place in the shared cell.Comparing supported against possible (the precomputed 26-bit summary of letters that appear at position 2 in 1-Down’s word list at all) with
possible & ^supportedgives unsupported: the letters that 1-Down’s word list actually uses at position 2, yet no longer have a single supporting candidate left in 2-Across. Notice ‘q’ in the diagram: 2-Across has no live ‘q’ words there, and ‘q’ still stays 0 in unsupported because 1-Down’s word list never had ‘q’ at position 2 anyway (in fact, the check skips testing ‘q’ on 2-Across in the first place). If unsupported is 0, every possible letter is still supported and propagation returns immediately without touching 1-Down. -
Prune 1-Down candidates that put an unsupported letter in the shared cell. In the diagram above, ‘i’ and ‘r’ are unsupported, so every live candidate in 1-Down with ‘i’ or ‘r’ at position 2 has to go. The constraint looks up 1-Down’s
ByPosAndLetter[2]['i']andByPosAndLetter[2]['r']bitmasks and prunes any live candidates inside them (liveBits & mask).
Scanning one candidate bitmask per unsupported letter is great when only 1 or 2 letters are unsupported, as in the diagram above. What if the opposite happens, though - say 2-Across narrowed down to just “aback” and “adept”, putting only ‘a’ or ’e’ in the shared cell, so 20+ letters are unsupported and only 2 are supported?
Running 20+ separate unsupported-letter passes over 1-Down’s buckets would still get the right answer, just with a lot of redundant work. When fewer letters are supported than unsupported, it’s cheaper to build an allowedBits mask from the supported letters instead:
- Start with a zeroed
[]uint64slice (allocated once on the constraint and reused so search doesn’t allocate). - Bitwise-OR 1-Down’s precomputed
ByPosAndLetter[2]['a']andByPosAndLetter[2]['e']bitmasks into that slice bucket by bucket. Because bit i is 1 in the ‘a’ mask if candidate i has ‘a’ at position 2, and 1 in the ’e’ mask if it has ’e’, the combined mask ends up with a 1 for every 1-Down candidate that has ‘a’ or ’e’ at position 2. - Run a single
liveBits & ^allowedBitspass on 1-Down, the exact same “prune outside mask” operation used when a crossing word was assigned.
Because every letter in possible is either supported or unsupported, whichever side has fewer 1 bits has at most 13 letters, capping propagation at 13 candidate bitmasks even in the worst case.
One small quirk here is user-supplied words. Because a user can pre-fill a word on the UI with something that isn’t in the dictionary, pre-filled variables get a tiny [-1, -1] domain (still a 1-bit domain, while -1 will panic immediately if anything mistakenly uses it as a word-list index) and the overlap constraint checks their fixed character directly instead of indexing into ByPosAndLetter.
Sparse all-different and word-score costs
The same pattern paid off in a couple of other constraints:
- Sparse all-different swapped its map of claimed values for a flat count slice and now prunes only the newly assigned value from each peer variable (a single bit check and clear per peer), instead of scanning all their live values.
- Scored crosswords use an objective function to prefer higher-scoring words from the dictionary, converting each word’s score into a non-negative cost (maximum score minus word score) so total cost only goes up as words are placed. Because dictionary scores fall into a small number of distinct values, I precomputed a bitmask for each cost threshold. Whenever the remaining cost budget shrinks, binary search finds the lowest cost tier that busts the budget, and one bitmask pass prunes every too-expensive word at once (or exits immediately if even the worst word still fits).
- Wiring up objective pruning exposed a subtle backtracking edge case: normally total cost only changes when a variable is assigned. Right after search finds a better solution and lowers its best-cost bound, though, it backtracks and unassigns variables, leaving an unassigned variable whose restored values may already exceed the tighter bound. Objective propagation therefore also has to filter the changed variable’s own domain when woken up unassigned.
With constraint propagation doing bulk bitmask filtering, performance bottlenecks shifted to the bookkeeping around search itself: map lookups, locks, undo tracking, and backjumping. I’ll tackle those in the final post of the series.