Python递归回溯单词搜索算法无法定位网格内已存在单词的问题
问题描述
- 已完成单词搜索网格生成器开发,目前正在开发配套的*递归回溯(recursive back-tracker)*求解器。生成器输出的网格为二维列表格式,示例结构如下:
[["C", "A", "T"], ["U", "A", "L"], ["P", "A", "R"]]
- 当前求解器存在异常:有时无法定位实际存在于二维数组中的单词。
可复现代码
以下为经过压缩、无冗余、可直接运行复现问题的完整求解器代码:
def neighbors(i, j): return [(i + i_step, j + j_step) for i_step in (-1, 0, 1) for j_step in (-1, 0, 1)] # To prevent ListIndexOutOfRangeError def elems_within_bounds(ls, smallest, largest): return all(smallest <= elem <= largest for elem in ls) def finder(grid, i, j, word): neighbour_rel_coords = neighbors(i, j) for coord in neighbour_rel_coords: if not elems_within_bounds(coord, 0, len(grid[0]) - 1): continue if grid[coord[0]][coord[1]] == word[0]: return True if len(word) == 1 else finder(grid, coord[0], coord[1], word[1:]) else: continue return False def find_word(grid, word): for row_index in range(len(grid)): for col_index in range(len(grid[0])): if finder(grid, row_index, col_index, word): print(f"{word} found.") return True print(f"{word} not found.") return False wordsearch_grid = [ ['E', 'N', 'I', 'G', 'M', 'A', '*'], ['B', '*', '*', '*', '*', '*', '*'], ['*', 'O', '*', '*', '*', '*', '*'], ['*', '*', 'T', '*', '*', '*', '*'], ['*', '*', '*', 'T', '*', '*', '*'], ['*', '*', '*', '*', 'L', '*', '*'], ['*', '*', '*', '*', '*', 'E', '*']] words = ["BOTTLE", "ENIGMA"] for word in words: find_word(wordsearch_grid, word)
- 运行上述测试代码的常规输出为:
BOTTLE not found. ENIGMA found.
- 但网格中实际存在合法的BOTTLE拼写路径。使用同一网格重复运行代码时,BOTTLE的查找结果会在“未找到”和“已找到”之间随机切换,ENIGMA始终能被正常定位。
- 之前尝试用PyCharm调试,但不清楚错误定位的切入点,且估算主循环运行次数可达2000次,逐次调试不具备可行性,需要排查求解器的逻辑问题。
问题原因排查
排查可运行代码后,求解器存在4个核心逻辑缺陷,是导致查找结果异常的直接原因:
- 递归未实现回溯逻辑
代码遍历邻居单元格时,只要碰到第一个和当前查找首字母匹配的坐标,就直接进入该分支递归,哪怕这个分支走到底也拼不出完整单词,也不会回退到当前位置,继续尝试其他同字母的邻居。只要第一个碰到的匹配分支是无效路径,整体查找就会直接判定失败,完全忽略后续可能存在的正确分支。 - 邻居列表包含当前位置
neighbors函数生成的坐标列表里,带着当前所在的(i, j)本身(对应行、列偏移都为0的情况)。递归查找时会优先匹配当前位置的字母,很容易抢占正确路径的遍历优先级,触发无效的自指递归。 - 无已访问路径标记
递归过程没有记录已经走过的单元格,很容易出现“从A格走到B格,又从B格走回A格”的循环遍历,直到触发Python默认的递归深度上限抛出栈溢出错误,直接中断整个查找流程。 - 边界判断逻辑不严谨
elems_within_bounds函数统一把坐标的两个分量和列索引的上限做比较,没有单独校验行、列的各自合法范围,在非正方形网格场景下会直接出现越界判断错误。
ENIGMA始终能被识别,是因为它的拼写路径位于网格第一行,每个步骤的下一个字母都是遍历邻居时第一个碰到的匹配项,没有被无效分支抢占优先级;而BOTTLE的正确路径刚好被自指的无效分支挡住,加上无标记的递归容易触发栈溢出,最终出现查找结果随机波动的现象。
修复方向
- 修改
neighbors函数,移除坐标为当前位置的自指项。 - 重构
finder函数的逻辑:首先校验当前位置的字母是否匹配待查单词的首字符,匹配成功后标记当前位置为已访问,遍历所有合法邻居递归匹配剩余字符,只要任意一个邻居分支返回匹配成功就整体返回结果;所有分支遍历完成仍未找到匹配时,取消当前位置的访问标记(回溯),返回查找失败。 - 调整边界判断逻辑,分别校验行、列坐标是否在合法范围内。
内容的提问来源于stack exchange,提问作者user15072974
相关产品推荐
相关产品推荐

