在Python中使用递归解决迷宫
我有一个作业，要求我用递归来解决一个迷宫。我会把作业的要求发上来，这样你们就能明白我在说什么。教授对递归的解释不多，他给了我们一些递归的例子，我也会发上来，但我希望有人能给我更深入的解释，告诉我如何用递归来解决迷宫。我并不是让大家给我写代码，只是希望一些解释能让我找到正确的方向。谢谢任何回答我的人。
这是我拥有的例子：
def foo():
print("Before")
bar()
print("After")
def bar():
print("During")
def factorial(n):
"""n!"""
product = 1
for i in range(n,0,-1):
product *= i
return product
def recFac(n):
"""n! = n * (n-1)!"""
if(n == 1):
return 1
return n * recFac(n-1)
def hello():
"""Stack overflow!"""
hello()
def fib(n):
"""f(n) = f(n-1) + f(n-2)
f(0) = 0
f(1) = 1"""
if n == 0 or n == 1: #base case
return n
return fib(n-1) + fib(n-2) #recursive case
def mult(a,b):
"""a*b = a + a + a + a ..."""
#base case
if (b == 1):
return a
#recursive case
prod = mult(a,b-1)
prod *= a
return prod
def exp(a,b):
"""a ** b = a* a * a * a * a *.... 'b times'"""
#base case
if (b==0):
return 1
if (b == 1):
return a
#recursive case
return exp(a,b-1)*a
def pallindrome(word):
"""Returns True if word is a pallindrome, False otherwise"""
#base case
if word == "" or len(word)==1:
return True
#recursive case
if word[0] == word[len(word)-1]:
word = word[1:len(word)-1]
return pallindrome(word)
else:
return False
以下是作业要求：
你需要创建一个迷宫爬行器，能够用递归的力量解决你给它的任何迷宫！
问题1 - 加载迷宫
在你解决迷宫之前，你需要先加载它。对于这个作业，你将使用一种简单的文本格式来表示迷宫。你可以使用这个示例迷宫，或者自己创建一个。
你在这个问题中的目标是加载任何给定的迷宫文件，并将其读入一个二维列表中。比如：loadMaze("somemaze.maze") 应该加载 somemaze.maze 文件，并创建一个如下所示的列表...
[['#','#','#','#','#','#','#','#','#'],
['#','S','#',' ',' ',' ','#','E','#'],
['#',' ','#',' ','#',' ',' ',' ','#'],
['#',' ',' ',' ','#',' ','#',' ','#'],
['#', #','#','#','#','#','#','#','#']]
注意，列表中已经去掉了所有的 '\r' 和 '\n' 字符。为了让下一个问题更简单，你可以把这个列表设为全局变量。
接下来，写一个函数，以更好看的格式打印出迷宫：
例如，
####################################
#S# ## ######## # # # # #
# # # # # # #
# # ##### ## ###### # ####### # #
### # ## ## # # # #### #
# # # ####### # ### #E#
####################################
在继续之前，先用不同的迷宫测试你的代码。
问题2 - 准备解决迷宫
在你解决迷宫之前，你需要找到起点！在你的代码中添加一个叫做 findStart() 的函数，它会逐个字符地搜索迷宫，并返回 'S' 字符的 x 和 y 坐标。你可以假设迷宫中最多只有一个这样的字符。如果在迷宫中没有找到 'S'，就返回 -1 作为 x 和 y 坐标。
在继续之前，先用 'S' 在多个位置（包括没有位置）测试你的代码。
问题3 - 解决迷宫！
最后，你准备好用递归来解决迷宫了！你的解决方案只需要一个方法：solve(y,x)
solve 方法的一个实例应该解决迷宫中的一个位置。参数 y 和 x 是当前要解决的坐标。你的 solve 方法应该完成几个任务。它应该检查当前是否在解决 'E' 的位置。如果是这样，你的 solve 方法就成功完成了。否则，它应该尝试递归地解决右边的空间。注意，你的方法只应该尝试解决空白区域，而不是墙壁（'#'）。如果这个递归没有找到终点，那么就尝试向下、向左和向上。如果所有这些都失败了，你的代码应该回溯一步，尝试另一个方向。
最后，在解决迷宫的过程中，你的代码应该留下进度的指示。如果它正在向右搜索，当前的位置应该用 '>' 替代空白。如果向下搜索则用 'v'，向左用 '<'，向上用 '^'。如果你的代码需要回溯，就去掉方向箭头，把位置恢复为 ' '。
一旦你的迷宫解决了，再次打印出迷宫。你应该能看到一步一步走迷宫的指南。比如，
main("somemaze.maze")
#########
#S# #E#
# # # #
# # # #
#########
S 在 (1,1)
#########
#S#>>v#E#
#v#^#>>^#
#>>^# # #
#########
在继续之前，测试你的代码，使用不同的起点和终点，最好在各种迷宫上测试。
这是我到目前为止的代码：但代码实际上没有在迷宫中打印出轨迹，我不太确定为什么。
def loadMaze():
readIt = open('Maze.txt', 'r')
readLines = readIt.readlines()
global mazeList
mazeList = [list(i.strip()) for i in readLines]
def showMaze():
for i in mazeList:
mazeprint = ''
for j in i:
mazeprint = mazeprint + j
print(mazeprint)
print('\n')
def solve(x,y, mazeList):
mazeList[x][y] = "o"
#Base case
if y > len(mazeList) or x > len(mazeList[y]):
return False
if mazeList[y][x] == "E":
return True
if mazeList[y][x] != " ":
return False
#marking
if solve(x+1,y) == True: #right
mazeList[x][y]= '>'
elif solve(x,y+1) == True: #down
mazeList[x][y]= 'v'
elif solve(x-1,y) == True: #left
mazeList[x][y]= '<'
elif solve(x,y-1) == True: #up
mazeList[x][y]= '^'
else:
mazeList[x][y]= ' '
return (mazeList[x][y]!= ' ')
5 个回答
用Python解决迷宫问题展示了我的答案。不过，如果你想自己写代码，步骤如下。
1. Start at the entrance.
2. Call the function solve(x,y) with the entrance co-ordinates
3. in solve, return false if the input point has already been handled or is a wall.
4. Mark the current point as handled (tag = 'o')
5. go to the right and call solve on that point. If it returns true, set tag to '>'
6 elif do the same for left and '<'
7 elif do the same for up and '^'
8 elif do the same for down and 'v'
9 else this is a false path, set tag = ' '
10 set the current maze point to tag
11 return (tag != ' ')
另外，你可以跳过第9步，直接进行第11步。
return(tag != 'o')
然后在迷宫中搜索，把每个'o'替换成' '（空格）。
你可以用两种方式展示迷宫，这样可以看到你尝试解决的过程和最终的结果。这种方法曾被用作Solaris的屏幕保护程序，潜在的路径用一种颜色显示，而实际的路径用另一种颜色，这样你就能看到它是如何尝试并最终成功的。
递归其实是个简单的概念：要解决一个问题，你先把这个问题缩小一步，然后解决缩小后的问题。这个过程会一直进行，直到你遇到一个“基础问题”，这个问题你已经知道怎么完全解决了。然后你把基础问题的解决方案返回，再在每一步的返回中加上之前记住的数字，直到你得到完整的解决方案。
举个例子，计算n!（n的阶乘），我们记住n，然后计算(n-1)!。基础情况是1!，我们返回1；然后在每次返回时，我们乘以之前记住的数字（2 * 1!等于2，3 * 2!等于6，4 * 3!等于24，5 * 4!等于120），直到我们乘以n，得到完整的答案。这其实是一种比较简单的递归；每一步只有一个可能的选择。这种叫做“尾递归”，很容易转换成迭代的方式（从1开始，依次乘到n）。
另一种更有趣的递归是把问题分成两半，分别解决每一半，然后把两个半部分的结果结合起来；比如快速排序就是通过选择一个元素，把列表分成“比这个元素小的部分”和“比这个元素大的部分”，对每一半进行快速排序，然后返回快速排序后的（小的部分）+ 这个元素 + 快速排序后的（大的部分）。基础情况是“当我的列表只有一个元素时，它已经排序好了”。
在迷宫问题中，我们会把问题分成四种情况——从当前位置向右、左、上、下走的所有可能解决方案——特别的是，只有一个递归搜索会找到解决方案。基础情况是“我站在E点上”，而失败的情况是“我在墙里”或者“我在一个已经访问过的地方”。
补充：为了增加趣味，这里有一个面向对象的解决方案（兼容Python 2.x和3.x）：
from collections import namedtuple
Dir = namedtuple("Dir", ["char", "dy", "dx"])
class Maze:
START = "S"
END = "E"
WALL = "#"
PATH = " "
OPEN = {PATH, END} # map locations you can move to (not WALL or already explored)
RIGHT = Dir(">", 0, 1)
DOWN = Dir("v", 1, 0)
LEFT = Dir("<", 0, -1)
UP = Dir("^", -1, 0)
DIRS = [RIGHT, DOWN, LEFT, UP]
@classmethod
def load_maze(cls, fname):
with open(fname) as inf:
lines = (line.rstrip("\r\n") for line in inf)
maze = [list(line) for line in lines]
return cls(maze)
def __init__(self, maze):
self.maze = maze
def __str__(self):
return "\n".join(''.join(line) for line in self.maze)
def find_start(self):
for y,line in enumerate(self.maze):
try:
x = line.index("S")
return y, x
except ValueError:
pass
# not found!
raise ValueError("Start location not found")
def solve(self, y, x):
if self.maze[y][x] == Maze.END:
# base case - endpoint has been found
return True
else:
# search recursively in each direction from here
for dir in Maze.DIRS:
ny, nx = y + dir.dy, x + dir.dx
if self.maze[ny][nx] in Maze.OPEN: # can I go this way?
if self.maze[y][x] != Maze.START: # don't overwrite Maze.START
self.maze[y][x] = dir.char # mark direction chosen
if self.solve(ny, nx): # recurse...
return True # solution found!
# no solution found from this location
if self.maze[y][x] != Maze.START: # don't overwrite Maze.START
self.maze[y][x] = Maze.PATH # clear failed search from map
return False
def main():
maze = Maze.load_maze("somemaze.txt")
print("Maze loaded:")
print(maze)
try:
sy, sx = maze.find_start()
print("solving...")
if maze.solve(sy, sx):
print(maze)
else:
print(" no solution found")
except ValueError:
print("No start point found.")
if __name__=="__main__":
main()
运行后会产生：
Maze loaded:
####################################
#S# ## ######## # # # # #
# # # # # # #
# # ##### ## ###### # ####### # #
### # ## ## # # # #### #
# # # ####### # ### #E#
####################################
solving...
####################################
#S# ## ######## # #>>>>>v# >>v# #
#v#>>v# >>>v #^# >>>>^#>>v#
#>>^#v#####^##v######^# ####### #v#
### #v##>>>^##>>>>>v#^# # ####v#
# #>>>^# #######>>^# ### #E#
####################################
注意，题目中给出的要求有一些不太符合Python风格的地方：
- 它要求使用
camelCase的函数名，而不是underscore_separated - 它建议使用全局变量，而不是显式地传递数据
- 它要求
find_start在失败时返回标志值，而不是抛出异常
在编程中，有时候我们会遇到一些问题，特别是在使用某些工具或库的时候。这些问题可能会让我们感到困惑，不知道该怎么解决。比如，有人可能会在使用某个功能时，发现它并没有按照预期的方式工作。这种情况很常见，尤其是对于刚开始学习编程的人来说。
当我们遇到问题时，首先要做的是仔细阅读错误信息。错误信息通常会告诉我们哪里出了问题，虽然有时候看起来很复杂，但它们其实是在给我们提示。接下来，我们可以在网上搜索这个错误，看看其他人是怎么解决的。StackOverflow就是一个很好的地方，很多程序员会在这里分享他们的经验和解决方案。
另外，尝试自己动手解决问题也是一个很好的学习方式。可以通过修改代码，逐步调试，找到问题的根源。记住，编程是一个不断学习和尝试的过程，不要害怕犯错，错误往往是最好的老师。
总之，遇到问题时不要慌张，认真分析，积极寻找解决方案，这样你会越来越熟练。
import os
class Maze_Crawler:
def __init__(self):
self.maze = []
def load_maze(self, path):
rows = []
with open(path, 'r') as f:
rows = f.readlines()
for i in range(len(rows)):
self.maze.append([])
for j in range(len(rows[i])-1):
self.maze[i].append(rows[i][j])
return self.maze
def get_start_coor(self):
for i in range(len(self.maze)):
for j in range(len(self.maze[i])):
if self.maze[i][j] == 'S':
return i, j
return -1, -1
def solve_maze(self, coor):
x, y = coor
if self.maze[x][y] == '#' or self.maze[x][y] == 'X':
return False
if self.maze[x][y] == 'E':
return True
if self.maze[x][y] != 'S':
self.maze[x][y] = 'X'
if self.solve_maze((x+1, y)):
if self.maze[x][y] != 'S':
self.maze[x][y] = 'v'
elif self.solve_maze((x-1, y)):
if self.maze[x][y] != 'S':
self.maze[x][y] = '^'
elif self.solve_maze((x, y+1)):
if self.maze[x][y] != 'S':
self.maze[x][y] = '>'
elif self.solve_maze((x, y-1)):
if self.maze[x][y] != 'S':
self.maze[x][y] = '<'
else:
return False
return True
def show_solution(self):
for i in range(len(self.maze)):
r = ''
for j in range(len(self.maze[i])):
if self.maze[i][j] == 'X':
r += ' '
else:
r += self.maze[i][j]
print(r)
这是我在CodeEval的迷宫挑战中的解决方案：
import sys
sys.setrecursionlimit(5000)
class Maze(object):
FLOOR = ' '
WALLS = '*'
PATH = '+'
def __init__(self):
self.cols = 0
self.rows = 0
self.maze = []
def walk_forward(self, current_k, r, c):
self.maze[r][c] = current_k
next_k = current_k + 1
# up
if r > 1:
up = self.maze[r - 1][c]
if up != self.WALLS:
if up == self.FLOOR or int(up) > current_k:
self.walk_forward(next_k, r - 1, c)
# down
if r < self.rows - 1:
down = self.maze[r + 1][c]
if down != self.WALLS:
if down == self.FLOOR or int(down) > current_k:
self.walk_forward(next_k, r + 1, c)
# left
if c > 1:
left = self.maze[r][c - 1]
if left != self.WALLS:
if left == self.FLOOR or int(left) > current_k:
self.walk_forward(next_k, r, c - 1)
# right
if c < self.cols - 1:
right = self.maze[r][c + 1]
if right != self.WALLS:
if right == self.FLOOR or int(right) > current_k:
self.walk_forward(next_k, r, c + 1)
def walk_backward(self, r, c):
current_k = self.maze[r][c]
if not isinstance(current_k, int):
return False
self.maze[r][c] = self.PATH
up = self.maze[r - 1][c] if r > 0 else None
down = self.maze[r + 1][c] if r < self.rows - 1 else None
left = self.maze[r][c - 1] if c > 1 else None
right = self.maze[r][c + 1] if c < self.cols else None
passed = False
if up and isinstance(up, int) and up == current_k - 1:
self.walk_backward(r - 1, c)
passed = True
if down and isinstance(down, int) and down == current_k - 1:
self.walk_backward(r + 1, c)
passed = True
if left and isinstance(left, int) and left == current_k - 1:
self.walk_backward(r, c - 1)
passed = True
if right and isinstance(right, int) and right == current_k - 1:
self.walk_backward(r, c + 1)
def cleanup(self, cleanup_path=False):
for r in range(0, self.rows):
for c in range(0, self.cols):
if isinstance(self.maze[r][c], int):
self.maze[r][c] = self.FLOOR
if cleanup_path and self.maze[r][c] == self.PATH:
self.maze[r][c] = self.FLOOR
def solve(self, start='up', show_path=True):
# finding start and finish points
upper = lower = None
for c in range(0, self.cols):
if self.maze[0][c] == self.FLOOR:
upper = (0, c)
break
for c in range(0, self.cols):
if self.maze[self.rows - 1][c] == self.FLOOR:
lower = (self.rows - 1, c)
break
if start == 'up':
start = upper
finish = lower
else:
start = lower
finish = upper
self.cleanup(cleanup_path=True)
self.walk_forward(1, start[0], start[1])
length = self.maze[finish[0]][finish[1]]
if not isinstance(length, int):
length = 0
if show_path:
self.walk_backward(finish[0], finish[1])
self.cleanup(cleanup_path=False)
else:
self.cleanup(cleanup_path=True)
return length
def save_to_file(self, filename):
with open(filename, 'w') as f:
f.writelines(str(self))
def load_from_file(self, filename):
self.maze = []
with open(filename, 'r') as f:
lines = f.readlines()
for line in lines:
row = []
for c in line.strip():
row.append(c)
self.maze.append(row)
self.rows = len(self.maze)
self.cols = len(self.maze[0]) if self.rows > 0 else 0
def get_maze(self):
return copy.copy(self.maze)
def __str__(self):
as_string = u''
for row in self.maze:
as_string += u''.join([str(s)[-1] for s in row]) + "\n"
return as_string
maze = Maze()
maze.load_from_file(sys.argv[1])
maze.solve(show_path=True)
print str(maze)
（说起来，我在高中时其实用COBOL做过这个问题。）
你可以把解迷宫想象成一步一步走。
每走一步，规则都是一样的。因为每次都用相同的规则，所以你可以用完全相同的指令来处理每一步。走一步的时候，你只需要再次调用同样的程序，只需改变参数来表示新的步骤。这就是递归。你通过一步一步来拆解问题。
注意：有些递归的解决方案是把问题分成两半，分别解决每一半，这种方法在两部分之间没有依赖关系时有效。但在这里不适用，因为每一步（解决方案）都依赖于之前的步骤。
如果你走到了死胡同，你就得退回去，直到找到还有可以检查的方块的步骤。
小提示：你在走向出口的路上不标记正确的路径，因为你不知道现在走的这一步是否是通往出口的路径的一部分。你是在回程的时候标记路径，这时你知道每一步确实是路径的一部分。你之所以能做到这一点，是因为每一步都记得自己之前在哪个方块。
相反，你在每个尝试过的方块上做个标记，表示：我来过这里，不用再检查了。在打印解决方案之前，记得把这些标记清理掉。