python - 递归地找到所有可能的路径，在每个节点上具有一定数量的移动和不同的选项

Question

我有一个 5 x 5 的网格。每个网格都是一个具有 id、值（最初为空）和可能的移动集的对象。可能的移动集是给定网格上的任何位置，它可以移动到当前网格 ID 的 -16、-21、-12、-3、3、12、21、16 的任何新位置，但该位置不能小于 1 或大于 25（因为网格是 25 个位置）并且不能已经被占用。目标是用数字 1-25 填充整个网格，数字是定位在那里的移动的数字。但是每个起始位置不一定只有一条路线，所以我想找到网格上给定起点的所有可能路径。

我的网格创建工作正常，以及从可能的选项中选择下一个。我的问题涉及几个方面，如果选择的路径是死胡同，则回滚以选择不同的路径，或者如果反复失败，则回滚多个选择级别。另外在找到一条路径后查找所有路径。

如上所示，例如，如果我从 13 的中心开始，我可以移动到 2，然后是 17，等等。如果我卡住了，我会回到前一点并尝试另一个选项。我会在那个级别尝试所有可能的选项，但如果这是一个死胡同，我会回到另一个级别。这个想法是找到一条使用所有 25 个单元格的路径

鉴于以下代码。我可以在选择的 25 轮中进入第 17 轮，但我似乎无法进一步回溯以找到一条完整的路径，更不用说多条了：

grid_size = 25

grid = {}
grid_list = []
#initialise grid details
pos_moves=[-16,-21,-12,-3,3,12,21,16 ]
### give all possible moves for this

x = 1
while x <= grid_size:
    moves =[]
    for i in pos_moves:
        if 0 < (x + i) < 26:
            moves.append(x + i)
    #print(moves)
    grid[x] ={ "id" : x, "moves" : moves}
    grid_list.append({"id":x})
    x += 1
    
print(grid)

visited = {}

next_location = int
round_level = 1


def choose_path(current_location):
    global round_level
    global next_location
    options = grid[current_location]['moves']
    print("################## Round " + str(round_level) + "##################\n" +
          "current grid area: " + str(current_location) + "\n"
          "current options: " + str(options) + "\n"
                  )
    next_location = options.pop(0)
    if next_location not in visited:
        visited[next_location] = options
        print("Remaining options: " + str(options) + " chosen option" + str(next_location))
        print("visited:  " + str(visited))
        round_level += 1
        return choose_path(next_location)
    elif next_location in visited:
        if len(options) == 0:
            print("Visited:   " + ",".join(str(key) for key in visited))
            print("stopping here")
        else:
            next_location = options.pop(0)
            return  choose_path(next_location)



choose_path(13)

标签： pythonalgorithmrecursionpath-finding