Design a distributed crossword fill solver

Scenario

You are building a service that fills a crossword-like grid with words.

• The board size is not specified; assume a medium board around 50×50 .
• There are about 100 word slots (across + down) that must be filled.
• You have a dictionary of ~1,000,000 words .
• A word slot is a sequence of contiguous cells; slots intersect at shared cells.
• Goal: find any one valid complete filling (not all solutions).

Requirements

1. Return one complete assignment of words to all slots such that:
   • Each slot is filled by a dictionary word of matching length.
   • Intersections have the same letter from both words.
   • (Optional, clarify in interview) Whether a word can be reused in multiple slots.
2. Discuss why a single machine may be insufficient (time/memory) and design a distributed solution.
3. Explain how you would:
   • Represent the problem and constraints
   • Prune the search space
   • Parallelize the search across machines
   • Detect completion and handle failures