Problem RestatementProblem
Given a crossword grid with blank cells (and maybe some letters already filled) and a large dictionary, fill in every across and down slot so that each is a valid word and the crossing letters match. Then scale it: much bigger grids or dictionaries, and many puzzles solved at the same time, using many machines. OpenAI asked this repeatedly, mixing algorithm design with distributed-systems thinking.
RequirementsRequirements
1.1 Functional
- Input: a grid (blocked cells, blanks, fixed letters) and a dictionary (maybe with scores or clues).
- Output: a valid fill (or all fills, or the best-scoring one), or "no solution".
- Optional: use clues to rank candidate words.
1.2 Non-Functional
- Solve typical puzzles in seconds.
- Scale to large puzzles by spreading work over workers.
- Handle many puzzle requests concurrently, with timeouts.
Modeling the ProblemProblem
This is a constraint satisfaction problem (CSP):
- Variables: the slots (e.g., 1-Across, 3-Down), each with a length.
- Domain of each slot: dictionary words of that length that match any fixed letters.
- Constraints: where an across slot crosses a down slot, they must share the same letter at that cell.
2.1 Dictionary index
To find candidates fast, pre-index the dictionary:
- Group words by length.
- For each length, position and letter, keep a bitset of which words have that letter there. For example, for length 5, position 2, letter "A" → bitset of words like "CRANE" and "PLANT".
- A pattern like
?A??Eis then an AND of two bitsets → matching words in microseconds.
Core Algorithm (single machine)
Backtracking search with smart ordering and pruning:- Pick the most constrained slot first: the one with the fewest candidate words (the MRV heuristic, "minimum remaining values"). Failing early saves huge amounts of work.
- Try its candidates, best-scored first (for clue-based solving).
- After placing a word, propagate: update the patterns of all crossing slots and recompute their candidate sets. If any becomes empty, undo immediately (forward checking).
- Don't use the same word twice in a grid.
- Recurse. If all slots are filled, we found a solution.
# Sketch: grid and index are helper objects (pattern, place, undo, crossing, candidates)
def solve(grid, slots, index, used):
open_slots = [s for s in slots if not grid.filled(s)]
if not open_slots:
return grid.copy()
slot = min(open_slots, key=lambda s: len(index.candidates(grid.pattern(s)))) # most constrained
for word in index.candidates(grid.pattern(slot)):
if word in used:
continue
undo = grid.place(slot, word)
if all(index.candidates(grid.pattern(x)) for x in grid.crossing(slot)): # forward check
used.add(word)
result = solve(grid, slots, index, used)
if result:
return result
used.discard(word)
grid.undo(undo)
return NoneDistributing the Search
4.1 Architecture
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
C["Client"] --> API["Solve API"]
API --> CO["Coordinator - splits search"]
CO --> Q[("Work queue of sub-problems")]
Q --> W1["Worker - backtracking"]
Q --> W2["Worker - backtracking"]
Q --> W3["Worker - backtracking"]
W1 -->|"solution / more work / dead end"| CO
W2 --> CO
W3 --> CO
IDX[("Dictionary index - replicated to all workers")] --> W1
IDX --> W2
IDX --> W3
CO -->|"cancel others when solved"| Q4.2 How to split the work
- Split at the top of the search tree: take the most constrained slot and create one sub-problem per candidate word (or groups of candidates). Each sub-problem is "the grid with slot X = word W". Put them on a queue.
- Workers run backtracking on their sub-problem. If a sub-problem runs too long, a worker can split it again and push the pieces back (work stealing), which keeps all workers busy even though some branches are far bigger than others.
- Replicate the dictionary index to every worker (it's read-only and fits in memory), so no remote lookups happen in the hot loop.
4.3 Stopping early
- For "any solution": the first worker to find one reports it, and the coordinator cancels the remaining sub-problems (workers check a cancel flag regularly).
- For "best solution": workers share the best score found so far, so others can prune branches that can't beat it (branch and bound).
- Every puzzle has a timeout. On timeout, return the best partial fill or "not solved".
Deep Dive — Choosing which slot to fill nextDeep dive
Backtracking spends all its time in one decision: given a partly filled grid, which empty slot do we try next? The same solver, with the same dictionary, swings between milliseconds and hours on that choice alone.
Fill slots in grid order
Work through the slots left to right, top to bottom, trying candidate words in dictionary order.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
G["Fill 1-Across - 30,000 candidates"] --> N["Fill 2-Down - 8,000 candidates"]
N --> D["... 14 slots deep"]
D --> F["15-Down has no word matching _Q_ZJ"]
F --> BT["Backtrack all the way up"]
BT --> GThe conflict that kills a branch usually lives deep in the grid, and grid order finds it last. The solver explores millions of partial fills that were doomed by a choice made fourteen levels earlier, and it rediscovers the same dead end for every combination above it.
Take the most constrained slot first
Pick the empty slot with the fewest matching candidates — the classic minimum-remaining-values heuristic. A slot with three possible words gets decided before a slot with thirty thousand.
Failures now surface near the top of the tree, where a wrong branch is cheap to abandon, and this alone is often a thousand-fold improvement. What it still does not do is act on what a choice implies. Placing a word narrows every slot crossing it, but the solver only discovers that when it eventually reaches those slots — and by then it may be deep inside a branch that was already impossible.
Propagate the consequences before descending
After placing a word, immediately recompute the candidate list for every crossing slot. If any slot drops to zero candidates, the branch is dead — abandon it now, before spending a single level on it.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
P["Place a word in the tightest slot"] --> PROP["Recompute candidates for crossing slots"]
PROP --> Z{"Any slot with zero candidates?"}
Z -->|"yes"| KILL["Dead branch - backtrack immediately"]
Z -->|"no"| NEXT["Descend into the new tightest slot"]
NEXT --> BIG{"Sub-problem still huge?"}
BIG -->|"yes"| SPLIT["Split it and push the pieces back on the queue"]
BIG -->|"no"| SOLVE["Solve locally"]The pattern is constraint propagation, and the cheap version — recomputing one level of crossings — captures most of the benefit for a fraction of the bookkeeping of full arc consistency.
It also makes the distribution work. Pruning is what keeps sub-problems from being wildly uneven, and the ones that are still large get split again and pushed back on the queue, so a worker that drew a monster branch shares it instead of running alone for an hour while the rest of the fleet idles.
Serving Many Puzzles
- Each puzzle request becomes a job with its own sub-problem queue. Fair scheduling gives each job a share of workers, so one huge puzzle can't starve the rest.
- Cache results by grid hash + dictionary version, since popular puzzles are asked repeatedly.
- Worker failure: sub-problems are leased. If a worker dies, its leased sub-problems go back to the queue. Duplicate results are harmless.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Search | Backtracking + MRV + forward checking | Huge pruning | Brute force: impossibly slow |
| Candidate lookup | Bitsets per (length, position, letter) | Microsecond pattern matching | Regex over word lists: slow |
| Distribution | Split top branches + work stealing | Even load despite uneven branches | Static split: some workers idle |
| Index | Replicated on every worker | No network in the inner loop | Central index service: latency per lookup |
Wrap-UpWrap-up
Model the crossword as a constraint problem, index the dictionary by length, position and letter with bitsets, and solve with backtracking that always fills the most constrained slot first and checks crossing slots after every placement. To scale, split the top of the search tree into sub-problems on a queue, replicate the index to workers, rebalance with work stealing, and cancel remaining work (or prune with the best score) as soon as a solution is found.