使用Python找到所有迷宫解决方案

Question

我正在尝试使用Python找到迷宫的所有可能解决方案。我有一个深度优先搜索脚本，可以返回一个解决方案。我正在尝试进行调整，但是我真的很难理解整个递归的过程。

这是我拥有的用于使用DFS查找一个可能解决方案的代码:

任何提示或帮助将不胜感激！（数组中的“lett”可以被忽略/视为常规“路径”）

def DFS(x,y,Map):
    if (Map[x][y]=="exit"):                             #check if we're at the exit
        return [(x,y)]                                  #if so then we solved it so return this spot
    if ((Map[x][y]!="path") and (Map[x][y]!="lett")):   #if it's not a path, we can't try this spot
        return []
    Map[x][y]="explored"                                #make this spot explored so we don't try again
    for i in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:         #new spots to try
        result = DFS(i[0],i[1],Map)                     #recursively call itself
        if len(result)>0:                               #if the result had at least one element, it found a correct path, otherwise it failed
            result.append((x,y))                        #if it found a correct path then return the path plus this spot
            return result
    return []                                           #return the empty list since we couldn't find any paths from here

def GetMap():
    return [
        ["wall","wall","wall","wall","wall","wall","wall","wall"],
        ["wall","path","path","path","path","path","path","wall"],
        ["wall","wall","wall","path","wall","lett","path","wall"],
        ["wall","path","path","path","wall","wall","path","wall"],
        ["wall","path","wall","lett","path","path","path","wall"],
        ["wall","path","wall","wall","wall","wall","path","wall"],
        ["wall","path","lett","path","path","path","exit","wall"],
        ["wall","wall","wall","wall","wall","wall","wall","wall"]
    ]

def DrawMap(Map,path):
    for x in range(0,len(Map)):
        for y in range(0,len(Map[x])):
            if ((x,y) in path):
                assert Map[x][y] in ("path","lett","exit")
                print("-",end="")
            elif (Map[x][y]=="wall"):
                print("#",end="")
            elif (Map[x][y]=="exit"):
                print("e",end="")
            elif (Map[x][y]=="lett"):
                print("L",end="")
            else:
                print(' ',end="")
        print()

print("\nUnsolved:\n")
DrawMap(GetMap(),[])
print("\n")

print("Solved with DFS:")
print("path is ",len(DFS(1,1,GetMap()))," spots long\n")
DrawMap(GetMap(),DFS(1,1,GetMap()))
print("\n")

- Deryckere Frederico

---

我看到脚本是有效的，所以我不确定你的问题是什么。 - DapperDuck

我想要一个包含所有可能解决方案的列表。 - Deryckere Frederico

重写DFS，以便返回从（x，y）开始到达出口的所有路径列表。然后，您的递归调用变成了“一个双重嵌套的for循环，在其中循环遍历下一个点和它们返回的解决方案。”警告。在返回之前，您需要撤消Map [x，y] =“explored”，并在返回之前将其放回其先前的值。 - Frank Yellin

Answer 1

美好的愿望

像这样的问题一开始可能会让人感到不知所措，但是编程中我最喜欢的技巧可以使复杂性消失得无影无踪。使用美好的愿望，我们按照我们希望程序能够实现的方式编写程序，然后我们让我们的愿望成真-

# simple.py

from maze import maze
from cursor import cursor

def dfs(cursor, maze):
  q = maze.get(cursor.y(), cursor.x())
  if not q or q.is_wall() or q.is_step():
    return
  elif q.is_exit():
    yield maze
  else:
    next_maze = maze.step(cursor.y(), cursor.x())
    yield from dfs(cursor.up(), next_maze)
    yield from dfs(cursor.down(), next_maze)
    yield from dfs(cursor.right(), next_maze)
    yield from dfs(cursor.left(), next_maze)

def solve(cursor, maze):
  for x in dfs(cursor, maze):
    return x

我们所需要的只是一个迷宫 m 和一个光标 c -。

# simple.py (continued)

# read maze from file
m = maze.from_file("./input")

# initialize cursor
c = cursor.from_ints(1, 1)

我们可以使用 solve 找到第一个解决方案 -

# simple.py (continued)

print(solve(c, m))

########
#---   #
###-#L #
#  -## #
# #----#
# ####-#
# L   e#
########

或者我们可以使用 dfs 查找 所有的 解决方案 -

# simple.py (continued)

for x in dfs(c, m):
  print(x, end="\n\n")

以下输出已重新格式化以节省空间。

########   ########   ########   ########   ########   ########
#---   #   #---   #   #----- #   #----- #   #------#   #------#
###-#L #   ###-#L #   ### #--#   ### #--#   ### #L-#   ### #L-#
#  -## #   #---## #   #   ##-#   #---##-#   #   ##-#   #---##-#
# #----#   #-#L   #   # #L  -#   #-#----#   # #L  -#   #-#----#
# ####-#   #-#### #   # ####-#   #-#### #   # ####-#   #-#### #
# L   e#   #-----e#   # L   e#   #-----e#   # L   e#   #-----e#
########   ########   ########   ########   ########   ########

