Python 中的回溯寻路问题

Question

最近，我从展示了一些数独回溯技巧 (https://www.youtube.com/watch?v=G_UYXzGuqvM&ab_channel=Computerphile 的人那里发现了回溯，并且没有多想就开始阅读这本书 (https://www.youtube.com/watch?v=G_UYXzGuqvM&ab_channel=Computerphile。不幸的是，我被第一个回溯问题困住了没有解决方案。

问题据此制定：使用回溯法计算一个图中从左下角到右上角的所有路径的数量 x * y 网格。这包括像 https://imgur.com/3t3Np4M 这样的路径。请注意，每个点只能访问一次。编写一个函数 np(x,y) 使 returns 是 x*y 网格中的路径数。例如。 np(2,3) 应该 return 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

几点建议：

您可能希望对网格使用集合，如果它还不是集合的成员，则在访问它时立即添加一个正方形。
计数器和网格可以是全局的，但一开始将它们作为函数的参数可能更容易。解决方案更清晰后，您可以担心那些细节。
您正在以错误的方式解决问题。最好有一个函数来计算从起点到终点的路径数（通过为尚未访问过的邻居调用该函数。确保更新网格）。最重要的是，您可以拥有一个函数，为起点和终点的每个组合调用路径函数。一个小提示：您不必计算相反方向的相同路径！你可以有一张计算路径总和的地图。如果已经计算出相反的方向，请不要打扰。稍后，将路径数量加倍 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)

Python 中的回溯寻路问题

Backtracking pathinding problem in Python

python

algorithm

numpy

sudoku

backtracking