document.write('最容易想到的方法就是尝试所有可能的路径，找出可达的一条路。显然这种方法效率非常低下，这
里重点介绍一种效率更高的回溯法。主要思路为：当碰到死胡同的时候，回溯到前一步，然后从前
一步出发继续寻找可达的路径。算法的主要框架为：
申请一个结果矩阵来标记移动的路径
if 到达了目的地
打印解决方案矩阵
else
(1)在结果矩阵中标记当前为1(1表示移动的路径)。
(2)向右前进一步，然后递归地检查，走完这一步后，判断是否存在到终点的可达的
路线。
(3)如果步骤(2)中的移动方法导致没有通往终点的路径，那么选择向下移动一步，
然后检查使用这种移动方法后，是否存在到终点的可达的路线。
(4)如果上面的移动方法都会导致没有可达的路径，那么标记当前单元格在结果矩阵
中为0，返回false，并回溯到前一步中。
根据以上框架很容易进行代码实现。示例代码如下：
class Maze:
def __init__(self):
self.N=4
#打印从起点到终点的路线
def printSolution(self,sol):
i=0
while i＜self.N:
j=0
while j＜self.N:
print sol[i][j],
j+=1
print \'\\n\'
i+=1
#判断x和y是否是一个合理的单元
def isSafe(self,maze,x,y):
return x＞=0 and x＜self.N and y＞=0 and\\
y＜self.N and maze[x][y]==1
"""
使用回溯的方法找到一条从左上角到右下角的路径
maze表示迷宫,x、y表示起点,sol存储结果
"""
def getPath(self,maze,x,y,sol):
#到达目的地
if x==self.N-1 and y==self.N-1:
sol[x][y]=1
return True
#判断maze[x][y]是否是一个可走的单元
if self.isSafe(maze,x,y):
#标记当前单元为1
sol[x][y]=1
#向右走一步
if self.getPath(maze,x+1,y,sol):
return True
#向下走一步
if self.getPath(maze,x,y+1,sol):
return True
#标记当前单元为0用来表示这条路不可行,然后回溯
sol[x][y]=0
return False
return False
if __name__=="__main__":
rat=Maze()
maze=[[1,0,0,0],
[1,1,0,1],
[0,1,0,0],
[1,1,1,1]]
sol=[[0,0,0,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
if not rat.getPath(maze,0,0,sol):
print "不存在可达的路径"
else:
rat.printSolution(sol)
程序的运行结果为：
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1
');