游戏简介
Lights Out（熄灯游戏）是一款经典的电子益智游戏，由Tiger Electronics于1995年推出。游戏板是一个5×5的方格，每个格子包含一盏灯，灯要么亮着要么熄灭。玩家点击任意一个格子时，该格子及其上下左右相邻格子的灯状态都会翻转（亮变灭、灭变亮）。游戏目标是在最少的点击次数内将所有灯熄灭。
本文用Java实现Lights Out求解器，重点讲解GF(2)域上的高斯消元算法以及状态空间分析。
核心算法设计
1. 游戏板与状态表示
Lights Out的核心是一个二进制状态向量：每个灯只有亮（1）和灭（0）两种状态。一个5×5的棋盘可以用25位二进制数表示，或用长度为25的布尔数组表示。
public class LightsOutSolver {
private static final int SIZE = 5; // 棋盘尺寸
private static final int N = SIZE * SIZE; // 总灯数
// 当前棋盘状态，true表示灯亮，false表示灯灭
private boolean[] board;
public LightsOutSolver() {
this.board = new boolean[N];
}
/**
* 从二维坐标(r,c)转换为一维索引
*/
private int idx(int r, int c) {
return r * SIZE + c;
}
/**
* 初始化随机棋盘状态
*/
public void randomizeBoard() {
Random rand = new Random();
for (int i = 0; i < N; i++) {
board[i] = rand.nextBoolean();
}
}
/**
* 设置指定位置的灯状态
*/
public void setLight(int r, int c, boolean on) {
board[idx(r, c)] = on;
}
/**
* 打印当前棋盘状态
*/
public void printBoard() {
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
System.out.print(board[idx(r, c)] ? "■ " : "□ ");
}
System.out.println();
}
System.out.println();
}
/**
* 检查是否所有灯都已熄灭
*/
public boolean isSolved() {
for (boolean b : board) {
if (b) return false;
}
return true;
}
}
2. 点击操作与状态翻转
点击一个格子会翻转该格子及其四个相邻格子的状态。在GF(2)域上，翻转等价于与1进行异或运算。
public class LightsOutSolver {
/**
* 点击指定位置，翻转该位置及其相邻位置的状态
* 在GF(2)中，翻转等价于 XOR 1
* @param r 行坐标
* @param c 列坐标
*/
public void press(int r, int c) {
// 翻转自身
board[idx(r, c)] ^= true;
// 翻转四个相邻方向
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] d : dirs) {
int nr = r + d[0];
int nc = c + d[1];
if (nr >= 0 && nr < SIZE && nc >= 0 && nc < SIZE) {
board[idx(nr, nc)] ^= true;
}
}
}
/**
* 获取点击(r,c)对所有灯的影响向量
* 返回长度为N的布尔数组，表示该操作会翻转哪些灯
*/
public boolean[] getPressEffect(int r, int c) {
boolean[] effect = new boolean[N];
effect[idx(r, c)] = true;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] d : dirs) {
int nr = r + d[0];
int nc = c + d[1];
if (nr >= 0 && nr < SIZE && nc >= 0 && nc < SIZE) {
effect[idx(nr, nc)] = true;
}
}
return effect;
}
}
3. GF(2)高斯消元求解
Lights Out的核心数学模型是：将25个可能的点击操作视为25个未知变量，每个灯的最终状态是若干个操作影响之和（在GF(2)中即异或）。这构成了一个在二元域GF(2)上的线性方程组，可以用高斯消元求解。
系数矩阵A的每一行代表一盏灯，每一列代表一个点击操作。A[i][j] = 1 表示点击第j个位置会影响第i盏灯。
public class LightsOutSolver {
/**
* 使用GF(2)高斯消元求解Lights Out
* @return 解向量，表示每个位置是否需要点击
*/
public boolean[] solve() {
// 构造增广矩阵：N行 × (N+1)列
// 前N列是系数矩阵，最后一列是初始状态（目标全0）
boolean[][] aug = new boolean[N][N + 1];
// 填充系数矩阵：aug[i][j] = 1 表示点击位置j会影响灯i
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
int col = idx(r, c); // 当前操作对应的列
boolean[] effect = getPressEffect(r, c);
for (int i = 0; i < N; i++) {
aug[i][col] = effect[i];
}
}
}
// 填充增广列：初始状态
for (int i = 0; i < N; i++) {
aug[i][N] = board[i];
}
// GF(2)高斯消元
int rank = gaussianEliminationGF2(aug);
// 检查是否有解（无矛盾方程）
for (int i = rank; i < N; i++) {
boolean allZero = true;
for (int j = 0; j < N; j++) {
if (aug[i][j]) {
allZero = false;
break;
}
}
if (allZero && aug[i][N]) {
return null; // 矛盾：0 = 1，无解
}
}
// 回代求解
boolean[] solution = new boolean[N];
for (int i = rank - 1; i >= 0; i--) {
// 找到主元列
int pivot = -1;
for (int j = 0; j < N; j++) {
if (aug[i][j]) {
pivot = j;
break;
}
}
if (pivot == -1) continue;
// 计算该变量的值：x_pivot = b_i XOR (sum of other variables)
boolean sum = aug[i][N];
for (int j = pivot + 1; j < N; j++) {
if (aug[i][j]) {
sum ^= solution[j];
}
}
solution[pivot] = sum;
}
return solution;
}
/**
* GF(2)域上的高斯消元，返回矩阵的秩
* 消元过程：用异或代替加减法
*/
private int gaussianEliminationGF2(boolean[][] aug) {
int row = 0;
for (int col = 0; col < N && row < N; col++) {
// 在当前列中寻找主元（值为1的行）
int pivotRow = -1;
for (int i = row; i < N; i++) {
if (aug[i][col]) {
pivotRow = i;
break;
}
}
if (pivotRow == -1) {
continue; // 该列没有主元，跳过
}
// 交换当前行与主元行
boolean[] temp = aug[row];
aug[row] = aug[pivotRow];
aug[pivotRow] = temp;
// 消去下方所有行的该列元素
for (int i = row + 1; i < N; i++) {
if (aug[i][col]) {
// 行i = 行i XOR 行row
for (int j = col; j <= N; j++) {
aug[i][j] ^= aug[row][j];
}
}
}
row++;
}
return row;
}
}
4. 寻找最少步数解
上述高斯消元找到的是一个特解。当方程组有自由变量时（即系数矩阵不满秩），可能存在多个解。我们需要在所有解中找到点击次数最少的一个。
对于5×5的Lights Out，系数矩阵的秩为23，存在2个自由变量，因此最多有4个解。我们可以通过枚举自由变量的所有组合来找到最优解。
public class LightsOutSolver {
/**
* 寻找最少点击次数的解
* @return 最优解向量，如果无解返回null
*/
public boolean[] solveMinClicks() {
// 先求一个特解
boolean[] particular = solve();
if (particular == null) return null;
// 对于5x5 Lights Out，矩阵秩为23，自由变量数为2
// 基础解系最多有 2^2 = 4 个解
// 这里简化处理：枚举所有可能的解空间
boolean[] bestSolution = particular;
int minClicks = countClicks(particular);
// 寻找零空间中的基向量
// 零空间向量z满足 A*z = 0 (mod 2)
// 即：执行z中的点击操作不会改变任何灯的状态
List<boolean[]> nullSpace = findNullSpace();
// 枚举零空间中所有向量的组合（2^k种）
int k = nullSpace.size();
for (int mask = 0; mask < (1 << k); mask++) {
boolean[] candidate = particular.clone();
for (int i = 0; i < k; i++) {
if ((mask & (1 << i)) != 0) {
// candidate = candidate XOR nullSpace[i]
for (int j = 0; j < N; j++) {
candidate[j] ^= nullSpace.get(i)[j];
}
}
}
int clicks = countClicks(candidate);
if (clicks < minClicks) {
minClicks = clicks;
bestSolution = candidate;
}
}
return bestSolution;
}
/**
* 计算解向量中的点击次数
*/
private int countClicks(boolean[] solution) {
int count = 0;
for (boolean b : solution) {
if (b) count++;
}
return count;
}
/**
* 寻找系数矩阵的零空间基向量
* 通过高斯消元的行最简形来确定自由变量
*/
private List<boolean[]> findNullSpace() {
List<boolean[]> basis = new ArrayList<>();
// 构造系数矩阵
boolean[][] A = new boolean[N][N];
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
int col = idx(r, c);
boolean[] effect = getPressEffect(r, c);
for (int i = 0; i < N; i++) {
A[i][col] = effect[i];
}
}
}
// 高斯消元得到行最简形
int[] where = new int[N]; // where[col] = 该列主元所在的行，-1表示自由变量
Arrays.fill(where, -1);
int row = 0;
for (int col = 0; col < N && row < N; col++) {
int sel = -1;
for (int i = row; i < N; i++) {
if (A[i][col]) {
sel = i;
break;
}
}
if (sel == -1) continue;
boolean[] tmp = A[sel];
A[sel] = A[row];
A[row] = tmp;
where[col] = row;
for (int i = 0; i < N; i++) {
if (i != row && A[i][col]) {
for (int j = col; j < N; j++) {
A[i][j] ^= A[row][j];
}
}
}
row++;
}
// 对于每个自由变量，构造一个零空间基向量
for (int freeVar = 0; freeVar < N; freeVar++) {
if (where[freeVar] == -1) {
boolean[] vec = new boolean[N];
vec[freeVar] = true;
for (int col = 0; col < N; col++) {
if (where[col] != -1 && A[where[col]][freeVar]) {
vec[col] = true;
}
}
basis.add(vec);
}
}
return basis;
}
}
5. 交互式游戏与验证
public class LightsOutSolver {
/**
* 应用求解结果到当前棋盘，验证是否全部熄灭
* @param solution 解向量
* @return 是否成功求解
*/
public boolean applySolution(boolean[] solution) {
if (solution == null) return false;
System.out.println("应用求解方案...");
for (int i = 0; i < N; i++) {
if (solution[i]) {
int r = i / SIZE;
int c = i % SIZE;
press(r, c);
System.out.println("点击 (" + r + "," + c + ")");
}
}
return isSolved();
}
public static void main(String[] args) {
LightsOutSolver game = new LightsOutSolver();
System.out.println("=== Lights Out 熄灯游戏求解器 ===");
System.out.println("初始状态：");
game.randomizeBoard();
game.printBoard();
boolean[] solution = game.solveMinClicks();
if (solution == null) {
System.out.println("该状态无解！");
return;
}
int clicks = 0;
for (boolean b : solution) if (b) clicks++;
System.out.println("最少需要点击 " + clicks + " 次");
boolean solved = game.applySolution(solution);
System.out.println("最终状态：");
game.printBoard();
System.out.println("求解" + (solved ? "成功" : "失败"));
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 构造系数矩阵 | O(N²) | O(N²) |
| GF(2)高斯消元 | O(N³) | O(N²) |
| 寻找零空间 | O(N³) | O(N²) |
| 枚举最优解 | O(2^k × N)，k为自由变量数 | O(N) |
| 整体求解 | O(N³) | O(N²) |
对于5×5棋盘（N=25），N³=15625，计算量极小，可瞬间完成求解。
扩展方向
- 变体规则：支持”点击翻转对角线邻居”或”点击翻转整行整列”的变体规则，只需修改系数矩阵的构造方式。
- 更大棋盘：8×8或N×M棋盘同样适用高斯消元，但时间复杂度变为O((NM)³)。
- 逆向问题：给定目标图案（如爱心形状），求解需要什么样的初始状态才能通过点击达到该图案。
小结
Lights Out熄灯游戏看似是一个需要穷举的谜题，但其本质是一个在GF(2)域上的线性方程组。通过高斯消元，我们可以在O(N³)时间内精确求解任意初始状态，而不需要任何启发式搜索。这一思想可以推广到所有”翻转类”谜题：只要翻转规则是线性的（即翻转两次等于不翻转），就可以用同样的线性代数框架求解。
