To the Moon 记忆碎片解谜

引言

记忆碎片（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 再和自己进行笛卡尔积。

全局依赖

由于对角线的存在，每一次枚举行/列无法完全确定其他某个变换是否进行，因此没有进一步减小空间的机会。

但事实上，除了第一个谜题，游戏中每个谜题都包含对角线。因此，可以默认只在奇数编码中搜索。将对角线放在最后一位也有利于快速找到解决方案。

最佳步数

代码稍作修改可以找到所有可能的方案，并对其排序，找到变换数最小的方案。也就是最佳步数无需输入。

完整代码

gist

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