技术

最近很火的益智玩具--迷宫大追捕的谜题穷举（02）

解决类似Scott骨牌谜题，有个比较快速的方法：

Dancing Links aka 跳舞链。

这个算法产生自1979年（没错，那会时间戳还很短呢）。主要目标就是搜索特定0,1矩阵中的一些行，这些行“叠加”起来，可以保证每一列有且只有一个1。

基于双向链表的一个特点：

1
2
3
4
5
6
7
删除一个节点：
x.left.right ← x.right;
x.right.left ← x.left;
恢复刚被删除的节点：
x.left.right ← x;
x.right.left ← x;

对一个由双向链表组成的矩阵，利用上面的特点可以快速删除、恢复一个节点乃至一整行or一整列。

这样，利用递归，就可以在搜索中轻易舍弃某些行、列，然后在搜索结束后，迅速的恢复现场。

具体的原理，参考这个

Wiki

中文翻译（PS：很好的翻译，虽然排版方式老旧点，单绝对用心）

OK，在了解DLX后，对我们的谜题–迷宫大追捕，如何搞定呢？

规则分析

玩具规则是在6x6的网格内，将上述模型中的11个块完整放入。并且，红色车和绿色车（如果用到了这个块）必须被警车和建筑物阻挡（阻挡规则是红绿车不能通过横、纵向移动达到网格边缘）。

  • 简单模式：不需要放入最后的绿色车块。
  • 高级模式：绿色车必须放入。

所以，基本规则如下：

  • 6x6的方格全部被覆盖。
  • 建筑的3块和红色车块为必选。
  • 6警车和绿色车块为备选。
  • 红绿车不能通过横纵移动达到棋盘边缘。

看起来不难哦~~ 建立模型吧。

基本模型

上面总结的基本模型，其实可以拆分为2部分：

  • 把这些块都老老实实完完整整的放入网格。
  • 放入网格后，红绿车不能逃走。

……

……

嗯，模型建立完毕。

如何把大象放入冰箱

模型一、把块放入冰箱 网格

显然是精确覆盖问题。直接建立几个放置规则列就好了。

  • 6x6个格子，必定被遮盖。=36个格子列
  • 3个建筑物+红色车，必定被放置。 =4个块列。
  • 6警车+1绿车块可能被放置 = 7个块列（这个就不是必须放的了，建立DLX的时候，设定为非必选）

（当然，规则三这里，如果不方便or节省计算时间，可以人工指定6个块即可）

大概代码：

1
dlx = DLX([("sharp_id{}".format(i) , DLX.PRIMARY) for i in range(4) ] +[("sharp_id{}".format(i) , DLX.SECONDARY) for i in range(7)]  + [("blocks{}".format(i) , DLX.SECONDARY) for i in range(36) ] )

然后，就是行的设立规则。

这块实在没啥好说的。就是根据每个块的形状不同，把旋转0，90，180，270度的所有覆盖格子的相对坐标设置好就行了。

嗯，大概代码是这个德行：（拿警车03–一个T型块做例子）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class T(Sharp):
    '''4 blocks T sharp'''
    def __init__(self, name='',blocks=[],image='assets/c_t.png'):
        super(T,self).__init__(name, blocks,image)
    def fill_into_grid(self, x, y, direction):
        #    *                      1
        #   ***                    234
        if direction == 0:
            used = [(x, y), (x-1, y+1), (x, y+1), (x+1, y+1)]
        #     *                     4
        #    **                    13
        #     *                     2
        elif direction == 1:
            used = [(x, y), (x+1, y+1), (x+1, y), (x+1, y-1)]
        #   ***                    432
        #    *                      1
        elif direction == 2:
            used = [(x, y), (x+1, y-1), (x, y-1), (x-1, y-1)]
        #   *                     2
        #   **                    31
        #   *                     4
        elif direction == 3:
            used = [(x, y), (x-1, y-1), (x-1, y), (x-1, y+1)]
        else :
            used = []
        if self._verity_fillable(used):
            self.loc_x = x
            self.loc_y = y
            self.direction = direction
            return used
        else:
            return []
    def render(self, bg):
        if self.image == '':
            return None
        im = Image.open(self.image)
        if self.direction == 0:
            pix_coordination = self._co_map(self.loc_x-1, self.loc_y)
        elif self.direction == 1:
            pix_coordination = self._co_map(self.loc_x, self.loc_y-1)
            im = im.transpose(Image.ROTATE_90)
        elif self.direction == 2:
            pix_coordination = self._co_map(self.loc_x-1, self.loc_y-1)
            im = im.transpose(Image.ROTATE_180)
        elif self.direction == 3:
            pix_coordination = self._co_map(self.loc_x - 1, self.loc_y - 1)
            im = im.transpose(Image.ROTATE_270)
        _, _, _, alpha = im.split()
        bg.paste(im, pix_coordination, mask=alpha)
        return bg

配置好后，插入N个行，跑起~~

于是，你发现吐出来无数的solution。不难理解，这些解大部分无用的，因为必须满足基本规则二：

放入网格后，红绿车不能逃走。

模型二、解迷宫

好吧，一个6x6的矩形迷宫的解法，用模型这个词是装逼。

这……这是高二作业吧？还得是素质教育后的……

一句话，递归+深度优先搜索。

我就不在这里废话了。

PS：系列文章列表：

最近很火的益智玩具–迷宫大追捕的谜题穷举（01）

最近很火的益智玩具–迷宫大追捕的谜题穷举（02）