Sign in to keep reading
“Crossword Puzzle Solver” is free with an account. Your progress and bookmarks follow you across devices.
Sign in to continueDesign a Crossword Puzzle Solver - This system design covers distributed constraint satisfaction, parallel search execution, fault-tolerant scheduling, and bounded solve times at scale.
Written by a Staff+ Engineer and an Engineering Manager
10+ years of experience in low-latency streaming and AI infrastructure. Tech lead for real-time LLM serving platforms handling millions of concurrent requests. Over 12 years of industry experience with 6 years in engineering leadership, building and scaling tech infrastructure teams that deliver end-to-end large-scale distributed systems.
“Crossword Puzzle Solver” is free with an account. Your progress and bookmarks follow you across devices.
Sign in to continueThink Beyond the Happy Path
Could you answer these today? Tick what you already know.
Design a backend service that fills a crossword puzzle grid.
Input:
Output:
Return any set of words—one per slot—such that:
(If no such fill exists, return "no solution" / unsatisfiable.)
You might hear "crossword solver" and think it's just a brute-force / DFS coding problem. In a system design interview, that mindset can make you miss the real trap: you need to align assumptions up front so you don't design the wrong thing.
Here's a clean assumption-check script you can use with your interviewer:
1) Grid size and problem scale
"Before I jump into algorithms, can we confirm the grid size?"
2) How many slots are we solving?
"Given an n×n grid, can we estimate how many word slots exist?"
3) Candidate dictionary size
"You mentioned we have a limited set of candidate words—what's the dictionary size we can use?"
4) Is a solution guaranteed?
"Should I assume every input puzzle is solvable?"
What can we learn from the assumptions?
1) This won't fit as a "single machine" design at realistic scale
Once we align on n=50, ~100 slots, and a 1M-word dictionary, the naive "just run DFS on one box" approach breaks quickly:
Conclusion: you should design for parallelism, bounded work, retries, and timeouts, not "one process finishes fast."
2) The interview is testing distributed problem-solving and scheduling, not just DFS
The assumptions implicitly push you toward a distributed constraint-satisfaction service:
FR1 – Solve puzzles
Given a board described as word slots (start position, direction, length) and a dictionary, find any valid assignment of words to slots.
FR2 – Enforce constraints
Each chosen word must match its slot length, and all intersecting across/down slots must agree on the shared letters.
FR3 – Return results
Output the solved puzzle as a slot-to-word mapping (including each word's position and direction), or return "no solution" if no valid assignment exists.
NFR1 – Low Latency (Bounded Batch Completion Time)
Metric: p95 solve time ≤ 5 minutes & hard cap ≤ 10 minutes per puzzle (return solution or "no solution within budget").
A real service can't run unbounded search. We need predictable completion so callers can set expectations, retry, or degrade gracefully when puzzles are extremely hard or unsatisfiable.
NFR2 – High Efficiency (No Duplicate Work)
Metric: duplicate exploration rate ≤ 5% (by unique-state hashing), and candidate lookup per constraint query (length + fixed letters) p95 ≤ 10 ms.
Distributed solving only helps if parallelism is productive. We must aggressively avoid two workers exploring the same partial assignment (same fixed letters + chosen words), and keep candidate filtering fast so compute is spent on search, not scanning the dictionary.
NFR3 – Fault Tolerance (Checkpoint + Resume)
Metric: ≥ 99.9% of solve jobs should finish (success, no-solution, or canceled) without being lost.
Worker crashes are normal at scale. The system must persist enough progress (frontier + constraints) so another worker can pick up quickly instead of starting over.
NFR4 – Concurrency Correctness (Exactly-One Result)
Metric: exactly-once completion semantics with cancellation propagation ≤ 500 ms after a solution is found.
In parallel search, multiple workers may find solutions nearly simultaneously. The system must commit exactly one result, ensure idempotent completion, and reliably stop the remaining work without race conditions.
The Core Algorithm: Distributed DFS
At its heart, this solver is a depth-first search with aggressive pruning. We prefer DFS over BFS because we're not looking for the "best" fill—we just need any valid one. BFS expands a wide frontier and can blow up memory quickly, while DFS keeps memory small (mainly the current path plus constraint bookkeeping) and often finds a valid solution sooner by going deep.
To make DFS scalable, we distribute the search tree. The scheduler takes an early branching point (for example, choose the most constrained slot and try different candidate words) and turns each branch into a Task. Each Task represents a partial assignment that becomes the root of a subtree. Workers pull tasks from a shared queue, run the DFS locally with backtracking, and either (1) hit a dead end and stop, (2) split again if the subtree is still too large, or (3) find a complete valid fill. Once any worker finds a solution, it writes the Result and the rest of the job stops, since we only need the first valid assignment.
Key mechanisms: task splitting at early high-branching states, queue-based work distribution for load balancing, and "first solution wins" termination so we don't waste compute after a valid fill is found.
Requirement Summary
| Functional Requirements (FRs) | |
|---|---|
| Name | Description |
| 1. Solve Puzzles | Given a board and dictionary, find any valid assignment of words to slots. |
| 2. Enforce Constraints | Each word must match slot length; intersecting slots must agree on shared letters. |
| 3. Return Results | Output slot-to-word mapping or 'no solution' if no valid assignment exists. |
| Non-Functional Requirements (NFRs) | |
|---|---|
| Name | Description |
| 1. Low Latency | p95 solve time ≤ 5 min; hard cap ≤ 10 min per puzzle. |
| 2. High Efficiency | Duplicate exploration ≤ 5%; candidate lookup p95 ≤ 10 ms. |
| 3. Fault Tolerance | ≥ 99.9% of jobs finish without being lost; checkpoint + resume on crash. |
| 4. Concurrency Correctness | Exactly-once completion; cancellation propagation ≤ 500 ms. |
Conclusion: the core skill is how you operationalize solving (job orchestration + scalable candidate lookup + pruning), not whether you remember backtracking.