关灯游戏背后的数学
灭灯游戏是一个经典益智游戏，游戏的规则非常简单，在一个 n × n 的网格里的每格都会有一盏灯，点击任意格子都会反转该灯和其上下左右所有相邻灯的状态，最终目标是将所有灯都关掉，无论你有没有玩过，你都可以在这里体验一下。
游戏最早的原型竟然是来自于一个玩具，而最原始的电子游戏版本叫做关灯游戏，在我印象里以前小时候玩的怎么都叫做点灯游戏，最基础的谜题是所有格子的灯都是打开的，按照对称的方法去尝试很容易就能解出来，提升一点难度后的谜题则是起始只有一部分灯是打开的，你可以在这个链接里点击页面里的 Random 体验。
解法解释
很明显这是一个数学相关的谜题，游戏的解法和线性代数强相关，Lights Out Puzzle 是一份比较通俗易懂的解析，下面我将略过专业知识，尝试用最简单的 2x2 的谜题来通俗解释。假设初始谜面是下面表格，一开始只有左上角的灯亮着，这个实际上等于一个只有 0 和 1 的矩阵，1 为亮灯状态，0 为灭灯状态。
目前博客没有支持数学公式的显示，暂时只能用表格的形式表示了。
| 1 | 0 |
|---|---|
| 0 | 0 |
点击左上角影响的是左上、右上和左下 3 个格子，即等于下面这个矩阵。
| 1 | 1 |
|---|---|
| 1 | 0 |
点击左上角的位置 1 次，等于原始的矩阵和这个矩阵相加，相加的方式很简单，就是对应每个格子相加而已，即会变成以下的矩阵。
| 2 | 1 |
|---|---|
| 1 | 0 |
此时左上的格子数值为 2，实际上格子在点击后，已经变回了灭灯状态，即数值应该为 0，以此类推，当再点击一次后，这个格子数值为 3，变回亮灯状态，数值应该为 1。
以此可见，矩阵相加后的数值偶数应该转化为 0，奇数转换为 1，这样是符合当前灯的状态的，这个称为模 2 运算，经过这个变换后的矩阵为：
| 0 | 1 |
|---|---|
| 1 | 0 |
依照上面这个步骤，我们最终需要做的是计算出 4 个格子分别需要点击多少次，接下来我们把每个格子的点击次数当作未知数，以 x11 表示点击左上格子的次数，x12 表示点击右上格子的次数，x21 表示点击左下格子的次数，x22 表示点击右下格子的次数。
目前博客也没有支持上下标的显示，暂时只能用这样的方式表示了。
左上格子的数值会受到 x11、x12 和 x21 的点击次数影响，因此我们可以得出方程：
x11+x12+x21=1
同理，根据其他格子的数值也能列出另外 3 条方程：
x11+x12+x22=0
x11+x21+x22=0
x12+x21+x22=0
解这个方程的关键点：
- 单个解的结果只会是 1 和 0，因为点击 3 次的效果等于点击 1 次
- 最终结果为 1 指的是模 2 运算后结果
依照这个规则，解出来的结果是： x11=1, x12=1, x21=1, x22=0
换成形象的操作，即最开始谜面的解法是按左上 1 次、右上 1 次和左下 1 次，这里还隐藏了一个细节，解法和点击顺序无关，只和点击次数有关。以上就是这个基础谜题的数学解法，3x3、4x4 或更大的其他网格，计算的基础原理也和以上一样。
关于解
任意谜题都可解吗
在这个问题上我其实先入为主了，在上面我写到 n × n，实际上关灯游戏的范围可以是 m × n，m 和 n 不一定相等。在处于随机的起始状态时，无论 m 与 n 是否相等，谜题都不一定有解。只有当一开始灯是全亮且为 n × n 的情况时，谜题才必然有解， Linear cellular automata and the Garden of Eden 这篇里有详细的证明。
作为外行人发现有意思的另一点是这篇文献的名称出现了「伊甸园」这个词，里面也对此有解释：“Any pattern Z such that p (Z) = X is called a predecessor of X under the global rule p. A pattern that fails to have any predecessors is frequently called a Garden-of-Eden: once ‘lost’ it remains inaccessible forever”
里面提到了很多专业名词，我借助 AI 的辅助大概理解了这个比喻：亚当和夏娃被驱逐出了伊甸园后再也无法返回，类比于没有来源的初始状态，而 n x n 的开灯问题（文献中说的全一问题）永远有来源，无论是什么状态下都可以演化到全开的状态，因此它永远不会是伊甸园。
可见这里说的伊甸园模式，并非我们一般理解的代表「理想环境」的伊甸园。
通用解法和最小解
小时候玩关灯游戏的解法都是先随便按一通，然后有点规律后再思考怎么按，而这个游戏有一个不需要计算的通用性策略 Light Chasing，即从第一行开始，用第二行来灭第一行的灯，依次类推，等剩下最后一行时，根据最后一行的亮灯情况来调整第一行，再重新来一遍，就可以完成了，这个方法保证谜题如果存在解就能得到一个解。
线性代数的解法保证了问题有解，但并不一定是最小解，上面的论文里也提到了找到最小解很难。
the problem of determining an odd-parity cover of minimal cardinality turns out to be computationally difficult: the corresponding optimization problem is NP-hard
如果你想了解更多关灯游戏的信息，我推荐阅读以下几个链接：
- Lights Out：极其详细的关灯游戏介绍
- 点灯游戏与数学之美：从程序开发的角度探讨灭灯游戏，解的视觉呈现让我印象深刻
- ALL LIGHTS AND LIGHTS OUT：关于灭灯游戏的数学教育材料
变体
在后续的发展中，关灯游戏产生了很多不同的变种，这里简单列出几个：
- 3x3 Lights Out of 3 states：灯拥有了多个颜色；
- Hysteria：目标是将网格填满颜色，每次点击方格将会随机变为 6 个颜色中的一种，一旦新颜色和相邻方格颜色一样，就会触发灭灯游戏的规则，这规则确实很符合歇斯底里的名字；
- Lights Out：你可以在这里也看到很多变种，比如立方体和球形模式；
上面是当时在做 龙年第一杯喝什么小活动时做的小调研的重新整理，我们也曾考虑过其他的一些小游戏，比如推箱子、 Dots and boxes、 四色定理、一笔画、接水管或者基于前一个网页上的其他谜题。
分享我们发现的另一个有趣谜题：Impossible Escape?
我认为这些谜题不那么经典和大众化，或是不满足我们当时设想的只需要「点击交互」这个条件，所以最终选择了关灯游戏。重新整理这篇文章，又让我再一次感受到了数学真有趣。