缘由
之前一阵子，慕慕妈妈给慕慕买了一个益智小玩具——👻幽灵捕手。
这个游戏的介绍视频可以参考: 幽灵捕手玩法视频。整整一年前我恰好看了Knuth的Dancling Links（参考之前的blog: https://kainwen.com/2022/01/03/dancing-links/ ) ，最近看着吕小慕玩儿这个游戏，顿时觉得，这就是一个可以用Dancling Links解决的Exact Cover Problem。那就让我们来试试看吧。
矩阵模型
我们看看上面的吕小慕弄出来的49关建模的样子如下:
注意到：
- 游戏的面板是4*4，总计16个单元
- 6枚板块恰好可以布满整个面板
仿照Knuth建模Scott’s pentomino problem [1]的办法，首先构建矩阵的列：
- 6枚板块(A,B,C,D,E,F)对应第1~6列
- 面板有16个单元，每个单元是一列，它们构成矩阵的第7～22列 (可以按自然坐标系编码，比如黄色的面板的三个单元是(1,1),(2,1),(1,2)，也即第1,2,5块单元)
- 最后6列代表6个幽灵，即第23～28列，幽灵的编码按所在的单元编号排序后的序号，比如绿色的骨牌的幽灵编号就是5.
每行代表一个板块的放置，比如上面49关的例子里，绿色的板块A对应的行向量就是:
- \forall i \in [1, 28], D[i] \in \{0, 1\}
- D[4]=1, 表明这是第一个block D
- D[7]=1, D[8]=1, D[11]=1, block A占据面板的第1，2，5个单元
- D[23]=1, D[24]=1, block照亮了第1, 2个幽灵
- 除此之外的所有的位置都是0
每个关卡纸的不同之处，也就是6个幽灵的位置。这可以看作是程序的输入。程序不变的地方是枚举每个骨牌的位置，然后根据骨牌的特点和关卡的安排，可以补充最后6列矩阵的内容，完成了矩阵的填充，剩下的交给Dancling Link [2]就可以了。
枚举各骨牌的位置
这部分思路也很简单，从一个骨牌的某个模式开始，旋转90度，180度，270度，360度可以得到4个模式，然后对于每个模式进行遍历。具体一个模式，选择一个点用符号表示，把符号坐标匹配盘面各个坐标，求解方程后，代入其他坐标，再检查一下边界情况即可。
旋转角度是线性变换，就是一个矩阵乘法而已。
符号方法可以用Python的SymPy包，非常方便好用。
快糙猛的把Python当Shell写可以得到下面的程序用来构建游戏的矩阵:
#!/usr/bin/env python3
#-*- coding: utf-8 -*-
from collections import namedtuple
import sympy as sym
from sympy.solvers import solve
import sys
Block = namedtuple('Block', ['name', 'col', 'cells', 'light_cell_idx'])
x = sym.Symbol('x')
y = sym.Symbol('y')
BlockA = Block('A', 1,
[(x, y), (x+1, y), (x+1, y+1)],
[0])
BlockB = Block('B', 2,
[(x, y), (x+1, y)],
[1])
BlockC = Block('C', 3,
[(x, y), (x+1, y), (x+1, y-1)],
[1])
BlockD = Block('D', 4,
[(x, y), (x+1, y), (x, y+1)],
[1,2])
BlockE = Block('E', 5,
[(x, y), (x+1, y), (x, y+1)],
[1])
BlockF = Block('F', 6,
[(x, y), (x+1, y)],
[])
AllBlocks = [BlockA, BlockB, BlockC, BlockD, BlockE, BlockF]
def rotate90(p, times):
(a, b) = p
P = sym.Matrix([[0, -1], [1, 0]])
m = sym.Matrix([[a], [b]])
r = (P**times) * m
return (r[0], r[1])
"""
Board
(4,1) (4,2), (4,3) (4,4)
(3,1) (3,2), (3,3) (3,4)
(2,1) (2,2), (2,3) (2,4)
(1,1) (1,2), (1,3) (1,4)
13 14 15 16
9 10 11 12
5 6 7 8
1 2 3 4
"""
def solve_eq(exp, target):
assert(len(exp.free_symbols) == 1)
val = list(exp.free_symbols)[0]
return (val, solve(exp-target, val)[0])
def get_cell_id(a, b):
return (a-1)*4 + b
Row = namedtuple('Row', ['block_col', 'cell_ids', 'light_cell_ids'])
def try_put_block(Blk):
r = []
for t in range(0, 4):
new_cells = [rotate90(p, t) for p in Blk.cells]
for i in range(1, 5):
for j in range(1, 5):
base = new_cells[0]
bind1 = solve_eq(base[0], i)
bind2 = solve_eq(base[1], j)
cells_val = [(e1.subs(*bind1).subs(*bind2),
e2.subs(*bind1).subs(*bind2))
for e1, e2 in new_cells]
if sum(1 for p in cells_val if not (1<= p[0] <= 4 and 1 <= p[1] <= 4)) > 0:
continue
new_light_cells = [new_cells[idx] for idx in Blk.light_cell_idx]
new_cell_ids = [get_cell_id(*p) for p in cells_val]
row = Row(Blk.col, new_cell_ids, [new_cell_ids[idx] for idx in Blk.light_cell_idx])
r.append(row)
return r
def load_game():
line = sys.stdin.readline()
ghost_pos = eval(line)
ghost_cells = [get_cell_id(*p) for p in ghost_pos]
ghost_cells.sort()
return ghost_cells
def print_row(r, ghosts_cell_ids_set, ghosts_cell_id_to_id_map):
block_cols = [0] * 6
block_cols[r.block_col-1] = 1
cell_cols = [0] * 16
for id in r.cell_ids:
cell_cols[id-1] = 1
ghost_cols = [0] * 6
lighted = False
for id in r.light_cell_ids:
if id in ghosts_cell_ids_set:
ghost_cols[ghosts_cell_id_to_id_map[id]-1] = 1
lighted = True
if (not lighted) and (not r.block_col == 6):
return None
row_vector = block_cols + cell_cols + ghost_cols
return row_vector
def print_matrix():
ghosts = load_game()
rows = []
ghosts_cell_ids_set = set(ghosts)
ghosts_cell_id_to_id_map = dict([(cell_id, i+1) for i, cell_id in enumerate(ghosts)])
for blk in AllBlocks:
rows.extend(try_put_block(blk))
print(len(rows), 28)
for r in rows:
rr = print_row(r, ghosts_cell_ids_set, ghosts_cell_id_to_id_map)
if rr is not None:
print(" ".join(list(map(str, rr))))
print_matrix()
实测
之前的Dancling Link程序和今天的程序都在这里：https://github.com/kainwen/misc/tree/main/dancing_links.
需要注意的是，algrithmX跑出来的结果行号从0开始的。
gpadmin@zlyu:~/workspace/misc/dancing_links$ python3 ghost_hunter.py > gm
[(1,2), (2,1), (3,1), (3,2), (3,4), (4,4)]
gpadmin@zlyu:~/workspace/misc/dancing_links$ gcc algorithmX.c
gpadmin@zlyu:~/workspace/misc/dancing_links$ ./a.out < gm
93 32 21 44 68 2
gpadmin@zlyu:~/workspace/misc/dancing_links$ vim gm
gpadmin@zlyu:~/workspace/misc/dancing_links$ # removed 1st line of gm
gpadmin@zlyu:~/workspace/misc/dancing_links$ octave
octave: X11 DISPLAY environment variable not set
octave: disabling GUI features
GNU Octave, version 6.4.0
Copyright (C) 2021 The Octave Project Developers.
This is free software; see the source code for copying conditions.
There is ABSOLUTELY NO WARRANTY; not even for MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. For details, type 'warranty'.
Octave was configured for "x86_64-pc-linux-gnu".
Additional information about Octave is available at https://www.octave.org.
Please contribute if you find this software useful.
For more information, visit https://www.octave.org/get-involved.html
Read https://www.octave.org/bugs.html to learn how to submit bug reports.
For information about changes from previous versions, type 'news'.
octave:1> load gm;
octave:2> gm(94, :) + gm(33, :) + gm(22, :) + gm(45, :) + gm(69, :) + gm(3, :)
ans =
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
上面最后用Octave快速验证了一下答案是正确的。选出来的行编码如下:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0: block A,覆盖9,13,14, 照亮第3个鬼0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1: block B, 覆盖15,16, 照亮第6个鬼0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0: block C, 覆盖8,11,12, 照亮第5个鬼0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0: block D, 覆盖1,2,5, 照亮第1，2个鬼0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0: block E, 覆盖6,7,10, 照亮第4个鬼0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0: block F, 覆盖3,4, 占据最后的位置
参考资料
- [1] Knuth, D. E. (2000). Dancing links. arXiv preprint cs/0011047.
- [2] Stanford Lecture: Don Knuth—”Dancing Links” (2018)