引言
关灯游戏（Lights Out）是一款经典的电子益智游戏：玩家面对一个 $5 \times 5$ 的灯阵，每次按下一个开关会翻转该灯及其上下左右邻灯的状态。目标是将所有灯关闭。看似简单的规则背后，隐藏着深刻的线性代数结构——整个游戏可以建模为 $GF(2)$ 域上的线性方程组，用高斯消元法在多项式时间内求解。本文将用Java实现关灯游戏的求解器，并深入讲解最少步数求解策略。
核心算法原理
1. 问题建模为GF(2)线性方程组
将 $5 \times 5$ 的灯阵展平为25维向量 $x$，每个分量代表是否按下对应开关（1=按，0=不按）。灯的最终状态由按下开关的集合决定：
$$
Ax = b \pmod 2
$$
其中：
– $A$ 是 $25 \times 25$ 的影响矩阵：$A_{ij}=1$ 表示按下开关 $j$ 会影响灯 $i$
– $b$ 是初始状态向量（1=亮，0=灭）
– 所有运算在 $GF(2)$ 上进行（加法是异或，乘法是逻辑与）
2. 高斯消元在GF(2)上的实现
与实数域高斯消元的区别仅在于：
– 加减法替换为异或（XOR）
– 无需选主元（系数只有0和1）
– 回代过程同样使用异或
3. 最少步数求解
高斯消元得到一个特解。若解空间的维数为 $d$，则共有 $2^d$ 个解。枚举所有解并选择1的个数最少的向量，即为最少步数解。
Java完整实现
package lightsout;
import java.util.*;
/**
* 关灯游戏求解器
* 核心算法：GF(2)域高斯消元 + 解空间枚举找最少步数
*/
public class LightsOutSolver {
private static final int N = 5; // 网格大小
private static final int SIZE = N * N; // 25个灯/开关
private int[][] matrix; // 增广矩阵 [SIZE][SIZE+1]
private int rank;
private List<Integer> freeVars; // 自由变量索引
public LightsOutSolver() {
buildInfluenceMatrix();
}
/**
* 构建影响矩阵A：按下开关(i,j)会影响(i,j)及其四邻域
* 矩阵A[i][j]=1 表示开关j会影响灯i的状态
*/
private void buildInfluenceMatrix() {
matrix = new int[SIZE][SIZE + 1]; // 最后一列是增广部分
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
int switchIdx = r * N + c; // 当前开关编号
// 该开关影响的灯：自身 + 上下左右
int[][] dirs = {{0,0}, {-1,0}, {1,0}, {0,-1}, {0,1}};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
int lightIdx = nr * N + nc;
matrix[lightIdx][switchIdx] = 1;
}
}
}
}
}
/**
* 求解关灯问题
* @param initialBoard 初始灯状态，1=亮，0=灭
* @return 最少步数解，若无可行解返回null
*/
public int[] solve(int[] initialBoard) {
// 设置增广矩阵的右端项
for (int i = 0; i < SIZE; i++) {
matrix[i][SIZE] = initialBoard[i];
}
// 高斯消元
gaussElimination();
// 检查是否有解
if (!hasSolution()) {
return null;
}
// 找最少步数解
return findMinimumStepsSolution();
}
/**
* GF(2)域上的高斯消元
* 核心：加减法变为异或，无需乘法逆元
*/
private void gaussElimination() {
rank = 0;
freeVars = new ArrayList<>();
int[] where = new int[SIZE];
Arrays.fill(where, -1);
for (int col = 0, row = 0; col < SIZE && row < SIZE; col++) {
// 找主元：该列中第一个值为1的行
int pivot = row;
while (pivot < SIZE && matrix[pivot][col] == 0) pivot++;
if (pivot == SIZE) {
freeVars.add(col); // 自由变量
continue;
}
// 交换当前行与主元行
swapRows(row, pivot);
where[col] = row;
// 消去其他行的该列（GF(2)中用异或）
for (int i = 0; i < SIZE; i++) {
if (i != row && matrix[i][col] == 1) {
for (int j = col; j <= SIZE; j++) {
matrix[i][j] ^= matrix[row][j];
}
}
}
row++;
rank++;
}
}
private void swapRows(int i, int j) {
int[] temp = matrix[i];
matrix[i] = matrix[j];
matrix[j] = temp;
}
/**
* 检查方程组是否有解
* 若存在某行系数全0但右端项为1，则无解
*/
private boolean hasSolution() {
for (int i = rank; i < SIZE; i++) {
boolean allZero = true;
for (int j = 0; j < SIZE; j++) {
if (matrix[i][j] != 0) { allZero = false; break; }
}
if (allZero && matrix[i][SIZE] == 1) return false;
}
return true;
}
/**
* 枚举解空间找最少步数解
* 解空间维度 d = |freeVars|，共 2^d 个解
*/
private int[] findMinimumStepsSolution() {
int d = freeVars.size();
int[] bestSolution = null;
int minSteps = Integer.MAX_VALUE;
// 枚举所有 2^d 种自由变量赋值
for (int mask = 0; mask < (1 << d); mask++) {
int[] solution = new int[SIZE];
// 设置自由变量
for (int i = 0; i < d; i++) {
solution[freeVars.get(i)] = (mask >> i) & 1;
}
// 回代求主元变量
for (int col = SIZE - 1; col >= 0; col--) {
int row = findPivotRow(col);
if (row >= 0) {
int sum = matrix[row][SIZE];
for (int j = col + 1; j < SIZE; j++) {
if (matrix[row][j] == 1) sum ^= solution[j];
}
solution[col] = sum;
}
}
// 统计步数
int steps = 0;
for (int v : solution) steps += v;
if (steps < minSteps) {
minSteps = steps;
bestSolution = solution.clone();
}
}
return bestSolution;
}
private int findPivotRow(int col) {
for (int i = 0; i < rank; i++) {
if (matrix[i][col] == 1) {
// 确认这是该行的首个1
boolean first = true;
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 1) { first = false; break; }
}
if (first) return i;
}
}
return -1;
}
/**
* 可视化打印棋盘状态
*/
public static void printBoard(int[] board) {
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
System.out.print(board[r * N + c] == 1 ? "■ " : "□ ");
}
System.out.println();
}
}
/**
* 模拟按下指定开关后的效果
*/
public static int[] press(int[] board, int row, int col) {
int[] next = board.clone();
int[][] dirs = {{0,0}, {-1,0}, {1,0}, {0,-1}, {0,1}};
for (int[] d : dirs) {
int nr = row + d[0], nc = col + d[1];
if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
next[nr * N + nc] ^= 1;
}
}
return next;
}
public static void main(String[] args) {
LightsOutSolver solver = new LightsOutSolver();
// 测试：随机生成初始状态
Random rand = new Random();
int[] initial = new int[SIZE];
for (int i = 0; i < SIZE; i++) initial[i] = rand.nextInt(2);
System.out.println("初始状态：");
printBoard(initial);
int[] solution = solver.solve(initial);
if (solution == null) {
System.out.println("该初始状态无解！");
return;
}
System.out.println("\n最少步数解（■=按下该开关）：");
printBoard(solution);
// 验证解的正确性
int[] verify = initial.clone();
for (int i = 0; i < SIZE; i++) {
if (solution[i] == 1) {
verify = press(verify, i / N, i % N);
}
}
System.out.println("\n验证（应全灭）：");
printBoard(verify);
int steps = 0;
for (int v : solution) steps += v;
System.out.println("最少步数：" + steps);
}
}
复杂度分析
| 步骤 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 构建影响矩阵 | $O(N^2)$ | $O(N^4)$ |
| GF(2)高斯消元 | $O(N^6)$ | $O(N^4)$ |
| 解空间枚举 | $O(2^d \cdot N^2)$ | $O(N^2)$ |
| 整体（$N=5$） | 实际 $<1$ms | 可忽略 |
对于 $5 \times 5$ 标准板，矩阵秩为23，解空间维度 $d=2$，仅需枚举4个解即可找到最少步数。
扩展思考
- 变体板型：$N \times N$ 或 $M \times N$ 矩形板只需修改
N常量，算法完全通用 - 邻域变体：若增加对角线影响，只需修改
buildInfluenceMatrix中的方向数组 - 最少步数上界：已证明任意 $5 \times 5$ 可解状态最多需15步即可关闭所有灯
总结
关灯游戏是理解线性代数在游戏求解中应用的绝佳案例。GF(2)域上的高斯消元将看似需要指数级搜索的问题转化为多项式时间可解的线性系统，展示了抽象代数在算法设计中的强大威力。
