一、游戏介绍与算法目标
点灯游戏（Lights Out）是1995年Tiger Electronics推出的经典电子谜题。在一个5×5的方格中，每个格子代表一盏灯，点击某格会翻转该格及其上下左右相邻格子的开关状态。目标是将所有灯熄灭。
本文用Java实现点灯游戏求解器，核心算法包括：
- 异或线性方程组建模：将游戏状态转化为模2线性方程组
- 高斯消元法：在GF(2)域上求解线性方程组
- 解空间分析：判定有解性、唯一解与多解情况
二、数学建模
2.1 状态向量
将5×5的25个格子按行优先展开为25维向量，每个分量取值为0（灭）或1（亮）。整个游戏状态就是 Z₂²⁵ 中的一个向量。
2.2 操作矩阵
设 x 为25维点击向量（xᵢ = 1表示点击第i格），b 为初始状态向量。我们需要找到 x 使得：
A · x = b (mod 2)
其中 A 是25×25的邻接影响矩阵：
– A[i][i] = 1（点击自己会翻转自己）
– A[i][j] = 1 当且仅当格子i与格子j相邻（上下左右）
2.3 高斯消元在GF(2)上
普通高斯消元在实数域进行，而点灯游戏需要在模2域（GF(2)）上运算：
– 加法变异或（XOR）
– 乘法变与（AND）
– 没有除法，因为1的逆元是1
三、完整Java实现
import java.util.*;
/**
* 点灯游戏（Lights Out）求解器
* 使用GF(2)域上的高斯消元求解异或线性方程组
*/
public class LightsOutSolver {
private final int rows;
private final int cols;
private final int n; // 总格子数 = rows * cols
private final int[][] A; // 影响矩阵（增广矩阵形式）
public LightsOutSolver(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.n = rows * cols;
this.A = new int[n][n + 1]; // 增广矩阵，最后一列是初始状态
buildMatrix();
}
/** 构建邻接影响矩阵 */
private void buildMatrix() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int idx = r * cols + c;
// 点击自己
A[idx][idx] = 1;
// 上
if (r > 0) A[idx][(r - 1) * cols + c] = 1;
// 下
if (r < rows - 1) A[idx][(r + 1) * cols + c] = 1;
// 左
if (c > 0) A[idx][r * cols + (c - 1)] = 1;
// 右
if (c < cols - 1) A[idx][r * cols + (c + 1)] = 1;
}
}
}
/**
* 求解点灯游戏
* @param board 初始棋盘状态，1表示亮，0表示灭
* @return 点击方案，null表示无解
*/
public int[] solve(int[][] board) {
// 将棋盘状态填入增广矩阵最后一列
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
A[r * cols + c][n] = board[r][c] & 1;
}
}
// 复制矩阵用于消元（避免修改原始矩阵）
int[][] M = new int[n][n + 1];
for (int i = 0; i < n; i++) {
System.arraycopy(A[i], 0, M[i], 0, n + 1);
}
int[] where = new int[n]; // where[col] = 该列主元所在的行
Arrays.fill(where, -1);
// 高斯消元（GF(2)域）
int row = 0;
for (int col = 0; col < n && row < n; col++) {
// 寻找该列中值为1的主元行
int pivot = -1;
for (int i = row; i < n; i++) {
if (M[i][col] == 1) {
pivot = i;
break;
}
}
if (pivot == -1) continue; // 该列没有主元，是自由变量
// 交换当前行与主元行
int[] temp = M[row];
M[row] = M[pivot];
M[pivot] = temp;
where[col] = row;
// 消去其他行在该列的1（GF(2)：1+1=0，直接异或）
for (int i = 0; i < n; i++) {
if (i != row && M[i][col] == 1) {
// 整行异或
for (int j = col; j <= n; j++) {
M[i][j] ^= M[row][j];
}
}
}
row++;
}
// 提取解
int[] solution = new int[n];
Arrays.fill(solution, 0);
// 回代求解
for (int i = n - 1; i >= 0; i--) {
if (where[i] != -1) {
solution[i] = M[where[i]][n];
// 该行其他已知变量贡献
for (int j = i + 1; j < n; j++) {
if (M[where[i]][j] == 1 && solution[j] == 1) {
solution[i] ^= 1;
}
}
}
}
// 验证解：检查是否存在矛盾方程 0 = 1
for (int i = 0; i < n; i++) {
boolean allZero = true;
for (int j = 0; j < n; j++) {
if (M[i][j] == 1) {
allZero = false;
break;
}
}
if (allZero && M[i][n] == 1) {
return null; // 矛盾：0 = 1，无解
}
}
// 验证解的正确性
if (!verifySolution(board, solution)) {
return null;
}
return solution;
}
/** 验证解是否正确 */
private boolean verifySolution(int[][] board, int[] solution) {
int[][] result = new int[rows][cols];
for (int r = 0; r < rows; r++) {
System.arraycopy(board[r], 0, result[r], 0, cols);
}
// 模拟点击
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (solution[r * cols + c] == 1) {
toggle(result, r, c);
}
}
}
// 检查是否全灭
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (result[r][c] != 0) return false;
}
}
return true;
}
/** 翻转指定格子及其邻居 */
private void toggle(int[][] board, int r, int c) {
board[r][c] ^= 1;
if (r > 0) board[r - 1][c] ^= 1;
if (r < rows - 1) board[r + 1][c] ^= 1;
if (c > 0) board[r][c - 1] ^= 1;
if (c < cols - 1) board[r][c + 1] ^= 1;
}
/**
* 寻找最少点击次数的解
* 当解不唯一时，在所有自由变量组合中寻找点击次数最少的解
*/
public int[] solveMinClicks(int[][] board) {
int[] baseSolution = solve(board);
if (baseSolution == null) return null;
// 构建完整增广矩阵并化为行阶梯形
int[][] M = new int[n][n + 1];
for (int i = 0; i < n; i++) {
System.arraycopy(A[i], 0, M[i], 0, n);
M[i][n] = board[i / cols][i % cols];
}
// 高斯消元
int rank = 0;
int[] where = new int[n];
Arrays.fill(where, -1);
for (int col = 0; col < n && rank < n; col++) {
int pivot = -1;
for (int i = rank; i < n; i++) {
if (M[i][col] == 1) {
pivot = i;
break;
}
}
if (pivot == -1) continue;
int[] tmp = M[rank];
M[rank] = M[pivot];
M[pivot] = tmp;
where[col] = rank;
for (int i = 0; i < n; i++) {
if (i != rank && M[i][col] == 1) {
for (int j = col; j <= n; j++) {
M[i][j] ^= M[rank][j];
}
}
}
rank++;
}
// 统计自由变量
List<Integer> freeVars = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (where[i] == -1) freeVars.add(i);
}
// 若自由变量太多（>20），用贪心近似
if (freeVars.size() > 20) {
return baseSolution;
}
// 枚举所有自由变量组合，寻找最少点击解
int[] bestSolution = baseSolution.clone();
int minClicks = countOnes(bestSolution);
int freeCount = freeVars.size();
for (int mask = 0; mask < (1 << freeCount); mask++) {
int[] candidate = new int[n];
// 从行阶梯形提取特解
for (int i = 0; i < n; i++) {
if (where[i] != -1) {
candidate[i] = M[where[i]][n];
}
}
// 设置自由变量
for (int f = 0; f < freeCount; f++) {
if ((mask & (1 << f)) != 0) {
int varIdx = freeVars.get(f);
candidate[varIdx] = 1;
}
}
// 回代计算主元变量
for (int i = n - 1; i >= 0; i--) {
if (where[i] != -1) {
int rowIdx = where[i];
for (int j = i + 1; j < n; j++) {
if (M[rowIdx][j] == 1 && candidate[j] == 1) {
candidate[i] ^= 1;
}
}
}
}
int clicks = countOnes(candidate);
if (clicks < minClicks) {
minClicks = clicks;
bestSolution = candidate.clone();
}
}
return bestSolution;
}
private int countOnes(int[] arr) {
int count = 0;
for (int v : arr) count += v;
return count;
}
/** 打印棋盘 */
public void printBoard(int[][] board) {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
System.out.print(board[r][c] == 1 ? "■ " : "□ ");
}
System.out.println();
}
}
/** 打印点击方案 */
public void printSolution(int[] solution) {
if (solution == null) {
System.out.println("无解！");
return;
}
System.out.println("点击方案（■=点击，□=不点）：");
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
System.out.print(solution[r * cols + c] == 1 ? "■ " : "□ ");
}
System.out.println();
}
System.out.println("总点击次数: " + countOnes(solution));
}
/** 测试主程序 */
public static void main(String[] args) {
LightsOutSolver solver = new LightsOutSolver(5, 5);
// 测试1：经典5×5全亮开局
System.out.println("=== 测试1：5×5全亮开局 ===");
int[][] board1 = new int[5][5];
for (int[] row : board1) Arrays.fill(row, 1);
System.out.println("初始状态：");
solver.printBoard(board1);
int[] sol1 = solver.solveMinClicks(board1);
solver.printSolution(sol1);
// 测试2：随机开局
System.out.println("\n=== 测试2：随机开局 ===");
Random rand = new Random(42);
int[][] board2 = new int[5][5];
for (int r = 0; r < 5; r++) {
for (int c = 0; c < 5; c++) {
board2[r][c] = rand.nextInt(2);
}
}
System.out.println("初始状态：");
solver.printBoard(board2);
int[] sol2 = solver.solveMinClicks(board2);
solver.printSolution(sol2);
// 测试3：3×3小棋盘
System.out.println("\n=== 测试3：3×3棋盘 ===");
LightsOutSolver solver3 = new LightsOutSolver(3, 3);
int[][] board3 = {{1, 0, 1}, {0, 1, 0}, {1, 0, 1}};
System.out.println("初始状态：");
solver3.printBoard(board3);
int[] sol3 = solver3.solveMinClicks(board3);
solver3.printSolution(sol3);
}
}
四、算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 矩阵构建 | O(n²) | O(n²) |
| 高斯消元 | O(n³) | O(n²) |
| 解验证 | O(n) | O(n) |
| 最少点击枚举 | O(2^k · n²) | O(n²) |
对于标准5×5棋盘，n=25，高斯消元仅需约25³ = 15625次位运算，现代CPU瞬间完成。
五、数学性质
5.1 5×5棋盘的秩
5×5点灯游戏的影响矩阵 A 的秩为23，零空间维数为2。这意味着：
– 任意初始状态要么无解，要么有4个解（2² = 4）
– 存在 “零操作”：某些点击组合不会改变任何灯的状态
5.2 有解性判定
方程组 Ax = b 有解的充要条件是 b 与 A 的左零空间正交。对于对称矩阵A，等价于 b 属于A的列空间。
六、扩展方向
- 变体规则：支持对角线翻转（8邻域）、仅翻转邻居不翻转自己等规则变体
- 多颜色版本：将二元状态扩展为k色循环（如三色循环点灯）
- 最小步数证明：利用线性代数证明某些初始状态的最优解步数下界
- 交互式求解器：结合Swing/JavaFX实现可视化界面，实时显示消元过程
