试图创建一个解决迷宫的程序，但它卡在了特定的路径上

Question

所以，基本上，我正在尝试编写一个解决迷宫的程序。我用不同的迷宫做了很多测试，我意识到我的程序无法解决所有类型的迷宫，只能解决一些，因为有一些特定的死胡同，我的程序会卡住并且无法返回。

我的代码背后的逻辑基本上是在迷宫中运行，直到找到出口，并且，如果在此过程中发现死胡同，它应该能够返回并找到一条新的未探索路径.

我的代码运行良好，直到我开始使用具有各种棘手死胡同的更复杂的迷宫对其进行测试。例如：

maze = (
                [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
                [1,0,1,1,1,0,1,1,1,1,1,1,1,1,1],
                [1,0,0,0,0,0,0,0,1,0,0,0,0,0,1],
                [1,1,1,0,1,1,1,0,1,0,1,0,1,0,1],
                [1,1,1,0,1,0,1,0,1,0,1,1,1,0,1],
                [1,1,1,1,1,0,1,0,1,0,0,1,0,0,1],
                [1,1,0,0,0,0,1,0,1,1,0,1,0,1,1],
                [1,1,0,1,1,0,0,0,0,1,0,1,0,1,1],
                [1,1,0,0,1,1,0,1,0,1,0,1,0,0,1],
                [1,1,0,1,0,0,1,0,0,0,1,0,0,1,1],
                [1,1,1,1,1,1,1,1,1,1,1,3,1,1,1]
                                                )

这是我的程序可以解决的有死胡同的迷宫示例，因此 1 是墙，0 是自由路径，3 是终点，起点是 maze[1][1]

maze = (
                [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
                [1,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
                [1,0,1,1,1,0,1,1,1,1,1,1,0,1,1],
                [1,0,1,0,0,0,0,0,0,1,1,1,0,1,1],
                [1,0,0,0,1,1,1,1,0,0,0,1,0,0,1],
                [1,1,0,1,1,0,0,1,1,1,0,1,1,0,1],
                [1,1,0,1,1,1,0,0,0,1,0,1,0,0,1],
                [1,0,0,1,1,1,1,1,0,1,0,1,1,0,1],
                [1,0,1,1,0,0,0,0,0,1,0,0,0,0,1],
                [1,0,0,0,0,1,1,1,1,1,0,1,1,1,1],
                [1,1,1,1,1,1,1,1,1,1,3,1,1,1,1]
                                                )

现在是我的程序无法解决的迷宫。我想这个迷宫的问题在于它有一个 "L" 形状或类似之字形的死胡同，但老实说，我不知道发生了什么。例如，maze[5][5] 中的死胡同（我的程序卡在那里）

在展示代码之前我想解释一些关于它的话题：

我打印的所有字符串都是英语和葡萄牙语，语言之间用“/”分隔，所以不用担心。
为了探索迷宫，程序使用递归策略并用 2 标记探索的路径。
程序使用基于数组的 x 和 y 坐标。 x + 1 向下，x - 1 向上，y + 1 向右，y - 1 向左。
如果陷入死胡同，策略是查看周围的情况以发现它是哪种死胡同，然后返回，直到找到标记为 0 的新路径。

这些是您将在我的代码中看到的死胡同。

如果可能的话，我想要一些关于如何改进我的代码或使其更干净的提示。

那么，我们开始吧：

maze = (
                [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
                [1,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
                [1,0,1,1,1,0,1,1,1,1,1,1,0,1,1],
                [1,0,1,0,0,0,0,0,0,1,1,1,0,1,1],
                [1,0,0,0,1,1,1,1,0,0,0,1,0,0,1],
                [1,1,0,1,1,0,0,1,1,1,0,1,1,0,1],
                [1,1,0,1,1,1,0,0,0,1,0,1,0,0,1],
                [1,0,0,1,1,1,1,1,0,1,0,1,1,0,1],
                [1,0,1,1,0,0,0,0,0,1,0,0,0,0,1],
                [1,0,0,0,0,1,1,1,1,1,0,1,1,1,1],
                [1,1,1,1,1,1,1,1,1,1,3,1,1,1,1]
                                                )


def solve(x, y):

    if maze[x][y] == 0 or maze[x][y] == 2:
        # To walk around and explore the maze
        print('Visiting/Visitando xy({},{})'.format(x, y))
        maze[x][y] = 2
        if x < (len(maze) - 1) and (maze[x + 1][y] == 0 or maze[x + 1][y] == 3):
            solve(x + 1, y)
        elif y < (len(maze) - 1) and (maze[x][y + 1] == 0 or maze[x][y + 1] == 3):
            solve(x, y + 1)
        elif x > 0 and (maze[x - 1][y] == 0 or maze[x][y + 1] == 3):
            solve(x - 1, y)
        elif y > 0 and (maze[x][y - 1] == 0 or maze[x][y + 1] == 3):
            solve(x, y - 1)

        else:
            # If it gets stuck in a dead end
            step_back = 1
            dead_end = True
            # each possible kind of dead ends and the strategy to go back
            if (maze[x + 1][y] == 1 or maze[x + 1][y] == 2) and maze[x][y - 1] == 1 and \
                    maze[x][y + 1] == 1 and maze[x - 1][y] == 2:

                print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
                while dead_end is True:
                    if maze[x - step_back][y - 1] == 0 or maze[x - step_back][y - 1] == 3:
                        solve(x - step_back, y - 1)
                    elif maze[x - step_back][y + 1] == 0 or maze[x - step_back][y + 1] == 3:
                        solve(x - step_back, y + 1)
                    else:
                        print("Going back/Voltando")
                        dead_end = False
                        step_back += 1
                        solve(x - step_back, y)

            elif (maze[x - 1][y] == 1 or maze[x - 1][y] == 2) and maze[x][y - 1] == 1 and \
                    maze[x][y + 1] == 1 and maze[x + 1][y] == 2:
                print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
                while dead_end is True:
                    if maze[x + step_back][y - 1] == 0 or maze[x - step_back][y - 1] == 3:
                        solve(x + step_back, y - 1)
                    elif maze[x + step_back][y + 1] == 0 or maze[x - step_back][y + 1] == 3:
                        solve(x + step_back, y + 1)
                    else:
                        print("Going back/Voltando")
                        dead_end = False
                        step_back += 1
                        solve(x + step_back, y)

            elif (maze[x][y + 1] == 1 or maze[x][y + 1] == 2) and maze[x + 1][y] == 1 and \
                    maze[x - 1][y] == 1 and maze[x][y - 1] == 2:
                print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
                while dead_end is True:
                    if maze[x][y - step_back] == 0 or maze[x][y - step_back] == 3:
                        solve(x - step_back, y)
                    elif maze[x][y + step_back] == 0 or maze[x][y + step_back] == 3:
                        solve(x + step_back, y)
                    else:
                        print("Going back/Voltando")
                        dead_end = False
                        step_back += 1
                        solve(x, y + step_back)

            elif (maze[x][y - 1] == 1 or maze[x][y - 1] == 2) and maze[x + 1][y] == 1 and \
                    maze[x - 1][y] == 1 and maze[x][y + 1] == 2:
                print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
                while dead_end is True:
                    if maze[x][y - step_back] == 0 or maze[x][y - step_back] == 3:
                        solve(x - step_back, y)
                    elif maze[x][y + step_back] == 0 or maze[x][y + step_back] == 3:
                        solve(x + step_back, y)
                    else:
                        print("Going back/Voltando")
                        dead_end = False
                        step_back += 1
                        solve(x, y - step_back)

    # to check if the end of the maze were found
    if maze[x + 1][y] == 3 or maze[x - 1][y] == 3 or maze[x][y + 1] == 3 or maze[x][y - 1] == 3:
        print('Exit found in/Saída encontrada em xy({},{})'.format(x, y))


solve(1,1)

Answer 1

一个简单的bfs/dfs就足以解决这个问题。只需从初始位置开始并跟踪所有已覆盖的节点。如果您到达任何死胡同或重复任何位置，您可以终止此路径。如果到达最终状态，则输出当前路径。

您可以找到有关此算法的更多信息here。

试图创建一个解决迷宫的程序，但它卡在了特定的路径上

Trying to create a program that solves mazes, but it is getting stuck in specific paths

python

algorithm

maze

artificial-intelligence