用线性代数解灭灯游戏

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

灭灯游戏背后的本质是线性代数, 本文将通过建立矩阵模型, 将经典的灭灯游戏的破解转化为求解一次线性方程组的问题.

灭灯游戏及其变体

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

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

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

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

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

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

我们来考虑 网格的灭灯游戏. 游戏的规则是：每格代表一盏灯, 每盏灯只有点亮和熄灭两种状态, 游戏的初始状态是, 9盏灯中有些是亮的, 其余则是暗的. 点击任意一个格子将使得它和相邻格子的灯变换状态. 游戏的目标是用尽可能少的点击数让所有灯都变暗. 下面我们给出一个初始状态，如图所示.

首先根据灭灯游戏的规则, 可以得出以下3个基本且重要的结论：

1. 一个格子点击两次(偶数次)不改变状态.

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

3. 从初始状态到灭灯状态和从灭灯状态回到初始状态所点击的格子是一样的.

进一步,我们将灭灯游戏中每个灯的状态用 表示, 其中1表示灯打开, 0表示灯关闭. 格子点击的次数只考虑 .

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

即对于二元集 定义相加再模2运算, 即2的同余类加法运算.

现在回到我们的问题, 只需要考虑将全灭状态 转为 该初始状态. 我们将灯按1-9进行编号.

假设 表示第 号格子点击的次数.

先考虑 号灯, 其初始状态为点亮的, 可以发现只有点击 号格子, 才会影响该灯的状态.

于是便有方程 .

同理,可以列出其他格子对应的方程, 便可得到一个9元1次方程组.

为了表述和计算的方便,下面我们通过矩阵表示来建立线性方程组.

用矩阵表示

初始状态可以用一个向量 表示, 其元素来自于集合 , 1表示灯是打开的, 0 表示灯是关闭的.

所以图1的状态用向量表示就是

称为初始状态向量.

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

比如, 在全灭的状态, 点击 号灯, 则有

在全灭的状态, 点击 号灯, 有

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

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

其中 表示零向量, 表示灭灯游戏中灯全灭的状态.

向量的加法遵循常规的矩阵加法运算, 只是这里元素相加后需要再进行模2运算.

于是 ，因此 。等式两边加上 后，得到 。

一般的, 给定一个初始状态向量 假设 表示第 号格子点击的次数(只需要考虑 即可), 那么找到游戏的最优解就是解出方程：

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

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

灭灯游戏求解

对于上文中 灭灯游戏的初始状态, 其求解只需要在线性方程组中将初始状态向量, 代入.

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

# input

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]

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

注意：这里的线性方程组求解是在有限域GF2上进行运算的, 需要用到 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.

来源：数来数趣

编辑：小咕咕

转载内容仅代表作者观点

不代表中科院物理所立场

如需转载请联系原公众号

1.2.

3.

4.

5.

6.

7.

8.

9.

10.