Design a crossword puzzle solver system

Design a crossword puzzle solver

Design a system that can solve a crossword puzzle.

Inputs

• A 2D board grid:
  • Some cells are blocked (black squares)
  • Some cells are empty (need letters)
  • Optionally, some cells may already contain a fixed letter
• A dictionary (word list)

A valid solution must:

• Fill every non-blocked cell with a letter
• Every horizontal and vertical contiguous run of non-blocked cells (a “slot”) must form a word present in the dictionary
• Respect pre-filled letters and intersections

Outputs

• One solved board (or all solutions / top-K solutions, if you choose—state your choice)
• If no solution exists, return “no solution”

What to cover

• Core algorithmic approach and data structures
• How you prune the search space and handle constraints from intersections
• Complexity considerations
• How you would structure this as a service/API if the dictionary and traffic are large (caching, precomputation, scaling)

State any assumptions (board size, dictionary size, allowed alphabets, whether repeated words are allowed, etc.).