按照下面的规则，找到从开始方格（红色）到目标方格（绿色）的路径。
- 同一个方格不能经过两次。
- 行走方向只能为横竖方向，斜对角方向不能行走。
- 上方和右方的数字表示那一行或者列中，所经过的方格的个数。
下图是一个例子，左图为迷宫，右图为解。从解可以看出，每一行所经过的方格数等于右侧对应的数字，而每一列所经过的方格数等于上方对应的数字。
下面是一个10×10的迷宫，这个题目有些难度，手工解决花了不少时间，让我们用Python写一个程序解解看。
解这种题目最简单的方法就是回溯法，回溯法最简单的实现就是用递归。这里先给出完整的程序，然后再简单介绍一下编程思路。
def __init__(self, tx, ty, n):
self.tx = tx
self.ty = ty
self.maze = set() #记录方格
self.sx = [0]*n #记录某列所走过的方格数
self.sy = [0]*n #记录某行所走过的方格数
self.n = n
def add(self, pos):
self.maze.add(pos)
self.sx[pos[0]] += 1
self.sy[pos[1]] += 1
def remove(self, pos):
self.maze.remove(pos)
self.sx[pos[0]] -= 1
self.sy[pos[1]] -= 1
def check(self, pos):
x,y = pos
sx, sy = self.sx, self.sy
tx, ty = self.tx, self.ty
if sx[x] > tx[x] or sy[y] > ty[y]: return False
if sx[x] == tx[x]:
for i in xrange(x):
if sx[i]!=tx[i]: return False
if sy[y] == ty[y]:
for i in xrange(y):
if sy[i]!=ty[i]: return False
return True
def print_out(self):
print " ".join((str(v) for v in self.tx))
for i in xrange(self.n):
for j in xrange(self.n):
if (j,i) in self.maze: print "*",
else: print ".",
print str(self.ty[i])
def near_pos(self, pos):
x,y=pos
if x-1>=0: yield x-1,y
if x+1<=self.n-1:yield x+1,y
if y-1>=0: yield x,y-1
if y+1<=self.n-1:yield x,y+1
def solve(self, pos, target):
self.add(pos)
if self.check(pos):
if pos == target:
self.print_out()
return
for npos in self.near_pos(pos):
if npos not in self.maze:
self.solve(npos, target)
self.remove(pos)
X = [4,1,9,4,6,5,3,3,4,8]
Y = [4,6,7,4,4,3,3,7,1,8]
maze = Maze(X, Y, 10)
maze.solve((0,0), (9,9))
Maze类的maze属性是一个集合，用来记录当前走过的所有的方格的坐标。sx和sy属性分别用来记录每列以及每行走过的方格数。tx和ty属性保存每列和每行走过的目标方格数。add()和remove()方法用来添加和删除方块，在添加或删除方块的时候，需要同时更新sx和sy属性中相应坐标的值。
check()方法用来检测当前的状态是否符合规则。pos参数为最后一个添加的方格坐标，也就是需要检查的对象。我们先看看这个方格所在的行和列的对应的方格数是否满足条件，这个条件很容易理解：
由于入口在左上，而出口在右下，因此一旦某一行或者列的方格数等于了规则所给出的方格数，那么它左边的列或者上面的行就必须也符合规定的数目。因为如果要走回的话，那么就必须再经过一次已经当前方格所在的行和列，这样就不能满足条件了。这也就是说，当走到某个方格时，那行的方格数已经等于了指定的值时，我们就不能再走那行上方的方格了。列方向上也是同样的道理。这个条件很关键，它能够裁剪掉大量的后续选路径，如果去除掉这个条件检测，那么等几个小时可能都出不来结果。
for i in xrange(x):
if sx[i]!=tx[i]: return False
if sy[y] == ty[y]:
for i in xrange(y):
if sy[i]!=ty[i]: return False
solve()方法完成递归回溯求解，它找到从pos到target的路径：
self.add(pos) ❶
if self.check(pos): ❷
if pos == target:
self.print_out()
return
for npos in self.near_pos(pos):
if npos not in self.maze:
self.solve(npos, target)
self.remove(pos) ❸
❶首先调用add(pos)走上坐标为pos方格。❷然后判断当前的状态是否符合条件。如果符合，对于pos的所有邻近的未走过的方格递归调用solve()方法，直到找到目标为止。在solve()返回之前，❸需要通过remove()还原到刚进入此方法时的状态，这样才能够正常回溯到上层的调用。
程序的输出为：
* . . * * * . . . . 4
* . * * . * . . * * 6
* . * . . * * * * * 7
* * * . . . . . . * 4
. . * * * . . . . * 4
. . * . * . . . . * 3
. . * . * . . . . * 3
. . * . * * * * * * 7
. . * . . . . . . . 1
. . * * * * * * * * 8