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 = 0def 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    returnif __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 npdef 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 Truedef 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

一些建议：

1. 您可能希望将集合用于网格，如果它还不是集合的成员，则在访问它时立即添加一个正方形。

2. 计数器和网格可以是全局的，但一开始将它们作为函数的参数可能会更容易。当解决方案更加清晰之后，您就可以担心这些细节了。

3. 你解决问题的方式是错误的。最好有一个函数计算从起点到目的地的路径数（通过调用尚未访问过的邻居的函数。确保更新网格）。最重要的是，您可以有一个函数为起点和终点的每个组合调用路径函数。一个小提示：您不必反向计算相同的路径！您可以获得计算路径总和的地图。如果相反的方向已经计算出来了，就不用麻烦了。随后，将路径数量加倍 2。

祝你好运！

Answer 2

我将向您展示坐标系上的解决方案，其中 (0,0) 是左上角，(maxY,maxX) 是机器人右侧。向右移动会增加 x，向下移动会增加 y。
1-如果您试图解决图像中的精确迷宫问题，那么您的网格阵列形状是错误的。请注意，您在正方形的角之间移动，有 4 个点可以水平移动，3 个点可以垂直移动。
2-提示告诉您有关对访问状态使用布尔掩码，您已经有一个网格数组，因此不需要单独的数组。
3-您的代码的主要问题是您在迷宫中的进展情况。循环结构

for i in range(0, x):
        for j in range(0, y):

没有意义，因为当你处于 (x, y) 位置时，你只能向 4 个主要方向移动（右、上、左、下）。然而，这个循环让你看起来像是在尝试分支到你身后的所有位置，这是无效的。在我的代码中，我将明确展示这个遍历的东西。

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

        [0, 0, 0, 0],

        [1, 0, 0, 0]]

#  number of solutions

solution = 0

#  maximum values of x and y coordinates

maxX = len(grid[0])-1

maxY = len(grid)-1

#  endpoint coordinates, top(y=0) right(x=maxX) of the maze

endX = maxX

endY = 0

#  starting point coordinates, bottom(y=maxY) left(x=0) of the maze

mazeStartX = 0

mazeStartY = maxY

def number_of_paths(startX, startY):

    global solution

    global grid

    global mask

    

    

    #  if we reached the goal, return at this point

    if (startX == endX and startY == endY):

        solution += 1

        return

    

    

    #  possible directions are 

    #RIGHT (+1x, 0y)

    #UP (0x, -1y)

    #LEFT (-1x, 0y)

    #DOWN (0x, +1y)

    #  I use a direction array like this to avoid nested ifs inside the for loop

    dx = [1, 0, -1, 0]

    dy = [0, -1, 0, 1]

   

    for d in range(len(dx)):

        newX = startX + dx[d]

        newY = startY + dy[d]

        

        #  out of maze bounds

        if (newX < 0 or newY < 0):

            continue

        

        #  out of maze bounds

        if (newX > maxX or newY > maxY):

            continue

            

       

        if (grid[newY][newX] == 1):

            #  this are is already visited 

            continue

        else:

            #  branch from this point

            grid[newY][newX] = 1

            number_of_paths(newX, newY)

            grid[newY][newX] = 0

if __name__ == '__main__':

    number_of_paths(mazeStartX, mazeStartY)

    print(grid)

    print(solution)