最近很火的益智玩具--迷宫大追捕的谜题穷举(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)