---

光标

为了使上面的程序正常运行，我们需要满足所有的愿望。我们将从光标模块开始。光标只是一对整数，它给我们提供了方便的向上、向下、向左和向右移动-

# cursor.py

def from_ints(y, x):
  return (y, x)

def up(t):
  (y, x) = t
  return from_ints(y - 1, x)

def down(t):
  (y, x) = t
  return from_ints(y + 1, x)

def left(t):
  (y, x) = t
  return from_ints(y, x - 1)

def right(t):
  (y, x) = t
  return from_ints(y, x + 1)

def to_str(t):
  (y, x) = t
  return f"({y}, {x})"

如您所见，我们正在使用普通函数进行工作。Python也具有良好的面向对象特性，我们希望将这种便利扩展到我们模块的用户中。我们可以通过包装普通函数轻松添加面向对象接口-

# cursor.py (continued)

class cursor:
  def from_ints(y, x): return cursor(from_ints(y, x))
  def __init__(self, t): self.t = t
  def __iter__(self): yield from self.t
  def __str__(self): return to_str(self.t)
  def up(self): return cursor(up(self.t))
  def down(self): return cursor(down(self.t))
  def right(self): return cursor(right(self.t))
  def left(self): return cursor(left(self.t))

---

迷宫

现在我们开始介绍maze模块。我们将首先编写普通函数，将from_file转换为迷宫，并将迷宫转换为字符串to_str -

# maze.py

from cell import cell

def from_file(filename):
  with open(filename) as f:
    return from_str(f.read())

def from_str(s):
  return [ list(map(cell.from_str, row)) for row in s.split("\n") ]

def to_str(t):
  return "\n".join("".join(map(str, row)) for row in t)

作为额外的奖励，注意我们免费获得了from_str。接下来，我们编写函数使用y和x坐标来get或set单元格。在这里，我们还编写了step，它是set的一个简单包装器，用于标记迷宫中已被探索的单元格。

# maze.py (continued)

from arr_ext import update

def get(t, y, x):
  try:
    if x < 0 or y < 0:
      return None
    else:
      return t[y][x]
  except IndexError:
    return None

def set(t, y, x, v):
  return update \
    ( t
    , y
    , lambda row: update(row, x, lambda _: v)
    )

def step(t, y, x):
  return set(t, y, x, cell.step())

不要害怕尽情许下你想要的愿望。我们会在需要时实现 update 。就像我们在之前的模块中所做的那样，我们添加面向对象的接口 -

# maze.py (continued)

class maze:
  def from_file(filename): return maze(from_file(filename))
  def from_str(s): return maze(from_str(s))
  def __init__(self, t): self.t = t
  def __iter__(self): yield from self.t
  def __str__(self): return to_str(self.t)
  def get(self, y, x): return get(self.t, y, x)
  def set(self, y, x, v): return maze(set(self.t, y, x, v))
  def step(self, y, x): return maze(step(self.t, y, x))

---

单元格

在编写迷宫模块时，我们希望有一个cell模块。现在应该可以看出心想事成的技巧了：许个愿望，实现它。我们的Cell模块代表着迷宫中的一个单元格。我们从一个方法开始，将from_str转换为一个单元格，并且从一个单元格to_str。

# cell.py

wall = 0
path = 1
exit = 2
lett = 3
step = 4

str_to_cell = \
  { "#": wall, " ": path, "e": exit, "L": lett, "-": step }

cell_to_str = \
  { v: k for (k, v) in str_to_cell.items() }

def from_str(s):
  if s in str_to_cell:
    return str_to_cell[s]
  else:
    raise RuntimeError(f"invalid cell character: {s}")

def to_str(t):
  if t in cell_to_str:
    return cell_to_str[t]
  else:
    raise RuntimeError(f"invalid cell component: {t}")

此外，我们编写 is_* 谓词来判断单元格是否为 wall，path 等。这突显了抽象的优势：我们可以在一个模块中更改数据的表示方式，而无需修改程序中的其他模块。

# cell.py (continued)

def is_wall(t): return t == wall
def is_path(t): return t == path
def is_exit(t): return t == exit
def is_lett(t): return t == lett
def is_step(t): return t == step

添加面向对象的接口。它只是我们普通函数的简单包装器。

# cell.py (continued)

class cell:
  def from_str(s): return cell(from_str(s))
  def wall(): return cell(wall)
  def path(): return cell(path)
  def exit(): return cell(exit)
  def lett(): return cell(lett)
  def step(): return cell(step)
  def __init__(self, t): self.t = t
  def __str__(self): return to_str(self.t)
  def is_wall(self): return is_wall(self.t)
  def is_path(self): return is_path(self.t)
  def is_exit(self): return is_exit(self.t)
  def is_lett(self): return is_lett(self.t)
  def is_step(self): return is_step(self.t)

