用线性代数解灭灯游戏

中科院物理所

2024-10-23 12:45发布于北京中科院物理所官方账号

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

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

灭灯游戏及其变体

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

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

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

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

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

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

研究灭灯游戏

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

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

一个格子点击两次(偶数次)不改变状态.
一个格子的状态只取决于它被点击偶数次还是奇数次, 因此与按键的顺序无关.
从初始状态到灭灯状态和从灭灯状态回到初始状态所点击的格子是一样的.

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

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

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

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

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

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

于是便有方程 .

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

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

用矩阵表示

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

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

称为初始状态向量.

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

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

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

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

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

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

向量的加法遵循常规的矩阵加法运算, 只是这里元素相加后需要再进行模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]

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

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

用线性代数解灭灯游戏

研究 灭灯游戏

灭灯游戏求解

更多思考

研究灭灯游戏