寻求优化2D字母矩阵拼图填字算法的解决方案

核心优化思路 #

针对原方案候选词过多导致二次回溯无法运行的问题，核心是避免预生成所有候选词，转而在矩阵上直接进行带剪枝的回溯，同时结合主题词优先策略缩小搜索空间。

1. 主题词优先定位 #

先遍历矩阵所有横向（每行8个连续字母）、纵向（每列6个连续字母）的序列，筛选出符合长度要求的合法主题词，确定其位置后标记占用格子，再围绕剩余格子回溯，直接将搜索空间缩小至少数倍。

2. 前缀树（Trie）替代AVL树做实时词典校验 #

AVL树适合精确单词查找，但在构建单词过程中需要频繁检查前缀是否存在，Trie树的前缀匹配效率更高，能在单词构建的每一步就剪枝无效路径，避免生成大量无意义的候选词。

3. 在位矩阵上直接回溯（无预生成候选词） #

从任意未使用的格子出发，沿8个方向延伸，每添加一个字母就用Trie检查前缀合法性：

• 前缀不存在时立即停止该方向延伸
• 前缀构成合法单词且长度符合要求时，标记对应格子为已使用，递归处理剩余格子
• 回溯时恢复格子状态

4. 强化剪枝策略 #

• 剩余格子数校验：剩余未使用格子数必须能被允许的单词长度范围覆盖（如要求单词长度3-5，剩余数需满足3 ≤ 剩余数 ≤ 5×k，且存在k使得剩余数能被某个允许长度整除）
• 字母频率校验：提前统计矩阵字母出现次数，构建单词时，当前单词的字母频率不能超过剩余字母频率
• 位掩码优化状态记录：用整数二进制位标记已使用格子（6×8=48位，Python原生int支持），状态拷贝和比较效率远高于二维数组

实现代码 #

1. 前缀树（Trie）实现 #

