python - 使用 Python 查找所有迷宫解决方案
问题描述
我试图找到（使用 Python）所有可能的迷宫解决方案。我有一个返回一个解决方案的 DFS 脚本。我正在尝试适应它，但我真的很难把头绕在整个递归的事情上。
这是我拥有的代码，可用于使用 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")
解决方案
妄想
像这样的问题一开始可能会让人感到不知所措，但我最喜欢的编程技术让复杂性化为乌有。使用一厢情愿的想法，我们编写我们希望的程序，然后我们实现我们的愿望 -
# 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模块开始。光标只是一对整数，它为我们提供了方便的up, down, left, 和right移动 -
# 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 也有很好的面向对象的特性，我们希望将这些便利扩展到我们模块的用户。我们通过包装普通函数轻松添加 OOP 接口 -
# 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免费获得的。接下来，我们使用和坐标将函数写入get或单元格。这里我们还写了一个简单的包装器，用来标记迷宫中的一个单元格已经被探索过-setyxstepset
# 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))
细胞
当我们编写 Maze 模块时，我们希望有一个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_*谓词来确定单元格是否是 a wall、 apath等。这突出了抽象的优势：我们可以更改数据在一个模块中的表示方式，而无需修改程序中的其他模块 -
# 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
只剩下一个愿望实现了！update我们在 Array Extensions 模块中编写通用函数， arr_ext -
# arr_ext.py
def update(t, pos, f):
try:
return [ *t[:pos], f(t[pos]), *t[pos + 1:]]
except IndexError:
return t
先进的
我们的simple程序以一种简化的方式解决了这个问题。如果我们想解决迷宫并知道每个解决方案的路径怎么办？让我们在下面编写一个advanced程序 -
# 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)
推荐阅读
- api - Azure 自动化 Runbook 中 Power BI API 的 PowerShell 代码
- c++ - 在c ++中插入数组中间的最后一个元素？
- javascript - Mobx 不会重新渲染 React 组件
- r - 如何解决这个绘图错误（xy.coords（x，y，xlabel，ylabel，log）中的错误：'x'和'y'长度不同）？
- ios - 有没有办法用 Decodable 忽略某些键，只提取它们的值？
- python - 如何在没有 Numpy 函数的 python 中显示 3 * 3 矩阵
- javascript - gql和styled.div后面的反引号是什么意思
- ios - 在真实设备上选择 PDF 时 iOS 文档选择器崩溃
- typescript - 无法设置threejs MeshBasicMaterial 实例的userData 属性
- docker - 当我在 kafka 中运行消费者脚本时，我收到错误 1 分区有领导代理没有匹配的侦听器