九宫格上有 9 个格子,每个格子有 亮(1)和 灭(0)两种状态。点击任意一个格子,它和它上下左右相邻的格子都会翻转(亮变灭、灭变亮)。
目标:把所有格子都变成灭(全 0)。
格子编号采用小键盘布局(7-8-9 在上,1-2-3 在下):
每个格子按下后会影响的范围:
| 按下的格子 | 影响的格子 | 翻转数量 |
|---|---|---|
| 1 号 | 1, 2, 4 | 3 |
| 2 号 | 1, 2, 3, 5 | 4 |
| 3 号 | 2, 3, 6 | 3 |
| 4 号 | 1, 4, 5, 7 | 4 |
| 5 号 | 2, 4, 5, 6, 8 | 5(中心) |
| 6 号 | 3, 5, 6, 9 | 4 |
| 7 号 | 4, 7, 8 | 3 |
| 8 号 | 5, 7, 8, 9 | 4 |
| 9 号 | 6, 8, 9 | 3 |
9 个格子,每个最多按 1 次,总共只有 2⁹ = 512 种按法。计算机遍历所有组合只需微秒级时间,所以"暴力枚举"就是最优解法。
这个问题本质上是一个 GF(2) 上的线性方程组(模 2 运算):
用矩阵表示:Ax = b (mod 2),其中 A 是 9×9 的影响矩阵,b 是初始状态向量。
最简单的方法 —— 用我们的 在线求解器,输入初始状态,一键出解。
如果你想自己解题,可以用逐行消除法:
一些常见的对称模式和对应的解法:
| 需要按的格子数 | 状态数量 | 占比 |
|---|---|---|
| 0(已经是全 0) | 1 | 0.2% |
| 1 | 9 | 1.8% |
| 2 | 36 | 7.0% |
| 3 | 84 | 16.4% |
| 4 | 126 | 24.6% |
| 5 | 126 | 24.6% |
| 6 | 84 | 16.4% |
| 7 | 36 | 7.0% |
| 8 | 9 | 1.8% |
| 9(全按) | 1 | 0.2% |
可以看到,大多数情况(约 66%)需要按 3~5 个格子就能解开。最难的情况也只需要按遍所有 9 个格子。
九宫格翻转游戏有很多变体,核心思路相同: