Crossword Puzzle Solver - System Design

Challenge

Think Beyond the Happy Path

Latency: How do we solve quickly or confidently conclude "no solution" without searching forever (timeouts, bounded search, and strong pruning)?
Efficiency: In a distributed search, how do we prevent two workers from exploring the same partial state (same chosen words / fixed letters) and wasting CPU?
Fault tolerance: If a worker dies mid-branch, what do we checkpoint (frontier + constraints), and how does another worker resume from that checkpoint instead of restarting?
Correctness under concurrency: If multiple workers find a valid fill around the same time, how do we guarantee we return exactly one solution and safely cancel all remaining work without race conditions?

Problem Statement

Design a backend service that fills a crossword puzzle grid.

Input:

A crossword "template" describing each word slot: its start position, direction (across/down), and length.
A dictionary of a limited number of candidate words.

Output:

Return any set of words—one per slot—such that:

Each slot's chosen word matches its required length, and
For every cell where an across and down slot intersect, the letters agree.

(If no such fill exists, return "no solution" / unsatisfiable.)

First Challenge - What is the valid assumption you should discuss?

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

Many crosswords are n×n.
If we assume n=50 as a mid-size board, that sets expectations for compute and latency.

2) How many slots are we solving?

"Given an n×n grid, can we estimate how many word slots exist?"

A reasonable quick estimate is around ~2n slots (across + down).
For n=50, that's roughly ~100 slots (order-of-magnitude).
This matters because the complexity grows more with #slots than with raw cell count.

3) Candidate dictionary size

"You mentioned we have a limited set of candidate words—what's the dictionary size we can use?"

This determines indexing strategy, memory footprint, and pruning efficiency.
If we assume a large dictionary like ~1M words, we'll design around fast filtering and constraint propagation rather than naive scanning.

4) Is a solution guaranteed?

"Should I assume every input puzzle is solvable?"

If it's not guaranteed, we need a clear output contract:
- Return one valid assignment if found, or
- Return 'no solution / unsatisfiable' when constraints can't be satisfied (and do so efficiently).

Tip

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:

If we naively treat each of ~100 slots as having ~10k candidates after basic filtering, the raw combination space is 10k^100 = 10^400. Intersections reduce this in practice, but it shows why we need aggressive pruning and distributed execution rather than brute force.
Even the first step—filtering candidates for each slot—means scanning/organizing 1M words by length/pattern and repeatedly intersecting constraints as letters get fixed.
With non-guaranteed solvability, the system must handle worst cases (deep backtracking, many dead ends), which can blow up CPU time unpredictably.

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:

Treat "solve this puzzle" as a job with a clear SLA and an explicit "no solution" outcome.
Use a scheduler + worker fleet to explore the search space in parallel (e.g., split by early branching choices / most-constrained slots).
Add system design primitives: work queue, dedup/idempotency, checkpoints, cancellation, and resource limits so bad puzzles don't starve the cluster.

Conclusion: the core skill is how you operationalize solving (job orchestration + scalable candidate lookup + pruning), not whether you remember backtracking.

Functional Requirements

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.

Non-Functional Requirements

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.

Tip

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.

Sign in to continue reading

"Crossword Puzzle Solver" requires a free account to access.