class TrieNode:
    __slots__ = ['children', 'is_end']
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def check_prefix(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False, False
            node = node.children[c]
        return True, node.is_end  # (前缀是否存在, 是否为完整单词)

2. 矩阵回溯核心逻辑 #

class MatrixWordSolver:
    def __init__(self, matrix, trie, min_len=3, max_len=5):
        self.matrix = matrix
        self.rows = len(matrix)
        self.cols = len(matrix[0])
        self.trie = trie
        self.min_len = min_len
        self.max_len = max_len
        # 预计算字母频率
        self.letter_count = {}
        for row in matrix:
            for c in row:
                self.letter_count[c] = self.letter_count.get(c, 0) + 1
        # 8个移动方向
        self.directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    
    def is_valid_pos(self, r, c):
        return 0 <= r < self.rows and 0 <= c < self.cols
    
    def backtrack(self, used_mask, current_words):
        # 所有格子已使用，返回结果
        if used_mask == (1 << (self.rows * self.cols)) - 1:
            return current_words.copy()
        
        # 剪枝：剩余格子数不符合单词长度要求
        remaining = bin(used_mask).count('0')
        if remaining < self.min_len or remaining > self.max_len * (remaining // self.min_len):
            return None
        
        # 找到第一个未使用的格子，避免重复搜索对称状态
        start_idx = next(i for i in range(self.rows*self.cols) if not (used_mask & (1 << i)))
        start_r, start_c = divmod(start_idx, self.cols)
        
        # 尝试从该格子出发的所有可能单词
        for dr, dc in self.directions:
            current_word = []
            current_mask = 0
            r, c = start_r, start_c
            while self.is_valid_pos(r, c) and not (used_mask & (1 << (r*self.cols + c))):
                current_word.append(self.matrix[r][c])
                current_mask |= (1 << (r*self.cols + c))
                word_str = ''.join(current_word)
                has_prefix, is_word = self.trie.check_prefix(word_str)
                
                if not has_prefix:
                    break  # 前缀不存在，停止延伸
                
                if len(current_word) >= self.min_len and is_word:
                    # 校验字母频率合法性
                    temp_count = self.letter_count.copy()
                    valid = True
                    for char in word_str:
                        temp_count[char] -= 1
                        if temp_count[char] < 0:
                            valid = False
                            break
                    if not valid:
                        r += dr
                        c += dc
                        continue
                    
                    # 递归回溯
                    result = self.backtrack(used_mask | current_mask, current_words + [word_str])
                    if result is not None:
                        return result
                
                r += dr
                c += dc
        
        return None
    
    def find_theme_candidates(self):
        # 筛选所有横向/纵向的合法主题词
        theme_candidates = []
        # 横向单词
        for r in range(self.rows):
            for start_c in range(self.cols - self.min_len + 1):
                for end_c in range(start_c + self.min_len - 1, min(self.cols, start_c + self.max_len)):
                    word = ''.join(self.matrix[r][start_c:end_c+1])
                    _, is_word = self.trie.check_prefix(word)
                    if is_word:
                        mask = 0
                        for c in range(start_c, end_c+1):
                            mask |= (1 << (r*self.cols + c))
                        theme_candidates.append((word, mask))
        # 纵向单词
        for c in range(self.cols):
            for start_r in range(self.rows - self.min_len + 1):
                for end_r in range(start_r + self.min_len - 1, min(self.rows, start_r + self.max_len)):
                    word = ''.join([self.matrix[r][c] for r in range(start_r, end_r+1)])
                    _, is_word = self.trie.check_prefix(word)
                    if is_word:
                        mask = 0
                        for r in range(start_r, end_r+1):
                            mask |= (1 << (r*self.cols + c))
                        theme_candidates.append((word, mask))
        return theme_candidates
    
    def solve(self):
        # 优先尝试主题词路径
        theme_candidates = self.find_theme_candidates()
        for theme_word, theme_mask in theme_candidates:
            # 校验主题词字母频率
            temp_count = self.letter_count.copy()
            valid = True
            for char in theme_word:
                temp_count[char] -= 1
                if temp_count[char] < 0:
                    valid = False
                    break
            if not valid:
                continue
            result = self.backtrack(theme_mask, [theme_word])
            if result is not None:
                return result
        # 主题词路径无解时，尝试普通回溯
        return self.backtrack(0, [])

3. 原AVL树实现（保留对比） #

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def get_height(self, node):
        return node.height if node else 0
    
    def get_balance(self, node):
        return self.get_height(node.left) - self.get_height(node.right) if node else 0
    
    def right_rotate(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y
    
    def left_rotate(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y
    
    def insert(self, node, key):
        if not node:
            return AVLNode(key)
        if key < node.key:
            node.left = self.insert(node.left, key)
        elif key > node.key:
            node.right = self.insert(node.right, key)
        else:
            return node
        
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
        balance = self.get_balance(node)
        
        if balance > 1 and key < node.left.key:
            return self.right_rotate(node)
        if balance < -1 and key > node.right.key:
            return self.left_rotate(node)
        if balance > 1 and key > node.left.key:
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)
        if balance < -1 and key < node.right.key:
            node.right = self.right_rotate(node.right)
            return self.left_rotate(node)
        return node
    
    def search(self, node, key):
        if not node or node.key == key:
            return node is not None
        return self.search(node.left, key) if key < node.key else self.search(node.right, key)

使用示例 #

# 初始化6×8矩阵
matrix = [
    ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'],
    ['I', 'J', 'K', 'L', 'M', 'N', 'O', 'P'],
    ['Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X'],
    ['Y', 'Z', 'A', 'B', 'C', 'D', 'E', 'F'],
    ['G', 'H', 'I', 'J', 'K', 'L', 'M', 'N'],
    ['O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V']
]

# 加载词典示例
dictionary = ['ABC', 'DEF', 'GHI', 'JKL', 'MNO', 'PQR', 'STU', 'VWX', 'YZAB', 'CDEF', 'GHIJ', 'KLMN', 'OPQR', 'STUV']
trie = Trie()
for word in dictionary:
    trie.insert(word)

# 初始化求解器并运行
solver = MatrixWordSolver(matrix, trie, min_len=3, max_len=4)
solution = solver.solve()
print("找到解：", solution) if solution else print("无解")

内容的提问来源于stack exchange，提问作者Dino