Python中的回溯寻路问题

Question

无论我在这段简短的代码块中进行什么更改，我都不会达到 38。

```

grid = [[0, 0,  0, 0,  0, 1],

        [0, 0,  0, 0,  0, 0],

        [0, 0,  0, 0,  0, 0],

        [1, 0,  0, 0,  0, 0]]

solution = 0

def number_of_paths(x, y):

    global solution

    global grid

    for i in range(0, x):

        for j in range(0, y):

            if grid[i][j] == 0:

                grid[i][j] = 1

                number_of_paths(x, y)

                grid[i][j] = 0

                solution += 1

    return

if __name__ == '__main__':

    number_of_paths(2, 3)

    print(grid)

    print(solution)```

这是一个使用数独求解器求解的示例解决方案。

```

grid = [[5, 3, 0, 0, 7, 0, 0, 0, 0], 

       [6, 0, 0, 1, 9, 5, 0, 0, 0],

       [0, 9, 8, 0, 0, 0, 0, 6, 0],

       [8, 0, 0, 0, 6, 0, 0, 0, 3],

       [4, 0, 0, 8, 0, 3, 0, 0, 1],

       [7, 0, 0, 0, 2, 0, 0, 0, 6],

       [0, 6, 0, 0, 0, 0, 2, 8, 0],

       [0, 0, 0, 4, 1, 9, 0, 0, 5], 

       [0, 0, 0, 0, 8, 0, 0, 7, 9]]

import numpy as np

def possible(y, x, n):

    global grid

    for i in range(0, 9):

        if grid[y][i] == n:

            return False

    for i in range(0, 9):

        if grid[i][x] == n:

            return False

    x0 = (x // 3) * 3

    y0 = (y // 3) * 3

    for i in range(0, 3):

        for j in range(0, 3):

            if grid[y0 + i][x0 + j] == n:

                return False

    return True

def solve():

    global grid

    for y in range(9):

        for x in range(9):

            if grid[y][x] == 0:

                for n in range(1, 10):

                    if possible(y, x, n):

                        grid[y][x] = n

                        solve()

                        # backtracking - bad choice

                        grid[y][x] = 0

                return

    print(np,matrix(grid))

    input("More?")```

Answer 1

一些建议：您可能希望将集合用于网格，如果它还不是集合的成员，则在访问它时立即添加一个正方形。计数器和网格可以是全局的，但一开始将它们作为函数的参数可能会更容易。当解决方案更加清晰之后，您就可以担心这些细节了。你解决问题的方式是错误的。最好有一个函数计算从起点到目的地的路径数（通过调用尚未访问过的邻居的函数。确保更新网格）。最重要的是，您可以有一个函数为起点和终点的每个组合调用路径函数。一个小提示：您不必反向计算相同的路径！您可以获得计算路径总和的地图。如果相反的方向已经计算出来了，就不用麻烦了。随后，将路径数量加倍 2。祝你好运！

Answer 2

我将向您展示坐标系上的解决方案，其中 (0,0) 是左上角，(maxY,maxX) 是机器人右侧。向右移动会增加 x，向下移动会增加 y。1-如果您试图解决图像中的精确迷宫问题，那么您的网格阵列形状是错误的。请注意，您在正方形的角之间移动，有 4 个点可以水平移动，3 个点可以垂直移动。2-提示告诉您有关对访问状态使用布尔掩码，您已经有一个网格数组，因此不需要单独的数组。3-您的代码的主要问题是您在迷宫中的进展情况。循环结构for&nbsp;i&nbsp;in&nbsp;range(0,&nbsp;x): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;j&nbsp;in&nbsp;range(0,&nbsp;y):没有意义，因为当你处于 (x, y) 位置时，你只能向 4 个主要方向移动（右、上、左、下）。然而，这个循环让你看起来像是在尝试分支到你身后的所有位置，这是无效的。在我的代码中，我将明确展示这个遍历的东西。grid = [[0, 0, 0, 0],&nbsp; &nbsp; &nbsp; &nbsp; [0, 0, 0, 0],&nbsp; &nbsp; &nbsp; &nbsp; [1, 0, 0, 0]]#&nbsp; number of solutionssolution = 0#&nbsp; maximum values of x and y coordinatesmaxX = len(grid[0])-1maxY = len(grid)-1#&nbsp; endpoint coordinates, top(y=0) right(x=maxX) of the mazeendX = maxXendY = 0#&nbsp; starting point coordinates, bottom(y=maxY) left(x=0) of the mazemazeStartX = 0mazeStartY = maxYdef number_of_paths(startX, startY):&nbsp; &nbsp; global solution&nbsp; &nbsp; global grid&nbsp; &nbsp; global mask&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; #&nbsp; if we reached the goal, return at this point&nbsp; &nbsp; if (startX == endX and startY == endY):&nbsp; &nbsp; &nbsp; &nbsp; solution += 1&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; #&nbsp; possible directions are&nbsp;&nbsp; &nbsp; #RIGHT (+1x, 0y)&nbsp; &nbsp; #UP (0x, -1y)&nbsp; &nbsp; #LEFT (-1x, 0y)&nbsp; &nbsp; #DOWN (0x, +1y)&nbsp; &nbsp; #&nbsp; I use a direction array like this to avoid nested ifs inside the for loop&nbsp; &nbsp; dx = [1, 0, -1, 0]&nbsp; &nbsp; dy = [0, -1, 0, 1]&nbsp; &nbsp;&nbsp; &nbsp; for d in range(len(dx)):&nbsp; &nbsp; &nbsp; &nbsp; newX = startX + dx[d]&nbsp; &nbsp; &nbsp; &nbsp; newY = startY + dy[d]&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; #&nbsp; out of maze bounds&nbsp; &nbsp; &nbsp; &nbsp; if (newX < 0 or newY < 0):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; #&nbsp; out of maze bounds&nbsp; &nbsp; &nbsp; &nbsp; if (newX > maxX or newY > maxY):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; if (grid[newY][newX] == 1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; #&nbsp; this are is already visited&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; #&nbsp; branch from this point&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; grid[newY][newX] = 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; number_of_paths(newX, newY)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; grid[newY][newX] = 0if __name__ == '__main__':&nbsp; &nbsp; number_of_paths(mazeStartX, mazeStartY)&nbsp; &nbsp; print(grid)&nbsp; &nbsp; print(solution)