Contents

## 矩阵模型

1. 游戏的面板是4*4，总计16个单元
2. 6枚板块恰好可以布满整个面板

• 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.

• \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

## 枚举各骨牌的位置

#!/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

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():
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()


## 实测

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".

Please contribute if you find this software useful.

Read https://www.octave.org/bugs.html to learn how to submit bug reports.
For information about changes from previous versions, type 'news'.

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



• 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, 占据最后的位置

## 参考资料

This site uses Akismet to reduce spam. Learn how your comment data is processed.