数字路线迷宫

数字路线迷宫

按照下面的规则，找到从开始方格（红色）到目标方格（绿色）的路径。

• 同一个方格不能经过两次。
• 行走方向只能为横竖方向，斜对角方向不能行走。
• 上方和右方的数字表示那一行或者列中，所经过的方格的个数。

下图是一个例子，左图为迷宫，右图为解。从解可以看出，每一行所经过的方格数等于右侧对应的数字，而每一列所经过的方格数等于上方对应的数字。

下面是一个10×10的迷宫，这个题目有些难度，手工解决花了不少时间，让我们用Python写一个程序解解看。

解题程序

解这种题目最简单的方法就是回溯法，回溯法最简单的实现就是用递归。这里先给出完整的程序，然后再简单介绍一下编程思路。

class Maze(object):
    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参数为最后一个添加的方格坐标，也就是需要检查的对象。我们先看看这个方格所在的行和列的对应的方格数是否满足条件，这个条件很容易理解：

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

solve()方法完成递归回溯求解，它找到从pos到target的路径：

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) ❸

❶首先调用add(pos)走上坐标为pos方格。❷然后判断当前的状态是否符合条件。如果符合，对于pos的所有邻近的未走过的方格递归调用solve()方法，直到找到目标为止。在solve()返回之前，❸需要通过remove()还原到刚进入此方法时的状态，这样才能够正常回溯到上层的调用。

程序的输出为：

4 1 9 4 6 5 3 3 4 8
* . . * * * . . . . 4
* . * * . * . . * * 6
* . * . . * * * * * 7
* * * . . . . . . * 4
. . * * * . . . . * 4
. . * . * . . . . * 3
. . * . * . . . . * 3
. . * . * * * * * * 7
. . * . . . . . . . 1
. . * * * * * * * * 8