不知道你有没有遇到过那种让人抓狂的益智小游戏一个网格里每个格子都是一盏灯亮着或灭着。点一下某个格子它自己和上下左右四个邻居都会反转状态。给定一个乱七八糟的初始图案目标是把所有灯全部灭掉或者全部点亮而且指令方案还必须是最佳的——也就是点击次数最少。这就是经典的 Lights Out关灯灯阵问题。文章标题里的“任意给定一个初始图案请你给出一个最佳指令方案”其实就是这个问题的核心。这篇文章我打算从题目拆解开始讲清楚怎么用线性代数建模、怎么用高斯消元求最优解再给出一套可以直接跑起来的代码最后分享几个我实际调试时踩过的坑。1. 题目拆解先看懂规则里藏着的数学模型1.1 点击顺序不重要重要的是点击次数我第一次认真思考这个游戏的时候第一反应是想用搜索硬莽每个格子点或不点2的 n 次方种组合对于一个 5×5 的盘面就是 33554432 种。暴力枚举当然可行但很笨而且题目要求“最佳指令方案”这意味着一组点击序列而不是一个点击过程的录像。这里有个非常关键的观察点击同一个格子两次效果会完全抵消。你在某个格子上点三次和点一次的效果完全一样点四次和点两次一样。这太重要了。因为灯只有亮和灭两种状态而点击造成的是“翻转”翻转两次就回到原点所以每个格子的点击次数只有“按了奇数次”和“按了偶数次”两种有效状态。只要用 0 和 1 来表示“不按”和“按”问题就从“点击顺序”变成了“选择一组格子”。另一个同样重要的观察是点击操作彼此之间满足交换律。你先点 A 再点 B和先点 B 再点 A最终状态完全一样。这一点让“指令方案”可以被理解为一个集合而不是一个时间序列。你在纸上画一个初始图案想找到的最优解就是“选哪些格子各点一次”而不是“按什么顺序点”。1.2 “最佳”到底意味着什么“最佳”这个词在标题里是带约束的。第一种理解是“能找到解就行”但更严格的题面显然要求“最少步数”。对关灯游戏来说最少步数就是点击次数最少的有效指令集合。因为点击顺序不影响结果所以最优方案一定存在一个最小基数的点击集合。任何有效的点击集合哪怕不是最优的也可以被看成一组在二元域上成立的等式。后面我会讲到线性代数会告诉我们要么无解要么有一堆解。在这一堆解里我们需要挑出点击次数最少的那一个这就是“最佳指令方案”的数学定义。另外要注意标题里说“使得所有灯关闭或点亮”也就是说目标状态有两种全灭和全亮。这两个目标在数学上并不是两个独立问题它们的差异只在于初始状态向量取反这一点在 2.3 节我会专门解释。1.3 这题值得研究的三个理由先说实用层面灯阵谜题在不少游戏合辑、逻辑训练 App 里反复出现网络上随便一搜都有人问“这个图案怎么过”。你只要手里有一套通用求解器任何初始图案输入进去立刻就能返回最少步指令这种“一次性解决所有关卡”的感觉非常舒服。再说理论层面这个问题是理解二元域上的线性方程组的绝佳入口。别被“线性代数”吓到实际上你只需要会做两件事把行与行之间做异或操作以及把 0/1 当成“偶数/奇数”来用。一旦你习惯了 mod 2 的算术很多看似离散的组合问题都能用这种方法统一处理。最后一个理由是算法层面的题目隐含了“任意初始图案”这意味着不能只针对某一个特定图形背答案。你需要设计的是通用求解流程这非常考验对问题本质的理解。我会先用数学方式推导再给代码实现整个过程比单纯背解法更有收获。2. 核心建模把灯阵变成一张 GF(2) 上的矩阵方程2.1 状态向量、点击向量和邻接矩阵假设盘面有 r 行 c 列总共有 n r × c 个灯。把所有灯拍扁成一列用 0 表示灭、1 表示亮得到一个长度为 n 的初始状态向量 b。同样地把每个格子是否被点击也写成长度 n 的点击向量 xx 的分量是 0 或 1。接着需要一个矩阵 A用来描述“点击一个格子会影响哪些格子”。A 是一个 n × n 的 0/1 矩阵第 i 行第 j 列等于 1当且仅当点击 j 格子会翻转 i 格子的状态。规则是“点自己或上下左右”所以 A 的对角线全是 1相邻格子的对应位置也是 1。比如一个 3×3 盘面编号从 0 到 8第二行第一列的那个格子也就是坐标 (1,0)它和 (0,0)、(2,0)、(1,1) 以及自己相邻所以 A 里这一行对应这几个位置是 1其余是 0。这个概念可以类比成“每盏灯收到一张来自自己和邻居的翻转账单”。现在看一次点击对最终状态的贡献。灯 i 的最终状态等于初始状态 b_i 加上所有相关点击带来的翻转次数然后对 2 取余。写成公式就是b_i (A x)_i ≡ 最终状态_i (mod 2)2.2 从方程组到增广矩阵目标全灭时所有最终状态都是 0所以得到 G(2) 上的线性方程组A x ≡ b (mod 2)等等这里要特别小心符号。如果初始亮表示 1点击造成翻转最终状态是 b_i (Ax)_i 再取 mod 2。要让最终为 0就需要 (Ax)_i ≡ b_i。为什么是等于 b 而不是等于负 b因为在 mod 2 的世界里加法和减法没有任何区别负号就是自己。所以目标全灭对应的方程就是 A x b。这个方程组解决的是给定初始亮灭图案 b找一组点击向量 x使得每个灯被影响的次数等于它初始状态的相反数也就是等于它本身。下一步是把 A 和 b 拼成一个增广矩阵 [A | b]在这个 n 行 n1 列的矩阵上做高斯消元。消元只允许三种操作交换任意两行、把某一行整体异或到另一行上、把某一行乘以 1。在 mod 2 下乘法 1 没有任何意义所以实际上只需要“行交换”和“行异或”两种操作这比普通实数域的高斯消元简单得多。我举个简单的 2×2 例子。设四个灯编号为 0 到 3邻接矩阵是| 1 1 1 0 | | 1 1 0 1 | | 1 0 1 1 | | 0 1 1 1 |如果初始状态是左上角亮、其余灭也就是 b [1,0,0,0]^T增广矩阵就是| 1 1 1 0 | 1 | | 1 1 0 1 | 0 | | 1 0 1 1 | 0 | | 0 1 1 1 | 0 |这个例子在后买你动手跑代码时可以自己验证。2.3 全灭与全亮一张矩阵方程就能统一标题说“关闭或点亮”所以目标状态可以全是 0也可以全是 1。如果目标是全亮最终状态要满足 b_i (Ax)_i ≡ 1 (mod 2)也就是(Ax)_i ≡ 1 b_i (mod 2)换句话说你把初始向量 b 先取反变成 b b 11 表示全 1 向量然后求解 A x b得到的就是让原始图案全亮的点击方案。这个技巧非常省事我只需要实现一个“求全灭解”的函数然后全亮问题就等价于“把初始图案取反再求全灭”。举个例子3×3 盘面初始全灭目标全亮。取反后的 b 是全 1 向量。实际跑高斯消元会发现点击四个角再加正中间一格也就是 5 步可以让 3×3 全亮。验证一下四个角各被自己和两个邻居影响是 3 次翻转亮四条边上的中间格被两个角加中心影响也是 3 次翻转亮中心被四个角加自己影响5 次翻转亮。这个 5 步方案正好对应方程 A x 全部 1 的一组最优解。3. 最佳指令怎么算通解 枚举自由变量3.1 高斯消元求通解直接解 A x b 的结果有两种无解或者有解。如果存在解并且矩阵不满秩那么解不止一组而是有一个由自由变量决定解族。消元过程中的核心判断是如果某一行左边全是 0但右边是 1那方程无解。这在物理上对应一种情况初始图案超出了这个盘面允许的翻转能力范围。比如 3×3 的标准规则下并不是每个随机图案都能全灭有的图案无论怎么点击都会至少剩下一盏灯这就是无解。消元完成后把所有“主元列”对应的变量称为基本变量其余没有主元的列叫自由变量。整个解可以写成x x_0 c_1 * v_1 c_2 * v_2 ... c_k * v_k其中 x_0 是一组特解v_1 到 v_k 是对应每个自由变量的零空间基向量k 是自由变量个数。c_j 任意取 0 或 1就可以生成全部解。3.2 枚举自由变量按点击次数取最优现在我们已经有一组通解但需要一个点击次数最小的解。点击次数就是 x 里 1 的数量也就是汉明重量。最直接的办法是枚举所有 2^k 组自由变量取值每组都生成一个完整点击向量 x统计它的汉明重量保留最小的那个。这个方法在 k 很小的时候非常快。标准 5×5 的关灯游戏里实践中很多随机图案的自由变量个数并不大枚举几组到几十组之间基本一瞬间完成。如果遇到 k 比较大比如某些特殊图案自由变量到了 8 个以上2^k 也就是 256 种依然可以接受。k 到 15 的时候是 32768 种用位运算来算也毫秒级。枚举的具体实现可以用一个从 0 到 2^k - 1 的循环每次取出一个掩码 mask把 mask 拆成 k 个比特分别乘到对应的零空间向量上再和特解异或起来。伪码就像for mask in range(1 k): x x0.copy() for j in range(k): if (mask j) 1: x ^ free_vector[j] weight x.count_one() update_best(weight, x)这就是“最佳指令方案”的搜索核心。注意这里要用位向量来表示 x否则统计次数和异或都会很慢。3.3 自由变量比较多时还可以用小规模 BFS对小盘面比如 3×3 或 4×4另一个更直观的求解办法是广度优先搜索BFS。从目标状态全灭或全亮反向搜索每次点击一盏灯得到新状态记录第一次到达该状态所需的步数。因为每个状态只需要访问一次3×3 一共 2^9 个状态BFS 可以在非常短的时间内把“每个图案到全灭的最优步数”全部算完。BFS 在这个场景里还有个额外好处它能天然保证最少步数因为它是按步数逐层扩展的。不过 BFS 的缺陷也很明显状态数随盘面大小指数增长。4×4 是 65536 个状态还能跑5×5 直接到 3355 万内存就不太舒服了。所以我的建议是3×3、4×4 用 BFS 预计算而 5×5 及以上用线性代数加枚举自由变量这样既快又稳。3.4 一个完整的手算级实例我拿 3×3 盘面初始全部为 0、目标全部为 1 来演示一下最佳指令求法。取反后的状态 b 全 1。增广矩阵是 9 行 10 列这里行太多我不展开每一行而是直接说消元后得到的关键结论这个方程组有解自由变量有 2 个所以一共有 4 组解。枚举四组之后最少步数是 5对应点击集合是四个角和中心。这个例子非常适合验证你自己的代码是否正确。如果你写一个通用 solver用 3×3 初始全灭、目标全亮来测返回的点击次数应该是 5而且点击位置正好是 (0,0)、(0,2)、(1,1)、(2,0)、(2,2)。一旦跑出这个结果说明建模、消元、枚举三个环节基本都没问题。4. 完整实现Python 代码与操作细节4.1 数据结构用整数的比特位表示矩阵行我写代码时最推崇的表示方法是用 Python 整数直接作为行向量。每一行都有一个整数第 j 位表示该行第 j 列是否为 1。行与行异或就是整数异或消元过程直接用^就能完成既快又不占大内存。对 5×5 的 25 个灯来说一个整数低 25 位就够用根本不用造二维列表。增广矩阵每一行由两部分组成左边 n 位是 A 的行右边第 n 位是 b 的值。所以实际用的整数位长是 n1。比如 n25用一个 26 位的整数表示一行。之所以这么设计是因为高斯消元中最频繁的操作就是“拿第 pivot 行去异或其它行”整数异或理论上比二维数组逐位操作快得多而且代码写起来也优雅。4.2 核心求解器代码下面这份代码是我在实际项目里一直用的版本去掉了无关打印只保留核心求解逻辑。输入是一个二维数组board1 表示亮、0 表示灭target传off表示全灭传on表示全亮。返回一个二维数组click同样 1 表示该格子要点一次。def solve_lights_out(board, targetoff): r len(board) c len(board[0]) n r * c # 构建初始向量 b并统一到“求全灭”问题的形式上 b 0 for i in range(r): for j in range(c): idx i * c j if board[i][j]: b | 1 idx if target on: # 全亮等价于初始取反后求全灭 b ^ (1 n) - 1 # 构建邻接矩阵 A 的每一行并用整数表示 mat [] for i in range(r): for j in range(c): row 0 idx i * c j row | 1 idx for di, dj in ((-1,0),(1,0),(0,-1),(0,1)): ni, nj i di, j dj if 0 ni r and 0 nj c: row | 1 (ni * c nj) mat.append(row) # 增广矩阵[A | b] aug [mat[i] | ((b i) 1) n for i in range(n)] # 高斯消元GF(2) pivots [] row 0 col 0 while row n and col n: # 找一个当前列含 1 的行 pivot -1 for i in range(row, n): if (aug[i] col) 1: pivot i break if pivot -1: col 1 continue aug[row], aug[pivot] aug[pivot], aug[row] # 消去其它行当前列的 1 for i in range(n): if i ! row and ((aug[i] col) 1): aug[i] ^ aug[row] pivots.append(col) row 1 col 1 # 检查无解 for i in range(n): left aug[i] ((1 n) - 1) right (aug[i] n) 1 if left 0 and right 1: return None # 无解 # 从 RREF 中提取特解和自由变量 x0 [0] * n free_cols [] used set(pivots) for col in range(n): if col in used: continue free_cols.append(col) # 特解主元行对应的右边值 for i, pcol in enumerate(pivots): x0[pcol] (aug[i] n) 1 # 对每个自由列构造零空间向量 free_vecs [] for free_col in free_cols: vec [0] * n vec[free_col] 1 for i, pcol in enumerate(pivots): if (aug[i] free_col) 1: vec[pcol] 1 free_vecs.append(vec) # 枚举自由变量组合找最小汉明重量 k len(free_cols) best_x None best_w n 1 for mask in range(1 k): x x0[:] for j in range(k): if (mask j) 1: for t in range(n): x[t] ^ free_vecs[j][t] w sum(x) if w best_w: best_w w best_x x # 转回二维点击矩阵 click [[0] * c for _ in range(r)] for t in range(n): if best_x[t]: click[t // c][t % c] 1 return click这段代码有几个值得注意的点。第一构建邻接矩阵时我特意用了row | 1 idx不遗漏自己。第二增广矩阵的右边位放在第 n 位消元时行异或不会把右边的位弄丢。第三零空间向量构造时先置自由变量本身为 1再根据 RREF 中该列在每一行的取值回代基础变量这是标准操作。4.3 我踩过的几个坑第一个坑是忘记全部模 2。最早我试图用普通浮点高斯消元来处理结果出现了 0.5、0.333 这类小数然后整个逻辑就崩了。其实在 GF(2) 上根本不需要做除法或乘小数只需要“异或”和“找主元”就能解决全部问题。后来我在代码开头就注释这是二元域不是实数域心态完全不同。第二个坑是枚举自由变量的时候把掩码直接当成了点击向量。掩码长度是自由变量的个数 k而点击向量长度是 n。必须把 mask 的每一位拆开依次异或对应的零空间向量不能拿 mask 本身去做汉明重量统计。这个错误很隐蔽我一开始甚至没发现后来发现解出来的点击次数总是和 BFS 不一致才排查出来。第三个坑是在做“全亮”目标时我只改了目标状态而没有改初始向量。实际上应该把初始向量 b 取反再走“全灭”的求解流程。如果只是把最终检查从“全灭”改成“全亮”结果会错得很离谱。第四个坑是边界条件。相邻关系里四个方向必须做边界检查不能用ni, nj直接索引二维数组。如果越界了还继续算就会把离得很远的灯错误地连到一起。这种情况在 3×3 和 5×5 上表现完全不同很容易让人误以为算法随机出错。5. 常见问题速查与实战经验5.1 无解的情况怎么处理高斯消元判断无解的条件是一行左边全 0、右边为 1。在实际使用时随机生成的图案有一定概率无解。碰到这种情况程序会返回None。这时可以有几种处理方式一是允许用户调整盘面尺寸二是扩展点击规则比如点击影响范围变成立方向或九宫格三是对无解图案做“最近可解图案”的搜索。最后那种做法适合做游戏提示但需要额外设计距离函数复杂度会高不少日常解题不太划算。如果你想快速验证某个盘面是否有解可以在输入代码后先检查返回值不为None才继续显示点击方案。这比花时间找近似解更符合“最佳指令方案”的要求。5.2 有多组解时怎么选解不唯一时枚举自由变量可能找到多个点击次数相同的方案。代码里best_x总是取第一个碰到的最优解所以你看到的是一组最佳方案但不是唯一一组。如果游戏要求“答案唯一”那通常是因为关卡设计者在选择初始图案时故意让矩阵满秩但这种条件非常苛刻标准 5×5 满足满秩的图案只占所有图案的一小部分。我在实际使用时不会在意唯一性因为最少步数往往就是玩家想要的。如果产品需求里需要显示“其中一种最优解”那代码保持现状即可。如果需要展示全部最优解可以让枚举阶段记录所有等于最小重量的解数量一般也不会太多。5.3 大规模盘面怎么提速5×5 型够用但如果你把盘面改成 10×10n100枚举自由变量可能因为 k 值较大而变慢。这时候可以换思路先做一次完整的 RREF再看自由变量个数。如果 k 超过 202^k 会到百万级别虽然还能跑但体验不好。可以考虑用分支限界剪枝在枚举过程中维护当前部分解的重重量一旦超过已知最优解就提前剪掉。另一个更暴力的优化方式是“预计算点击向量库”对固定尺寸的盘面预先算出每个可解状态对应的最优点击向量存成字典。在线查询只需要做一次状态检索复杂度可以降到 O(1)。代价是离线构建时间很长不过对 5×5 来说完全值得2^25 个状态太多但如果只保存实际关卡出现的图案内存是可控的。我在多次实际测试中发现结合线性代数高斯消元加小规模枚举已经是通用场景下最均衡的方案。它既不需要庞大的预计算表也能应对绝大多数随机输入。如果你也打算自己实现一遍我强烈建议先用 3×3 全灭全亮两个经典用例做回归验证确认输出步数无误之后再上 5×5 随机图案压力测试。说一个我最深刻的体验这类看起来纯粹靠脑洞的谜题一旦你把“点击次数”和“翻转奇偶性”抽象成二元域上的向量与矩阵解题思路会瞬间变得异常清晰。而且这套方法不只适用于关灯游戏很多带“点一个影响一片”规则的推箱子变体、质数游戏、甚至一些棋盘翻转谜题都可以沿用同样的建模套路。以后你再遇到这类谜题至少可以先从“异或消元”这个方向想而不是上来就暴力搜索。