引言
点灯游戏（Lights Out）是一款经典的电子益智游戏。玩家面对一个由灯泡组成的矩阵，每次点击一个灯泡，该灯泡及其上下左右的相邻灯泡都会切换状态（亮变暗、暗变亮）。目标是将所有灯泡熄灭。
看似简单的游戏规则背后，隐藏着深刻的线性代数结构。本文将用Java实现点灯游戏的求解器，揭示其核心算法——在GF(2)（二元域）上的高斯消元法。
游戏规则与数学建模
游戏规则
- 棋盘为 $N \times M$ 的方格，每个格子有一盏灯
- 初始状态随机，部分灯亮（1）、部分灯暗（0）
- 点击一个格子，该格子及其四邻域的灯状态翻转
- 目标：所有灯熄灭（全0）
数学模型
将棋盘按行优先展开为一个长度为 $N \times M$ 的向量 $\mathbf{x}$，每个元素取值为0或1。设点击操作向量也为 $\mathbf{c}$（$c_i=1$ 表示点击第 $i$ 个格子）。
每个格子的最终状态等于初始状态加上（模2）所有影响它的点击操作之和。这可以表示为线性方程组：
$$A \cdot \mathbf{c} = \mathbf{b} \pmod{2}$$
其中：
– $A$ 是 $(N \times M) \times (N \times M)$ 的系数矩阵，$A_{ij} = 1$ 当且仅当点击第 $j$ 个格子会影响第 $i$ 个格子的状态
– $\mathbf{b}$ 是初始状态向量（目标为全0，所以右边就是初始状态）
– 所有运算在GF(2)上进行，即加法等价于异或（XOR）
核心算法：GF(2)上的高斯消元
GF(2)是只包含两个元素 ${0, 1}$ 的有限域，其加法和乘法定义如下：
– 加法：$0+0=0$, $0+1=1$, $1+0=1$, $1+1=0$（即异或）
– 乘法：与常规乘法相同
高斯消元在GF(2)上的实现与普通高斯消元类似，但所有加减法替换为异或运算。
Java实现
项目结构
lights-out-solver/
├── src/
│ └── com/
│ └── lightsout/
│ ├── LightsOutSolver.java // 求解器核心
│ ├── GFM2Matrix.java // GF(2)矩阵操作
│ ├── LightsOutGame.java // 游戏交互界面
│ └── Main.java // 入口
GF(2)矩阵类
package com.lightsout;
import java.util.Arrays;
/**
* GF(2)上的矩阵，所有运算在模2下进行
*/
public class GFM2Matrix {
private final int rows;
private final int cols;
private final int[][] data; // 每个元素为0或1
public GFM2Matrix(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.data = new int[rows][cols];
}
public void set(int row, int col, int value) {
data[row][col] = value & 1;
}
public int get(int row, int col) {
return data[row][col];
}
public int getRows() { return rows; }
public int getCols() { return cols; }
/**
* 高斯消元：将矩阵化为行阶梯形
* @return 矩阵的秩
*/
public int gaussianElimination() {
int rank = 0;
for (int col = 0; col < cols && rank < rows; col++) {
// 寻找主元：在第col列中从第rank行开始找第一个1
int pivot = -1;
for (int row = rank; row < rows; row++) {
if (data[row][col] == 1) {
pivot = row;
break;
}
}
if (pivot == -1) continue; // 该列没有主元
// 交换当前行与主元行
if (pivot != rank) {
int[] temp = data[rank];
data[rank] = data[pivot];
data[pivot] = temp;
}
// 消去其他行在该列的1（GF(2)中减法等于加法等于异或）
for (int row = 0; row < rows; row++) {
if (row != rank && data[row][col] == 1) {
// row = row XOR rank
for (int c = col; c < cols; c++) {
data[row][c] ^= data[rank][c];
}
}
}
rank++;
}
return rank;
}
/**
* 高斯消元并求解增广矩阵
* @return 是否有解
*/
public boolean solve() {
gaussianElimination();
// 检查是否有矛盾行：[0 0 ... 0 | 1]
for (int row = 0; row < rows; row++) {
boolean allZero = true;
for (int col = 0; col < cols - 1; col++) {
if (data[row][col] == 1) {
allZero = false;
break;
}
}
if (allZero && data[row][cols - 1] == 1) {
return false; // 矛盾：0 = 1
}
}
return true;
}
/**
* 提取解向量（假设最后一列为常数项）
*/
public int[] extractSolution() {
int[] solution = new int[cols - 1];
Arrays.fill(solution, 0);
// 从行阶梯形回代
for (int row = rows - 1; row >= 0; row--) {
// 找到该行的主元列
int pivotCol = -1;
for (int col = 0; col < cols - 1; col++) {
if (data[row][col] == 1) {
pivotCol = col;
break;
}
}
if (pivotCol == -1) continue;
// 计算该变量的值
int sum = data[row][cols - 1];
for (int col = pivotCol + 1; col < cols - 1; col++) {
if (data[row][col] == 1) {
sum ^= solution[col];
}
}
solution[pivotCol] = sum;
}
return solution;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int[] row : data) {
sb.append(Arrays.toString(row)).append("\n");
}
return sb.toString();
}
}
点灯游戏求解器
package com.lightsout;
import java.util.ArrayList;
import java.util.List;
/**
* 点灯游戏求解器
* 利用GF(2)上的高斯消元求解线性方程组
*/
public class LightsOutSolver {
private final int rows;
private final int cols;
private final int n; // 总格子数
public LightsOutSolver(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.n = rows * cols;
}
/**
* 将二维坐标转换为一维索引
*/
private int idx(int r, int c) {
return r * cols + c;
}
/**
* 构建系数矩阵A和增广矩阵[A|b]
* @param initialState 初始状态，二维数组，0=暗，1=亮
* @return 增广矩阵
*/
public GFM2Matrix buildAugmentedMatrix(int[][] initialState) {
// 增广矩阵为 n x (n+1)，前n列为系数，最后一列为常数项
GFM2Matrix matrix = new GFM2Matrix(n, n + 1);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int rowIdx = idx(i, j);
// 设置常数项（初始状态）
matrix.set(rowIdx, n, initialState[i][j]);
// 设置系数：点击每个格子对当前格子的影响
// 点击自己
matrix.set(rowIdx, idx(i, j), 1);
// 点击上邻居
if (i > 0) matrix.set(rowIdx, idx(i - 1, j), 1);
// 点击下邻居
if (i < rows - 1) matrix.set(rowIdx, idx(i + 1, j), 1);
// 点击左邻居
if (j > 0) matrix.set(rowIdx, idx(i, j - 1), 1);
// 点击右邻居
if (j < cols - 1) matrix.set(rowIdx, idx(i, j + 1), 1);
}
}
return matrix;
}
/**
* 求解点灯游戏
* @param initialState 初始状态
* @return 点击方案，如果无解返回null
*/
public int[][] solve(int[][] initialState) {
GFM2Matrix augMatrix = buildAugmentedMatrix(initialState);
if (!augMatrix.solve()) {
return null; // 无解
}
int[] solution = augMatrix.extractSolution();
// 转换回二维
int[][] clicks = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
clicks[i][j] = solution[idx(i, j)];
}
}
return clicks;
}
/**
* 获取所有解（当矩阵不满秩时，可能存在多解）
*/
public List<int[][]> solveAll(int[][] initialState) {
List<int[][]> allSolutions = new ArrayList<>();
// 先找到一个特解
int[][] particular = solve(initialState);
if (particular == null) return allSolutions;
allSolutions.add(particular);
// 找到零空间的一组基
// 对于简化版实现，这里只返回一个解
// 完整实现需要计算零空间的所有基向量
return allSolutions;
}
/**
* 验证解的正确性
*/
public boolean verify(int[][] initialState, int[][] clicks) {
int[][] state = new int[rows][cols];
for (int i = 0; i < rows; i++) {
System.arraycopy(initialState[i], 0, state[i], 0, cols);
}
// 应用所有点击操作
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (clicks[i][j] == 1) {
// 翻转自己和邻居
state[i][j] ^= 1;
if (i > 0) state[i - 1][j] ^= 1;
if (i < rows - 1) state[i + 1][j] ^= 1;
if (j > 0) state[i][j - 1] ^= 1;
if (j < cols - 1) state[i][j + 1] ^= 1;
}
}
}
// 检查是否全灭
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (state[i][j] != 0) return false;
}
}
return true;
}
}
游戏主类与演示
package com.lightsout;
/**
* 点灯游戏演示入口
*/
public class Main {
public static void main(String[] args) {
// 5x5 点灯游戏
int rows = 5;
int cols = 5;
// 构造一个初始状态（手动设置或随机生成）
int[][] initialState = {
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 0},
{1, 0, 0, 0, 1},
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 1}
};
System.out.println("=== 点灯游戏求解器 ===");
System.out.println("初始状态：");
printBoard(initialState);
LightsOutSolver solver = new LightsOutSolver(rows, cols);
int[][] solution = solver.solve(initialState);
if (solution != null) {
System.out.println("\n求解成功！点击方案（1=点击，0=不点击）：");
printBoard(solution);
// 验证
boolean valid = solver.verify(initialState, solution);
System.out.println("\n验证结果：" + (valid ? "通过" : "失败"));
// 统计点击次数
int clickCount = 0;
for (int[] row : solution) {
for (int val : row) {
clickCount += val;
}
}
System.out.println("最少点击次数：" + clickCount);
} else {
System.out.println("\n该初始状态无解！");
}
}
private static void printBoard(int[][] board) {
for (int[] row : board) {
for (int val : row) {
System.out.print(val == 1 ? "■ " : "□ ");
}
System.out.println();
}
}
}
算法复杂度分析
时间复杂度
高斯消元的时间复杂度为 $O(n^3)$，其中 $n = rows \times cols$ 是格子总数。
- 构建矩阵：$O(n)$
- 高斯消元：$O(n^3)$
- 回代求解：$O(n^2)$
对于常见的 $5 \times 5$ 棋盘，$n = 25$，运算量极小。即使是 $10 \times 10$ 的棋盘，$n = 100$，也能瞬间求解。
空间复杂度
增广矩阵需要 $O(n^2)$ 的空间存储。对于 $N \times M$ 棋盘，空间复杂度为 $O((NM)^2)$。
扩展与思考
1. 多解情况
当系数矩阵 $A$ 不满秩时，方程组可能存在多解或无解。对于标准点灯游戏：
– $N \times N$ 棋盘当 $N$ 被3整除时，矩阵通常不满秩
– 这时可以寻找点击次数最少的解（通过枚举零空间的基向量组合）
2. 变种规则
- 对角线影响：点击同时影响对角线邻居，修改系数矩阵即可
- 环形边界：上下左右连通（环面），需要修改邻居计算逻辑
- 多状态灯：三态或更多状态，需要将GF(2)扩展为GF(p)
3. 最少步数求解
当存在多解时，可以转化为一个优化问题：在解空间中寻找汉明重量最小的解。这可以通过在高斯消元后枚举自由变量实现。
总结
点灯游戏是有限域上线性代数的完美应用实例。通过将游戏状态建模为GF(2)上的向量、将点击操作建模为线性变换，我们成功地将一个看似需要穷举的搜索问题转化为高效的线性方程组求解问题。这种数学建模思想在密码学、纠错码、电路设计等领域都有广泛应用。
