灭灯游戏

在高中阶段, 矩阵和矩阵乘法的教学往往不被重视, 在多数高中生眼里, 认为矩阵就是一张简单的数表, 把矩阵的运算看作是数字运算的批处理. 那么本文将从灭灯游戏这一有趣的问题入手, 带你看看矩阵的魅力.

灭灯游戏背后的本质是线性代数, 本文将通过建立矩阵模型, 将破解灭灯游戏的难题转化为线性方程组的求解问题. 首先我们来介绍一下灭灯游戏及其发展历史.

灭灯游戏及其变体

灭灯游戏, 是20世纪90年代开始流行的一款电子游戏, 该游戏由一个的网格组成, 每格代表一盏灯, 每盏灯只有点亮和熄灭两种状态, 游戏的初始状态是, 25盏灯中有些是亮的, 其余则是暗的. 点击任意一个格子将使得它和相邻格子的灯变换状态. 游戏的目标是用尽可能少的点击数让所有灯都变暗. 以下视频是一个具体的示例.

随着灭灯游戏的盛行, 它还出现了很多变种游戏, 比如：

• 改变灯的状态：从2种到3种甚至多种(用不同颜色来表示不同状态).

• 修改游戏规则, 比如点击任意一个格子会改变该格子所在行或列的格子的状态.

• 改变网格大小或形状：除了网格, 还有, 大小的灭灯游戏, 另外也有将正方形改为六边形或其他各种怪异形状的, 如图所示.

下面是一些实物游戏机. [1]

灭灯游戏初探

我们来考虑 网格的灭灯游戏. 游戏的规则是：每格代表一盏灯, 每盏灯只有点亮和熄灭两种状态, 游戏的初始状态是, 9盏灯中有些是亮的, 其余则是暗的. 点击任意一个格子将使得它和相邻格子的灯变换状态.

游戏的目标是用尽可能少的点击数让所有灯都变暗. 那么我们的任务就是要找到游戏的策略：确定要点击哪些格子.

根据灭灯游戏的规则, 通过实验, 可以得出以下个基本且重要的结论：

1. 一个格子点击两次(偶数次)等同于没有操作.

2. 一个格子的状态只取决于它或者与它相邻的格子被点击偶数次还是奇数次, 因此与按键的顺序无关.

由以上两点, 可以得出游戏的策略中每个格子最多被点击次.

模型建立

根据上述结论,我们可以进行如下的数学抽象. 将灭灯游戏中每个灯的状态用表示, 其中表示灯打开, 表示灯关闭. 格子点击的次数只需考虑 , 记集合.

那么灯的状态和格子点击次数均满足以下运算法则:

• (可以理解为熄灭状态+不点击格子=熄灭状态, 这里不点击的格子指的是这个格子及与其相邻的格子.)

• (熄灭状态+点击=点亮状态)

• (点亮状态+不点击=点亮状态)

• (点亮状态+点击=熄灭状态)

这其实对二元集定义了模加法运算, 即相加再求的同余类.

下面我们将目光转向所有灯, 为了指代方便, 我们将灯按进行编号.

于是进一步, 游戏的初始状态可以用一个向量表示, 称为初始状态向量, 记为

其中表示第个灯的状态,

目标状态即灭灯状态则对应零向量

由于点击任意一个格子将使得它和相邻的格子变换状态, 对于每个灯, 都可定义状态转移向量

其中表示点击了号灯第个灯改变了状态, 表示点击了号灯第个灯没有改变状态.

比如,

意思是点击了号灯, 改变了号灯的状态.

意思是点击了号灯, 改变了号灯的状态.

同理, 可以写出所有个灯的状态转移向量.

将游戏从初始状态通过点击某些格子变成灭灯状态, 这一过程对应着

初始状态向量+某几个状态转移向量=零向量.

举个例子:

视频中的游戏过程对应式子：

其中

注意：这里的加法运算是元素相加后再进行模运算.

如果在上式两边分别加上向量, 由于, 因此

一般的, 给定一个初始状态向量 假设表示第 号格子点击的次数(), 那么找到游戏的策略就是解出以下方程：

解向量

称为游戏策略向量.

将个状态转移向量作为列向量组合在一起, 就可以得到行列的矩阵, 称为状态转移矩阵.

于是方程可以写为

所以破解灭灯游戏就是求解上述线性方程组.

面对不同的初始状态, 只需要改变初始状态向量即可. 而对于所有的灭灯游戏, 我们只需要分析线性方程组中的系数矩阵(状态转移矩阵), 即可得到方程是否有解. 从灭灯游戏中可以看到, 矩阵不仅仅是一张数表, 它可以将一个向量变换为另一个向量, 所以矩阵也是一种变换.

模型求解

下面我们将上述模型应用于一个具体的例子.

给出一个灭灯游戏的初始状态, 如图所示.

初始状态向量为

将其代入上述线性方程组中解方程即可求得游戏策略.

下面我们用计算机来完成方程组求解：

# input
import numpy as np
import galois
GF = galois.GF(2)

A = GF([[1, 1, 0, 1, 0, 0, 0, 0, 0],
            [1, 1, 1, 0, 1, 0, 0, 0, 0],
            [0, 1, 1, 0, 0, 1, 0, 0, 0],
            [1, 0, 0, 1, 1, 0, 1, 0, 0],
            [0, 1, 0, 1, 1, 1, 0, 1, 0],
            [0, 0, 1, 0, 1, 1, 0, 0, 1],
            [0, 0, 0, 1, 0, 0, 1, 1, 0],
            [0, 0, 0, 0, 1, 0, 1, 1, 1],
            [0, 0, 0, 0, 0, 1, 0, 1, 1]
            ])

B = GF([1, 1, 0, 0, 0, 0, 0, 0, 0])

x = np.linalg.solve(A, B)
print(x)

# output
# [1 0 1 0 1 1 0 0 1]

游戏策略向量为

即只需要点击 号格子, 即可灭灯.

注意：这里的线性方程组求解是在有限域上进行运算的, 需要用到galois包[2].

更多思考

关于灭灯游戏, 其实还有很多问题可以思考：

解线性方程组需要高斯消去法, 高斯消去法在这里还能适用吗？

灭灯游戏的状态转移矩阵是怎样的? 与灭灯游戏的状态转移矩阵有什么区别?

对于不同网格大小的灭灯游戏, 任意一个初始状态, 是否一定有解？

如果不是, 那么随机选择一个初始状态, 有解的概率是多少？

如果有解, 那么解是否唯一？如果不唯一, 能否找到最优解（最少步数的可行解）?

参考文献：

[1] The Mathematics of Lights Out, https://www.jaapsch.net/puzzles/lomath.htm#refs.

[2] https://github.com/mhostetter/galois

图片来源:

[1] The Mathematics of Lights Out, https://www.jaapsch.net/puzzles/lomath.htm#refs.