使用Python查找所有迷宫解决方案 [英] Finding all maze solutions with Python
问题描述
我正在尝试(使用Python)找到迷宫的所有可能解决方案.我有一个DFS脚本，它返回一个解决方案.我正在尝试适应它，但是我真的很难把头放在整个递归过程上.
I am trying to find (using Python) all possible solutions to a maze. I have a DFS script that returns one solution. I am trying to adapt it but I'm really having a hard time wrapping my head around the whole recursion thing.
这是我拥有的代码，可用于使用DFS查找一种可能的解决方案:任何提示或帮助将不胜感激！(数组中的字母"可以忽略/认为是常规的路径")
Here's the code I have, which works for finding one possible solution using DFS: Any tips or help would be much appreciated! (The "lett" in the array can be ignored/considered regular "path")
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")
推荐答案
如意算盘
像这样的问题的发作可能让人感到不知所措，但是我最喜欢的编程技术使复杂性消失van尽.使用一厢情愿，我们按照自己的意愿编写程序，然后实现我们的愿望.-
The onset of a problem like this can feel overwhelming, but my favourite technique in programming makes complexity vanish into thin air. Using wishful thinking, we write our program how we wish it could be, then we make our wishes come true -
# 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 -
All we need to get going is a maze, m, and a cursor, 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")
(下面的输出重新格式化以节省空间)
(output below reformatted to save space)
######## ######## ######## ######## ######## ########
#--- # #--- # #----- # #----- # #------# #------#
###-#L # ###-#L # ### #--# ### #--# ### #L-# ### #L-#
# -## # #---## # # ##-# #---##-# # ##-# #---##-#
# #----# #-#L # # #L -# #-#----# # #L -# #-#----#
# ####-# #-#### # # ####-# #-#### # # ####-# #-#### #
# L e# #-----e# # L e# #-----e# # L e# #-----e#
######## ######## ######## ######## ######## ########
光标
要使上述程序正常运行，我们需要实现我们的所有愿望.我们将从 cursor 模块开始.光标只是一对整数，它使我们可以方便地进行 up ， down ， left 和 right 移动-
To make the program above work, we need to fulfill all of our wishes. We'll start with the cursor module. A cursor is simply a pair of integers that gives us a convenient up, down, left, and right movements -
# 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接口-
As you can see, we are working with ordinary functions. Python has nice object-oriented features too and we wish to extend such conveniences to the users of our module. We easily add an OOP interface by wrapping the plain functions -
# 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))
迷宫
现在，我们进入迷宫迷宫模块.我们将首先编写普通函数以将 from_file 转换为迷宫，并从迷宫 to_str -
Now we move onto our maze module. We'll start by writing ordinary functions to convert from_file to a maze, and from a maze 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 的简单包装器，用于标记迷宫中的某个单元已被探索.-
As a bonus, notice how we got from_str for free. Next we write functions to get or set a cell using y and x coordinates. Here we also write step, a simple wrapper around set, which is used to mark that a cell in the maze has been explored -
# 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 .就像我们在上一个模块中所做的一样，我们添加了面向对象的接口-
Don't be afraid to make as many wishes as you want. We'll implement update when we need it. And just like we did in the previous module, we add the object-oriented interface -
# 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 模块.如意算盘的技巧现在应该成为焦点:许下愿望，实现它.我们的细胞"模块代表迷宫中的一个细胞.我们从将 from_str 转换为单元格以及从单元格 to_str -
When we wrote the Maze module, we wished for a cell module. The technique of wishful thinking should be coming into focus now: make a wish, fulfill it. Our Cell module represents a cell in our maze. We start with a way to convert from_str to a cell, and from a cell 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 等.这突出了抽象的优势:我们可以更改数据在一个模块中的表示方式，而无需修改程序中的其他模块.-
Additionally we write is_* predicates to determine whether a cell is a wall, a path, etc. This highlights a strength of abstraction: we can change how our data is represented in one module without having to modify other modules in our program -
# 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
添加面向对象的界面.再次，这是我们普通函数的简单包装器-
Add the object-oriented interface. Again, it's a simple wrapper around our plain functions -
# 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 -
Only one wish left to fulfill! We write the generic update function in an Array Extensions module, 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 程序以简化的方式解决了该问题.如果我们想解决迷宫 并知道每种解决方案的路径怎么办?让我们在下面编写一个高级程序-
Our simple program solves the problem in a simplified way. What if we want to solve the maze and know the path for each solution? Let's write an advanced program below -
# 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
请注意，高级解决方案只是对简单模块的一小部分调整.让我们来看看第一个解决的迷宫是什么样的
Notice how the advanced solution is just a small adjustment of the simple module. Let's see what the first solved maze looks like -
# 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)
现在让我们看看已解决的迷宫和路径的全部
Now let's see all of the solved mazes and paths -
# 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 ，但是这次我们将其保留在同一文件中-
Don't forget to fulfill your wishes! We can see the emergence of a new module, solution, happening, but this time we will just leave it in the same file -
# 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)
这篇关于使用Python查找所有迷宫解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
