Distributed Crossword Solver

0) Problem Restatement

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.

1) Requirements

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.

2) Modeling the Problem

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??E is then an AND of two bitsets → matching words in microseconds.

3) Core Algorithm (single machine)

1. 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.
2. Try its candidates, best-scored first (for clue-based solving).
3. 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).
4. Don't use the same word twice in a grid.
5. 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 None

4) Distributing the Search

4.1 Architecture

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"| Q

4.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".

5) 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.

6) Trade-offs & Alternatives

7) Wrap-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.