---

arr_ext

只剩下一个愿望了！我们将在一个数组扩展模块 arr_ext 中编写通用的 update 函数。

# arr_ext.py

def update(t, pos, f):
  try:
    return [ *t[:pos], f(t[pos]), *t[pos + 1:]]
  except IndexError:
    return t

---

高级

我们的简单程序用简化的方式解决了问题。如果我们想要解决迷宫并知道每个解决方案的路径怎么办？让我们编写一个高级程序 -

# advanced.py

from maze import maze
from cursor import cursor

def dfs(cursor, maze, path=[]):
  q = maze.get(*cursor)
  if not q or q.is_wall() or q.is_step():
    return
  elif q.is_exit():
    yield (maze, path)
  else:
    next_maze = maze.step(*cursor)
    next_path = [*path, cursor]
    yield from dfs(cursor.up(), next_maze, next_path)
    yield from dfs(cursor.down(), next_maze, next_path)
    yield from dfs(cursor.right(), next_maze, next_path)
    yield from dfs(cursor.left(), next_maze, next_path)

def solve(cursor, maze):
  for x in dfs(cursor, maze):
    return x

注意，高级解决方案只是简单模块的微小调整。让我们看看第一个解决的迷宫长什么样子 -

# advanced.py (continued)

print(solution(solve(c, m)))

########
#---   #
###-#L #
#  -## #
# #----#
# ####-#
# L   e#
########
(1, 1)->(1, 2)->(1, 3)->(2, 3)->(3, 3)->(4, 3)->(4, 4)->(4, 5)->(4, 6)->(5, 6)

现在让我们来看看所有已解决的迷宫和路径 -

# advanced.py (continued)

for x in dfs(c, m):
  print(solution(x), end="\n\n")

########
#---   #
###-#L #
#  -## #
# #----#
# ####-#
# L   e#
########
(1, 1)->(1, 2)->(1, 3)->(2, 3)->(3, 3)->(4, 3)->(4, 4)->(4, 5)->(4, 6)->(5, 6)

########
#---   #
###-#L #
#---## #
#-#L   #
#-#### #
#-----e#
########
(1, 1)->(1, 2)->(1, 3)->(2, 3)->(3, 3)->(3, 2)->(3, 1)->(4, 1)->(5, 1)->(6, 1)->(6, 2)->(6, 3)->(6, 4)->(6, 5)

########
#----- #
### #--#
#   ##-#
# #L  -#
# ####-#
# L   e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(2, 5)->(2, 6)->(3, 6)->(4, 6)->(5, 6)

########
#----- #
### #--#
#---##-#
#-#----#
#-#### #
#-----e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(2, 5)->(2, 6)->(3, 6)->(4, 6)->(4, 5)->(4, 4)->(4, 3)->(3, 3)->(3, 2)->(3, 1)->(4, 1)->(5, 1)->(6, 1)->(6, 2)->(6, 3)->(6, 4)->(6, 5)

########
#------#
### #L-#
#   ##-#
# #L  -#
# ####-#
# L   e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(1, 6)->(2, 6)->(3, 6)->(4, 6)->(5, 6)

########
#------#
### #L-#
#---##-#
#-#----#
#-#### #
#-----e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(1, 6)->(2, 6)->(3, 6)->(4, 6)->(4, 5)->(4, 4)->(4, 3)->(3, 3)->(3, 2)->(3, 1)->(4, 1)->(5, 1)->(6, 1)->(6, 2)->(6, 3)->(6, 4)->(6, 5)

不要忘记实现你的愿望！我们可以看到一个新模块solution的出现，但这次我们将把它留在同一个文件中 -

# advanced.py (continued)

def to_str(t):
  (maze, path) = t
  return str(maze) + "\n" + "->".join(map(str, path))

class solution:
  def __init__(self, t): self.t = t
  def __str__(self): return to_str(self.t)

- Mulan

---

老兄，你太棒了，这个社区真是太神奇了！ - Deryckere Frederico

Answer 2

這是你要的：

更新後的DFS：

def DFS(x,y,Map):                                    
    if (Map[x][y]=="exit"):                          
        return [[(x,y)]]                             
    if ((Map[x][y]!="path") and (Map[x][y]!="lett")):
        return []                                    
    stat = Map[x][y]                                 
    Map[x][y]="explored"                             
    my_results = []                                     
    for i in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:      
        results = DFS(i[0],i[1],Map)                   
        for res in results:                            
            if len(res)>0:                           
                res.append((x,y))                    
                my_results.append(res)                  
    Map[x][y] = stat                                 
    return my_results                                   

更新的输出：

print("\nUnsolved:\n")                           
DrawMap(GetMap(),[])                             
print("\n")                                      
                                                 
print("Solved with DFS:")                        
results = DFS(1,1,GetMap())                      
for result in results:                           
    print("path is ",len(result)," spots long\n")
    DrawMap(GetMap(),result)                     
    print("\n")                                  

- yakir0