引言
记忆碎片（Memento）是游戏《去月球》（To the Moon）中的一个解谜小游戏。基本规则已在游戏中介绍。即通过点击按钮翻转某一行、列或者对角线，直至所有碎片都转成同一面。
解谜画面
这个解谜与成就/剧情分支无关，而且谜题设置比较简单，比较适合自己玩。谜题也非随机生成，答案都可以在网上找到。
兴趣使然地写了一个编程通用解法。在此介绍一下。
分析
注意到同一位置进行任意偶数次变换都等价于不变，而奇数次变换等价于进行 1 次。为使总变换次数最少，只需决定每个位置是否进行变换即可。
其次，多个不同变换之间满足交换律和结合律，即任意改变变换之间的顺序不会影响最终的结果。
因此，每个解决方案，对应到将变换集合映射到 {进行，不进行} 集合的一个函数映射。若有 N 种可能的变换，则共有 2^N 种可能的解决方案。
可以使用二进制编码，宽度为 行数 + 列数 + 1 。每一位都对应着翻转行、列或对角线。该位为 1 代表进行变换，该位为 0 代表不进行变换。
接下来我们只需要枚举所有可能的解决方案，并将其中正确的挑选出来即可。
游戏中给出了最佳步数，因此可以作为加速搜索的方式，一旦解决方案中，变换的次数超过最佳步数，则跳过。这样，整个搜索空间大小从 2^N 减小到了 C(N, B) ，其中 B 是最佳变换次数， C 是组合数。
实现
首先处理输入，我们将输入的图形转换为一个布尔矩阵。
rowNum = int(input('Row number: '))
colNum = int(input('Col number: '))
best = int(input('Best move: '))
print("Input table, 1 for solved, 0 for unsolved")
table = [list(map(lambda x: True if int(x) == 1 else False,
input().split())) for i in range(rowNum)]
接下来定义一些工具函数：
def check():
return all([all(row) for row in table])
def flip(i, j):
table[i][j] = False if table[i][j] else True
我们需要从解决方案中提取对应的行、列、对角线进行翻转：
def apply_solution(solution):
for r in range(rowNum):
if solution[r]:
for c in range(colNum):
flip(r, c)
for c in range(colNum):
if solution[rowNum+c]:
for r in range(rowNum):
flip(r, c)
if solution[-1]:
# diagnol, from left-bottom
for i in range(min(rowNum, colNum)):
flip(rowNum-1-i, i)
注意，对角线是从左下角开始的。
类似的，我们定义打印解决方案的函数：
def print_solution(solution):
for r in range(rowNum):
if solution[r]:
print('r%s' % r)
for c in range(colNum):
if solution[rowNum+c]:
print('c%s' % c)
if solution[-1]:
print('d')
注意，编号从 0 开始，方向是从上到下、从左到右。 d 代表对角线。
主要过程是枚举整个解决方案空间：
for solution in itertools.product([False, True], repeat=rowNum+colNum+1):
if solution.count(True) > best:
continue
apply_solution(solution)
if check():
print_solution(solution)
break
else:
apply_solution(solution)
else:
print('No answer for best move %s' % best)
首先，使用 itertools.product 产生所有的编码。
对于每一个编码，如果变换数大于最佳，则跳过当前。
如果找到了一个解，则打印并跳出，否则重新调用 apply_solution 函数将表格恢复原状态。
测试
Row number: 3
Col number: 3
Best move: 2
Input table, 1 for solved, 0 for unsolved
1 0 0
1 0 0
1 0 0
c1
c2
Row number: 3
Col number: 3
Best move: 3
Input table, 1 for solved, 0 for unsolved
1 0 0
0 0 0
0 0 1
r1
c1
d
附注
itertools.product
该函数产生一系列 iterable 的笛卡尔积（Cartesian product），如果指明了 repeat 关键字参数，则会将前面所有的 iterable 再和自己进行笛卡尔积。
全局依赖
由于对角线的存在，每一次枚举行/列无法完全确定其他某个变换是否进行，因此没有进一步减小空间的机会。
但事实上，除了第一个谜题，游戏中每个谜题都包含对角线。因此，可以默认只在奇数编码中搜索。将对角线放在最后一位也有利于快速找到解决方案。
最佳步数
代码稍作修改可以找到所有可能的方案，并对其排序，找到变换数最小的方案。也就是最佳步数无需输入。
完整代码
import itertools
def solve_memento():
rowNum = int(input('Row number: '))
colNum = int(input('Col number: '))
best = int(input('Best move: '))
print("Input table, 1 for solved, 0 for unsolved")
table = [list(map(lambda x: True if int(x) == 1 else False,
input().split())) for i in range(rowNum)]
def check():
return all([all(row) for row in table])
def flip(i, j):
table[i][j] = False if table[i][j] else True
def apply_solution(solution):
for r in range(rowNum):
if solution[r]:
for c in range(colNum):
flip(r, c)
for c in range(colNum):
if solution[rowNum+c]:
for r in range(rowNum):
flip(r, c)
if solution[-1]:
# diagnol, from left-bottom
for i in range(min(rowNum, colNum)):
flip(rowNum-1-i, i)
def print_solution(solution):
for r in range(rowNum):
if solution[r]:
print('r%s' % r)
for c in range(colNum):
if solution[rowNum+c]:
print('c%s' % c)
if solution[-1]:
print('d')
for solution in itertools.product([False, True], repeat=rowNum+colNum+1):
if solution.count(True) > best:
continue
apply_solution(solution)
if check():
print_solution(solution)
break
else:
apply_solution(solution)
else:
print('No answer for best move %s' % best)
solve_memento()
网友评论