System Design - Design a Crossword Puzzle Solver

System Design - Design a Crossword Puzzle Solver

Problem Statement: Design a service that solves crossword puzzles. Given a board with word slots (positions, directions, lengths) and a dictionary of ~1 million words, find any valid assignment of words that satisfies all the constraints.

Examples:

1. Crossword board: +---+---+---+---+---+---+ | | | | | | | +---+---+---+---+---+---+ | | | | | | | +---+---+---+---+---+---+ | | | | | | | +---+---+---+---+---+---+ | | | | | | | +---+---+---+---+---+---+ | | | | | | | +---+---+---+---+---+---+ | | | | | | | +---+---+---+---+---+---+ Word slots:

• Across: (1,1) -> 5
• Down: (3,1) -> 3
• Across: (3,3) -> 7

Dictionary: ["hello", "world", "example", ...]

Output: A valid assignment of words that satisfies all the constraints.

Constraints:

1. The crossword board has a fixed size (e.g., 15x15).
2. The dictionary contains ~1 million words.
3. Words can be placed horizontally or vertically.
4. Words must fit within the board boundaries.
5. Words must not overlap with each other.

Hints:

1. Use a backtracking algorithm to explore all possible word assignments.
2. Preprocess the dictionary to group words by length for efficient lookup.
3. Use a trie data structure to store the dictionary for fast prefix matching.

Solution:

1. Preprocess the dictionary:

   • Group words by length.
   • Build a trie data structure for fast prefix matching.

2. Define a recursive backtracking function to explore all possible word assignments:

   • Start with an empty board.
   • For each word slot, try all possible words from the dictionary that fit the slot's length and direction.
   • Check if the word fits the board boundaries and does not overlap with existing words.
   • Recursively call the backtracking function for the next word slot.
   • If all slots are filled, return the solution.
   • If no valid assignment is found, backtrack and try the next word.

3. Optimize the backtracking algorithm:

   • Use memoization to store intermediate results and avoid重复计算。
   • Use pruning techniques to eliminate branches that cannot lead to a valid solution.

4. Return the first valid assignment found by the backtracking algorithm.

Example Code:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True

    def search(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

def solve_crossword(board, word_slots, dictionary):
    # Preprocess the dictionary
    trie = Trie()
    for word in dictionary:
        trie.insert(word)

    # Group words by length
    words_by_length = {}
    for word in dictionary:
        length = len(word)
        if length not in words_by_length:
            words_by_length[length] = []
        words_by_length[length].append(word)

    # Backtracking function
    def backtrack(board, word_slots, index):
        if index == len(word_slots):
            return True

        slot = word_slots[index]
        direction = slot["direction"]
        start_pos = slot["start_pos"]
        length = slot["length"]

        # Try all possible words for the current slot
        for word in words_by_length.get(length, []):
            if can_place_word(board, word, start_pos, direction):
                board[start_pos[0]][start_pos[1]] = word[0]
                if backtrack(board, word_slots, index + 1):
                    return True
                board[start_pos[0]][start_pos[1]] = None

        return False

    def can_place_word(board, word, start_pos, direction):
        if direction == "across":
            for i in range(len(word)):
                if board[start