Python中的回溯路径问题

Question

最近，我发现了回溯，没有太多思考就从一个展示了一些数独回溯技巧的家伙那里开始了这本书(https://www.youtube.com/watch?v=G_UYXzGuqvM

这个问题被相应地表述为：使用回溯计算x*y网格中从左下角到右上角的所有路径的数量。这包括以下路径：https://imgur.com/3t3Np4M.请注意，每个点只能访问一次。编写一个函数np（x，y），返回x*y网格中的路径数。例如，np（2,3）应该返回38。提示：创建一个布尔网格，在其中标记已访问的位置。

无论我在这段短代码中做了什么改变，我都不会接近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

我将展示一个坐标系上的解决方案，其中（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)

Answer 2

一些建议：

1. 您可能希望将一个集合用于网格，如果它不是集合的成员，则在访问它时立即添加一个正方形
2. 计数器和网格可以是全局的，但一开始可能更容易将它们作为函数的参数。在解决方案更清晰之后，你可以担心这些细节
3. 你处理这个问题的方式不对。最好有一个函数来计算从起点到终点的路径数（通过为尚未访问的邻居调用该函数。确保更新网格）。除此之外，您还可以有一个函数，该函数为起点和终点的每个组合调用路径函数。小贴士：你不必反向计算同一条路径！你可以有一张计算路径和的地图。如果相反的方向已经被计算过了，就不用麻烦了。之后，将路径数量加倍2

祝你好运