Hidato谜题生成器路径查找算法无限循环问题求助

核心问题分析 #

孔洞引入后，路径填充的回溯逻辑大概率陷入了重复访问同一单元格或死胡同循环——孔洞改变了网格连通性，但原代码的回溯条件未适配这种场景，导致循环无法终止。

具体排查方向 #

• 缺失已访问标记：如果回溯时没记录当前路径走过的单元格，很可能在孔洞周边反复绕圈。检查代码是否有visited集合/矩阵，推进路径时标记，回溯时移除标记。
• 回溯终止条件不全：当当前单元格无合法下一步（8方向邻居要么是孔洞、超出网格、已被路径占用），且当前数字未达目标最大值时，必须触发回溯而非继续循环。确认while循环的终止条件是否覆盖该场景。
• 邻居合法性判断错误：孔洞单元格应被排除在可走邻居之外，检查代码判断邻居时是否正确过滤了孔洞（比如if grid[neighbor_r][neighbor_c] == HOLE则跳过）。

修复示例思路 #

假设原代码回溯逻辑框架如下，补充关键缺失逻辑：

def find_path(grid, start_pos, max_num):
    current_pos = start_pos
    path_stack = [(current_pos, 1, set())]  # 栈元素：(当前位置, 当前数字, 已访问集合)
    
    while path_stack:
        pos, num, visited = path_stack.pop()
        if num == max_num:
            grid[pos[0]][pos[1]] = num
            return True
        
        # 标记当前位置为已访问
        visited.add(pos)
        grid[pos[0]][pos[1]] = num
        
        # 获取所有合法邻居：非孔洞、在网格内、未被访问
        neighbors = []
        for dr in [-1, 0, 1]:
            for dc in [-1, 0, 1]:
                if dr == 0 and dc == 0:
                    continue
                nr, nc = pos[0] + dr, pos[1] + dc
                if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
                    if grid[nr][nc] != "HOLE" and (nr, nc) not in visited:
                        neighbors.append((nr, nc))
        
        if neighbors:
            # 压回当前状态，准备回溯
            path_stack.append((pos, num, visited.copy()))
            # 推进到下一个数字
            next_pos = neighbors[0]
            path_stack.append((next_pos, num + 1, visited.copy()))
        else:
            # 死胡同，回溯：清空当前位置数字
            grid[pos[0]][pos[1]] = "EMPTY"
    
    return False

关键补充点：

1. 用visited集合跟踪当前路径单元格，彻底避免重复访问。
2. 无合法邻居时主动清空当前单元格并回溯，而非继续无效循环。
3. 严格过滤孔洞单元格，确保邻居列表仅包含可走位置。

大网格适配优化 #

针对7x7以上网格，可增加剪枝逻辑提升效率：

• 提前检查剩余未填充单元格（不含孔洞）数量是否等于max_num - 当前数字，不匹配则直接剪枝，避免无效回溯。
• 优先填充"唯一邻居"单元格（可用邻居数为1且非起点/终点），减少路径分支，降低回溯概率。

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