熄灯游戏（Lights Out）是1995年Tiger Electronics推出的经典掌上逻辑益智游戏。一块由灯格组成的棋盘上，每盏灯初始随机亮灭；玩家点击任意灯格时，该格及其上下左右邻格的开关状态都会翻转。目标是在最少步数内将所有灯熄灭。看似简单的规则背后，隐藏着模2线性代数与高斯消元的深刻数学结构。本文将用Java完整实现该游戏的自动求解引擎，从状态压缩到GF(2)域上的方程组求解逐层展开。
一、游戏规则与状态压缩
1.1 为什么可以压缩为位向量
标准的熄灯游戏采用 5×5 棋盘，共25盏灯。每盏灯只有”亮”（1）和”灭”（0）两种状态，天然适合用二进制位表示：
- 棋盘状态 → 25位无符号整数（
int的低25位即可容纳） - 点击操作 → 同样25位掩码，第i位为1表示点击第i格
这种压缩带来巨大优势：状态的”异或”（XOR）操作直接对应灯的翻转逻辑，且所有运算可在CPU寄存器内完成。
1.2 棋盘与邻接掩码生成
将 5×5 棋盘按行优先展平为 0~24 的一维索引。对于每个位置 i，生成一个”影响掩码”：第 i 位及其上下左右邻位均为1。
import java.util.*;
/**
* 熄灯游戏核心类
* 棋盘大小可自定义，默认为经典的5×5
*/
class LightsOut {
final int rows;
final int cols;
final int n; // 总灯数 = rows * cols
final int[] effect; // effect[i] = 点击第i格时影响的位掩码
LightsOut(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.n = rows * cols;
this.effect = new int[n];
buildEffectMasks();
}
/**
* 构建每个位置的影响掩码
* 点击位置 (r,c) 会翻转自身及上下左右共5个邻格
*/
private void buildEffectMasks() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int idx = r * cols + c;
int mask = 0;
// 自身
mask |= 1 << idx;
// 上
if (r > 0) mask |= 1 << ((r - 1) * cols + c);
// 下
if (r + 1 < rows) mask |= 1 << ((r + 1) * cols + c);
// 左
if (c > 0) mask |= 1 << (r * cols + (c - 1));
// 右
if (c + 1 < cols) mask |= 1 << (r * cols + (c + 1));
effect[idx] = mask;
}
}
}
/**
* 执行一次点击操作
* @param board 当前棋盘状态（位掩码）
* @param pos 点击的位置索引
* @return 操作后的新状态
*/
int press(int board, int pos) {
return board ^ effect[pos];
}
/**
* 批量执行一组点击（掩码形式）
* @param board 当前棋盘状态
* @param clicks 点击掩码，第i位为1表示点击第i格
* @return 最终棋盘状态
*/
int pressAll(int board, int clicks) {
// 每个被点击的格都会施加其影响掩码
int result = board;
for (int i = 0; i < n; i++) {
if ((clicks & (1 << i)) != 0) {
result ^= effect[i];
}
}
return result;
}
/**
* 检查是否全部熄灭
*/
boolean isAllOff(int board) {
return board == 0;
}
/**
* 打印棋盘状态（用于调试与演示）
*/
void printBoard(int board) {
for (int r = 0; r < rows; r++) {
StringBuilder line = new StringBuilder();
for (int c = 0; c < cols; c++) {
int idx = r * cols + c;
line.append((board & (1 << idx)) != 0 ? "● " : "○ ");
}
System.out.println(line.toString().trim());
}
}
/**
* 生成随机初始状态
*/
int randomBoard(Random rand) {
// 5×5 棋盘最多25位，int 完全容纳
if (n >= 31) {
int state = 0;
for (int i = 0; i < n; i++) {
if (rand.nextBoolean()) state |= (1 << i);
}
return state;
}
return rand.nextInt(1 << n);
}
}
二、从游戏到线性方程组
2.1 数学建模
设棋盘有 n 盏灯，当前状态为向量 b（b[i] = 1 表示第 i 盏灯亮）。设我们的点击方案为向量 x（x[i] = 1 表示点击第 i 格）。因为每盏灯被翻转偶数次等于没翻、奇数次等于翻一次，所以所有运算都在 GF(2)（模2整数域）上进行。
对于第 i 盏灯，它被翻转的总次数等于所有影响它的点击操作之和（模2）：
Σ A[i][j] * x[j] ≡ b[i] (mod 2)
其中 A[i][j] = 1 表示点击第 j 格会影响第 i 盏灯。显然 A 就是上面生成的 effect 矩阵的转置。目标是让所有灯熄灭，即：
A * x ≡ b (mod 2)
这是一个 n 元模2线性方程组，可用高斯消元求解。
2.2 GF(2) 高斯消元的特殊性
在普通实数域上，高斯消元涉及乘除法；而在 GF(2) 上：
- 加法 = 异或（XOR）
- 乘法 = 逻辑与（AND）
- 没有除法，主元只能是1；若主元为0则找下方行交换
- 消元时只需用 XOR 替代减法
这使得 GF(2) 上的高斯消元代码异常简洁，且可用位运算对整个行进行并行操作。
三、核心算法：GF(2) 高斯消元求解器
/**
* GF(2) 域上的高斯消元求解器
* 求解 A * x = b (mod 2)
*
* 增广矩阵有 n 行、n+1 列（最后一列为 b）
* 每一行用一个 int[] 存储，每个 int 的每一位代表一列
* 对于 n<=25 的棋盘，一行只需一个 int 即可容纳
*/
class Gf2Solver {
/**
* 求解结果封装
*/
static class Solution {
// 是否有解
boolean solvable;
// 一个特解（若存在）
int particular;
// 自由变量掩码：第i位为1表示x[i]是自由变量
int freeMask;
// 齐次解空间的基向量（每个向量是一个int掩码）
List<Integer> nullspaceBasis;
Solution() {
nullspaceBasis = new ArrayList<>();
}
}
/**
* 对增广矩阵执行高斯消元并求解
*
* @param aug 增广矩阵，aug[row] 的第0~n-1位是A的行，第n位是b[row]
* @param n 未知数个数（也是方程个数）
* @return 求解结果，包含特解与零空间基
*/
Solution solve(int[] aug, int n) {
Solution sol = new Solution();
// 复制矩阵避免修改外部数据
int[] a = aug.clone();
// rowForCol[col] = 该列主元所在的行号，-1表示自由变量
int[] rowForCol = new int[n];
Arrays.fill(rowForCol, -1);
int row = 0;
for (int col = 0; col < n && row < n; col++) {
// 寻找主元：当前列中从row行开始第一个值为1的行
int pivot = -1;
for (int r = row; r < n; r++) {
if (getBit(a[r], col)) {
pivot = r;
break;
}
}
if (pivot == -1) {
// 该列为自由变量
continue;
}
// 交换当前行与主元行
int tmp = a[row];
a[row] = a[pivot];
a[pivot] = tmp;
rowForCol[col] = row;
// 消去其他行中该列的1（GF(2)下用XOR）
for (int r = 0; r < n; r++) {
if (r != row && getBit(a[r], col)) {
a[r] ^= a[row];
}
}
row++;
}
// 检查是否有矛盾方程 0 = 1
for (int r = 0; r < n; r++) {
boolean allZero = true;
for (int c = 0; c < n; c++) {
if (getBit(a[r], c)) {
allZero = false;
break;
}
}
if (allZero && getBit(a[r], n)) {
// 0 = 1，无解
sol.solvable = false;
return sol;
}
}
sol.solvable = true;
// 提取特解：主元变量取增广列的值，自由变量取0
int particular = 0;
for (int col = 0; col < n; col++) {
if (rowForCol[col] != -1 && getBit(a[rowForCol[col]], n)) {
particular |= (1 << col);
} else if (rowForCol[col] == -1) {
sol.freeMask |= (1 << col);
}
}
sol.particular = particular;
// 提取零空间基向量
// 对每个自由变量，将其设为1、其余自由变量设为0，回代求得主元变量
for (int freeCol = 0; freeCol < n; freeCol++) {
if ((sol.freeMask & (1 << freeCol)) == 0) continue;
int vec = (1 << freeCol); // 自由变量部分
for (int col = 0; col < n; col++) {
if (rowForCol[col] == -1) continue;
// 看该主元行在 freeCol 处是否为1
if (getBit(a[rowForCol[col]], freeCol)) {
vec |= (1 << col);
}
}
sol.nullspaceBasis.add(vec);
}
return sol;
}
private boolean getBit(int val, int bit) {
return (val & (1 << bit)) != 0;
}
}
四、求解引擎：从棋盘到最少点击方案
4.1 为什么需要搜索零空间
高斯消元给出一个特解 x₀，但若方程组有自由变量，则通解为：
x = x₀ + k₁·v₁ + k₂·v₂ + ... (mod 2)
其中 v₁, v₂, ... 是零空间的基向量。因为我们要找最少点击次数的方案，所以需要枚举所有 2^d 种组合（d 为零空间维数），统计每种解的1的位数（汉明重量），取最小者。
对于经典 5×5 熄灯游戏，d = 2，即最多只有 2² = 4 种候选解，枚举代价极低。
/**
* 熄灯游戏求解引擎
* 将游戏状态转化为线性方程组并求解最优点击方案
*/
class LightsOutSolver {
private final LightsOut game;
private final Gf2Solver solver;
// 预计算好的系数矩阵增广形式（最后一列初始为0，实际求解时替换为b）
private final int[] baseAug;
LightsOutSolver(LightsOut game) {
this.game = game;
this.solver = new Gf2Solver();
this.baseAug = buildAugmentedMatrix();
}
/**
* 构建系数矩阵 A 的增广形式（暂不填充常数列 b）
* A[i][j] = 1 表示点击第j格会影响第i盏灯
*/
private int[] buildAugmentedMatrix() {
int n = game.n;
int[] aug = new int[n];
for (int i = 0; i < n; i++) {
// 第 i 行：哪些 effect 掩码包含第 i 位
int row = 0;
for (int j = 0; j < n; j++) {
if ((game.effect[j] & (1 << i)) != 0) {
row |= (1 << j);
}
}
aug[i] = row; // 最后一列（第n位）暂时为0
}
return aug;
}
/**
* 求解给定棋盘状态的最优点击方案
* @param board 当前棋盘位掩码
* @return 最优点击掩码，若无解返回 -1
*/
int solve(int board) {
int n = game.n;
int[] aug = baseAug.clone();
// 填充增广列（第n位）
for (int i = 0; i < n; i++) {
if ((board & (1 << i)) != 0) {
aug[i] |= (1 << n);
}
}
Gf2Solver.Solution sol = solver.solve(aug, n);
if (!sol.solvable) {
return -1;
}
// 枚举零空间的所有组合，寻找点击次数最少的解
int best = sol.particular;
int bestCount = Integer.bitCount(best);
int d = sol.nullspaceBasis.size();
// 枚举 2^d 种线性组合
for (int mask = 1; mask < (1 << d); mask++) {
int candidate = sol.particular;
for (int i = 0; i < d; i++) {
if ((mask & (1 << i)) != 0) {
candidate ^= sol.nullspaceBasis.get(i);
}
}
int cnt = Integer.bitCount(candidate);
if (cnt < bestCount) {
bestCount = cnt;
best = candidate;
}
}
return best;
}
/**
* 将点击掩码转换为人类可读的位置列表
*/
List<int[]> clicksToPositions(int clicks) {
List<int[]> list = new ArrayList<>();
for (int i = 0; i < game.n; i++) {
if ((clicks & (1 << i)) != 0) {
list.add(new int[]{i / game.cols, i % game.cols});
}
}
return list;
}
}
五、完整运行示例
public class LightsOutDemo {
public static void main(String[] args) {
Random rand = new Random(42);
LightsOut game = new LightsOut(5, 5);
LightsOutSolver solver = new LightsOutSolver(game);
System.out.println("=== 熄灯游戏自动求解演示 ===\n");
// 生成随机初始状态
int board = game.randomBoard(rand);
System.out.println("初始棋盘（●=亮，○=灭）：");
game.printBoard(board);
System.out.println();
// 求解
int clicks = solver.solve(board);
if (clicks == -1) {
System.out.println("该状态无解！");
return;
}
System.out.println("最优点击方案（共 " + Integer.bitCount(clicks) + " 步）：");
List<int[]> positions = solver.clicksToPositions(clicks);
for (int[] p : positions) {
System.out.println(" 点击 (" + p[0] + ", " + p[1] + ")");
}
System.out.println();
// 验证：执行所有点击后是否全灭
int after = game.pressAll(board, clicks);
System.out.println("执行点击后的棋盘：");
game.printBoard(after);
System.out.println("全部熄灭？" + game.isAllOff(after));
System.out.println();
// 演示2：构造一个已知有解的特殊图案
System.out.println("=== 演示2：全亮棋盘 ===");
int allOn = (1 << 25) - 1; // 25位全1
game.printBoard(allOn);
int clicks2 = solver.solve(allOn);
System.out.println("最优解步数：" + Integer.bitCount(clicks2));
int after2 = game.pressAll(allOn, clicks2);
game.printBoard(after2);
System.out.println("全部熄灭？" + game.isAllOff(after2));
System.out.println();
// 演示3：单次点击后的求解
System.out.println("=== 演示3：仅中心一格亮 ===");
int center = 1 << 12; // (2,2) 为中心
game.printBoard(center);
int clicks3 = solver.solve(center);
System.out.println("最优解步数：" + Integer.bitCount(clicks3));
int after3 = game.pressAll(center, clicks3);
game.printBoard(after3);
System.out.println("全部熄灭？" + game.isAllOff(after3));
}
}
六、复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 影响掩码生成 | O(rows × cols) |
O(n) |
n = rows×cols |
| 构建系数矩阵 | O(n²) |
O(n) |
每行检查n个effect |
| GF(2)高斯消元 | O(n³ / wordsize) |
O(n) |
行操作可用位运算并行 |
| 零空间枚举 | O(2^d × n) |
O(n) |
d为零空间维数，5×5时d=2 |
| 单次pressAll | O(n) |
O(1) |
遍历所有位 |
对于经典 5×5 棋盘（n = 25），高斯消元仅需处理 25×25 的二进制矩阵，现代CPU可在微秒级完成。即使扩展到 10×10（n = 100），毫秒级求解也绰绰有余。
七、延伸思考
- 变体规则：若点击只翻转邻格而不翻转自身，只需修改
buildEffectMasks中去掉mask |= 1 << idx即可，数学框架完全不变。 - 高维扩展：三维熄灯游戏（灯格排成立方体）同样可建模为模2线性方程组，只是
n增大导致矩阵更大。 - 最少步数下界：信息论下界为
log₂(n) / log₂(5)步（每步最多影响5盏灯），可快速排除不可能解。 - 矩阵预求逆：若需要反复求解不同初始状态，可预计算
A的伪逆矩阵，将每次求解降为O(n²)的矩阵向量乘法。 - 对称性约简：棋盘具有旋转与镜像对称性，求解时可利用Burnside引理减少重复计算。
八、总结
本文通过Java完整实现了熄灯游戏的自动求解引擎，核心展示了三个算法层面：
- 状态压缩将二维棋盘压缩为位向量，使状态操作变为高效的位运算。
- GF(2)线性建模将游戏规则转化为模2线性方程组，揭示出看似随机的翻转行为背后的代数结构。
- 高斯消元与零空间枚举不仅能判定任意状态是否有解，还能在通解中找到点击次数最少的全局最优策略。
熄灯游戏是理解有限域上线性代数的绝佳入口，其求解思路也广泛应用于纠错码（LDPC解码）、密码学（线性反馈移位寄存器分析）与电路测试等领域。
