You need to enable JavaScript to run this app. Python递归回溯单词搜索算法无法定位网格内已存在单词的问题
优惠活动
大模型
产品
解决方案
定价
更多

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个核心逻辑缺陷,是导致查找结果异常的直接原因:

  1. 递归未实现回溯逻辑
    代码遍历邻居单元格时,只要碰到第一个和当前查找首字母匹配的坐标,就直接进入该分支递归,哪怕这个分支走到底也拼不出完整单词,也不会回退到当前位置,继续尝试其他同字母的邻居。只要第一个碰到的匹配分支是无效路径,整体查找就会直接判定失败,完全忽略后续可能存在的正确分支。
  2. 邻居列表包含当前位置
    neighbors函数生成的坐标列表里,带着当前所在的(i, j)本身(对应行、列偏移都为0的情况)。递归查找时会优先匹配当前位置的字母,很容易抢占正确路径的遍历优先级,触发无效的自指递归。
  3. 无已访问路径标记
    递归过程没有记录已经走过的单元格,很容易出现“从A格走到B格,又从B格走回A格”的循环遍历,直到触发Python默认的递归深度上限抛出栈溢出错误,直接中断整个查找流程。
  4. 边界判断逻辑不严谨
    elems_within_bounds函数统一把坐标的两个分量和列索引的上限做比较,没有单独校验行、列的各自合法范围,在非正方形网格场景下会直接出现越界判断错误。

ENIGMA始终能被识别,是因为它的拼写路径位于网格第一行,每个步骤的下一个字母都是遍历邻居时第一个碰到的匹配项,没有被无效分支抢占优先级;而BOTTLE的正确路径刚好被自指的无效分支挡住,加上无标记的递归容易触发栈溢出,最终出现查找结果随机波动的现象。

修复方向
  • 修改neighbors函数,移除坐标为当前位置的自指项。
  • 重构finder函数的逻辑:首先校验当前位置的字母是否匹配待查单词的首字符,匹配成功后标记当前位置为已访问,遍历所有合法邻居递归匹配剩余字符,只要任意一个邻居分支返回匹配成功就整体返回结果;所有分支遍历完成仍未找到匹配时,取消当前位置的访问标记(回溯),返回查找失败。
  • 调整边界判断逻辑,分别校验行、列坐标是否在合法范围内。

内容的提问来源于stack exchange,提问作者user15072974

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.28 12:54:01