Flip Tiles 的最优解:用线性代数破解 Lights Out
我做 Flip Tiles 时遇到一个直观问题:这游戏明明每次点击都改变 5 个格子的状态,看起来该非常混乱才对,为什么有些初始状态能轻易解开,有些却怎么都解不出来?答案藏在线性代数里。这篇说说怎么解。
问题的真实结构
先做一个反直觉的观察:点击同一个格子两次,跟没点击一样。 因为每个格子状态(亮/暗)是二元的(开关),按两次就回到原状态。所以,无论你按什么顺序、按多少次,只要每个格子最终被按的次数一致(奇数次或偶数次),结果就一样。
这意味着 5x5 棋盘上,你不需要考虑"按多少次"或"按的顺序",你只需要决定 25 个格子中哪些"要按一次,哪些不按"。这是一个 2^25 ≈ 3300 万种选择的问题。
这种"每个变量只能取 0 或 1"的代数结构,叫做 GF(2) 上的线性代数(伽罗瓦域,Galois Field 2)。它跟我们常见的实数代数最大的区别是:1 + 1 = 0(因为按两次等于没按)。
把游戏写成方程
对每个格子 (i, j),它的最终亮暗状态取决于:
- 它的初始状态
- 它自己被按的次数(每次自己被按,自己翻转)
- 它的 4 个邻居被按的次数(每次邻居被按,自己也翻转)
所以"格子 (i,j) 最终亮"这个条件,可以写成一个 GF(2) 上的线性方程。25 个格子 → 25 个方程,共 25 个未知数(每个格子按或不按)。
剩下的就是经典的高斯消元法(Gaussian Elimination),只不过在 GF(2) 上做。本科线性代数会讲。
但我不需要你懂线性代数
说了那么多数学,只为了引出一个非常实用的玩法策略:光追溯法(Light Chasing)。这是 1990 年代的 Lights Out 玩家社区集体总结出来的。
光追溯的核心思想:
从第二行开始,如果某个格子上方(第一行)的对应位置是亮的,你就按这个格子。这样按完整张棋盘后,前 4 行一定全暗,只剩最后一行未知。
具体来说:
- 逐行处理,从第二行(y=1)到第五行(y=4)
- 对于每一行 y 的每个格子 (x, y):如果上方 (x, y-1) 是亮的,就按 (x, y) 这个格子
- 处理完所有行之后,前 4 行必然全暗
- 看最后一行:它可能全暗(直接赢)、可能有特定模式(用查找表解)、可能无解
关键是步骤 4。光追溯法不能 100% 解决所有 5x5 棋盘,因为有些初始状态本身就无解(数学上叫"不在解空间")。但 ——
BverGame 的 Flip Tiles 保证有解
这是我编游戏时做的一个关键决定:我们的生成器从"全亮"状态出发,随机做 N 次按动反推。 这保证生成的所有初始状态都至少有一个解,因为我们就是反着推回来的。
这跟"先随机生成棋盘,再判断有没有解"完全不同。后者要做高斯消元才能判定,而且大约 75% 的随机棋盘是无解的(只有 2^15 = 32768 / 2^25 = 33554432 ≈ 1024 个状态可解)。
所以你可以放心地在 Flip Tiles 上死磕任何一关 —— 它一定有解。如果你卡住了,试试光追溯法。
更高维的情况
3x3 棋盘:8 维解空间,所有 512 个状态都可解。
4x4 棋盘:16 维解空间,所有 65536 个状态都可解。
5x5 棋盘:23 维解空间,只有 2^23 = 8,388,608 / 2^25 = 33,554,432 ≈ 25% 状态可解。
6x6 棋盘:回到全状态都可解。
这个不规则的现象,源自 GF(2) 矩阵的"零空间维度"周期性 —— 5x5 这种特殊大小的矩阵有 2 维零空间,所以解空间缩小了 4 倍。这种"有些尺寸能解、有些不能"的奇特性,是 Lights Out 数学上的迷人之处。
实战:5x5 的最短解
对一个标准的 Lights Out 5x5 棋盘(初始 25 个亮),最短解步数据知道是 15 步。这是数学证明的结果,任何完美玩家都做不到比 15 步少。
但 BverGame 的 Flip Tiles 不是从"全亮"开始,而是从"全亮"反推 5-15 次操作。所以你的最佳解步数就是反推的次数 —— 通常是 5-20 步之间,具体看关卡。
结尾:数学不是用来吓人的
我写这篇文章不是为了炫耀我懂线性代数。我想说的是:很多看似随机的小游戏,背后都有非常优美的数学结构。理解了这个结构,你就不再是"盲玩",而是真正在跟设计者对话。
下次你点开 Flip Tiles,试着先用眼睛扫一遍棋盘 —— 想想光追溯。多玩几次,你会发现自己进步神速。
而且,这个技巧能让你在朋友面前显得很神秘。
作者 Leo 是 BverGame 联合工程师。本文涉及的 Lights Out 数学结构在 Marlow Anderson 与 Todd Feil 1998 年的论文 "Turning Lights Out with Linear Algebra" 中有完整证明。光追溯法的玩家术语沿用自 1990 年代 Lights Out 玩家社区,具体出处已难以追溯。