Courses › System Design › Question Breakdowns

Design a Crossword Puzzle Solver

Backtracking with constraint propagation, splitting the search across workers, cancellation and caching.

Design a service that fills crossword grids: users submit a grid (some cells blocked, some letters already placed) and the system returns a fill where every across and down slot is a word from a dictionary. It's an unusual question that mixes an algorithm (constraint satisfaction with backtracking) with a distributed system (splitting a huge search across workers, async jobs, cancellation and caching). Expect to spend real time on both.

Requirements

Functional

  • Users submit a grid (size, blocked cells, pre-filled letters) and optionally a dictionary choice (or a word list with scores)
  • The system returns a valid fill (or the best *k* fills by word score), or reports that none exists
  • Users can check progress and cancel a solve
  • (Variant) Given clues, rank candidate words per slot using a clue-answer model, then solve

Out of scope: generating clues, the puzzle-playing UI, multiplayer.

Non-functional

  • Latency: typical 15×15 grids solve in seconds; hard or unsatisfiable grids may take minutes — so the API is asynchronous
  • Scale: ~1k solve requests/minute at peak; each may be CPU-heavy
  • Bounded cost: every solve has a time/CPU budget; runaway searches are stopped
  • Deterministic & cacheable: the same grid + dictionary gives the same answer

[!TIP] Start with the algorithm, briefly Interviewers want to know you can actually solve the puzzle before you distribute it. Two minutes on "slots are variables, words are domains, crossings are constraints, solve with backtracking + constraint propagation" earns the right to spend the rest of the time on the system.

The algorithm in two minutes

  • Variables: each across/down slot (a run of ≥ 3 open cells).
  • Domains: dictionary words of the slot's length that match its pre-filled letters.
  • Constraints: two crossing slots must share the same letter at the crossing cell.
  • Search: pick the slot with the fewest candidates (MRV heuristic), try its words in score order, and after each placement propagate: filter every crossing slot's candidates to words with the right letter at that position. If any slot is left with zero candidates, backtrack.

Fast candidate filtering: index the dictionary by (length, position, letter) → bitset of word IDs. A slot's candidates are the AND of the bitsets for its fixed letters — a few microseconds even for 100k+ words.

def candidates(length, pattern):
    bits = all_words[length]                     # bitset of words of this length
    for pos, ch in enumerate(pattern):
        if ch != "?":
            bits &= index[length][pos][ch]       # (length, position, letter) -> bitset
    return bits

Core Entities

  • Dictionary — ID, version, words with scores, prebuilt bitset index
  • Solve job — grid, dictionary ID, options (k, time budget), status, result, stats
  • Subproblem — job, partial assignment (a prefix of the search tree), status, assigned worker

API

POST /v1/solves
{ "grid": ["#..#....", ...], "dictionaryId": "en-2026", "k": 1, "timeoutSec": 60 }
→ 202 { "solveId": "s_31", "status": "queued" }

GET    /v1/solves/{solveId}   → { "status": "solved", "fill": [...], "nodesExplored": 1840221 }
DELETE /v1/solves/{solveId}   → cancel

High-Level Design

user = client "Client" @0,0
api = service "Solve API" @1,0
cache = cache "Result Cache\n(grid hash)" @1,1
jobs = store "Jobs DB" @2,0
coord = service "Coordinator\n(splits search)" @2,1
q = queue "Subproblem Queue" @3,1
w = service "Search Workers\n(dictionary in RAM)" @4,1
dict = blob "Dictionary Index\n(S3)" @4,0
user -> api : submit / poll
api -> cache : seen this grid?
api -> jobs
coord -> jobs
coord -> q : subproblems
w -> q : pull
dict --> w : load at startup
w -> coord : solution / exhausted
  • The API normalizes the grid, hashes (grid, dictionary version, options) and returns a cached result if there is one.
  • Otherwise it creates a job and hands it to a coordinator, which runs propagation once and splits the search into subproblems.
  • Workers (with the dictionary index preloaded in memory) pull subproblems and search them depth-first.
  • The first worker to find a valid fill reports it; the coordinator marks the job solved and cancels the remaining subproblems.

Deep Dives

1. Splitting the search across workers

Backtracking is a tree. Split it by fixing the first few decisions: take the most-constrained slot, and for each of its top N candidates create a subproblem "slot 7 = CATTLE". If that's not enough parallelism, branch one level deeper.

The catch: subtrees are wildly uneven — most die after a few steps, one may take minutes. Fixed splitting leaves workers idle while one grinds.

  • Work stealing / re-splitting: a worker that has been in one subproblem for more than ~1s splits its remaining unexplored branches into new subproblems and pushes them back to the queue.
  • Each subproblem is self-contained (the grid plus a partial assignment), so any worker can take it — no shared state between workers.

2. Stopping early and cancelling

Workers check a cancellation flag (Redis key per job) every few thousand search nodes. The flag is set when: a solution is found (for k = 1), the user cancels, or the job's time budget expires. Subproblems for cancelled jobs are skipped when dequeued.

For k > 1, workers report solutions with scores; the coordinator keeps a top-k heap and tells workers the current k-th best score so they can prune branches that can't beat it (branch and bound).

3. Proving "no solution"

Unsatisfiable grids are the most expensive case — the whole tree must be explored. The coordinator tracks subproblems as pending / running / exhausted; the job is unsatisfiable only when every subproblem (including re-split children) is exhausted. Count outstanding subproblems atomically (a counter decremented as each finishes) so you don't declare failure while a child is still in flight.

[!WARNING] Losing a subproblem means a wrong "no solution" If a worker crashes mid-subproblem and nobody notices, the coordinator may never finish — or worse, finish and claim no solution exists. Use queue visibility timeouts / leases, so an unacknowledged subproblem reappears and another worker re-runs it.

4. Dictionaries as data

  • Build the bitset index offline per dictionary version and store it in S3; workers load it at startup (tens of MB for a large English list).
  • Custom user word lists are small: build their index on the fly and cache by content hash.
  • Pin each job to a dictionary version so results are reproducible and the cache key is stable.

5. Fairness and cost

Solves vary from milliseconds to minutes. Enforce a CPU-seconds budget per job and per user, put small grids in a fast lane, and autoscale workers on queue depth. Very large or adversarial grids (e.g. an empty 25×25) get a budget and an honest "timed out".

6. Caching

Many requests are repeats (the same daily puzzle submitted by thousands of users). Cache results by normalized grid hash; also cache unsatisfiable results. Symmetric grids can be canonicalized (rotate/reflect to a canonical form) to raise the hit rate.

What's expected at each level

  • Mid-level: a correct backtracking solver with sensible heuristics, wrapped in an async job API.
  • Senior: fast candidate filtering, splitting the search into independent subproblems, cancellation on first solution, caching and per-job budgets.
  • Staff: load balancing uneven subtrees (re-splitting / work stealing), correct termination for unsatisfiable grids under worker failures, branch-and-bound for top-k, and cost controls.