使用 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 寻找一种可能的解决方案:任何提示或帮助将不胜感激！(数组中的lett"可以被忽略/认为是常规的路径")
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("
Unsolved:
")
DrawMap(GetMap(),[])
print("
")
print("Solved with DFS:")
print("path is ",len(DFS(1,1,GetMap()))," spots long
")
DrawMap(GetMap(),DFS(1,1,GetMap()))
print("
")
推荐答案
一厢情愿
遇到这样的问题可能会让人不知所措，但我最喜欢的编程技术使复杂性化为乌有.使用一厢情愿，我们按照我们希望的方式编写程序，然后让我们的愿望成真-
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 -
Or we can find all solutions using dfs -
# simple.py (continued)
for x in dfs(c, m):
print(x, end="
")
(以下输出重新格式化以节省空间)
(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))
迷宫
现在我们进入我们的 maze 模块.我们将从编写普通函数开始，将 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("
") ]
def to_str(t):
return "
".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))
单元格
当我们编写迷宫模块时，我们希望有一个 cell 模块.一厢情愿的技巧现在应该成为焦点:许下愿望，实现它.我们的 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
只剩下一个愿望要实现了！我们在数组扩展模块中编写通用的 update 函数，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="
")
########
#--- #
###-#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) + "
" + "->".join(map(str, path))
class solution:
def __init__(self, t): self.t = t
def __str__(self): return to_str(self.t)
这篇关于使用 Python 查找所有迷宫解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
