问题引入
电路谜题是一类经典的逻辑益智游戏：有 n 盏灯排成一排，每盏灯对应一个开关，但开关与灯之间并非一一对应——按下一个开关可能同时翻转多盏灯的状态。目标是找到按动哪些开关，能让所有灯从初始状态变为全部点亮，且按动次数最少。本文用Java实现两种核心解法：小规模下的二进制枚举，以及大规模下的模2高斯消元。
算法原理
问题建模
将灯的状态用 0（灭）和 1（亮）表示，按开关的操作等价于异或运算。设开关 i 对灯 j 的影响为 a[i][j]（1 表示翻转，0 表示无影响），则问题转化为求解异或线性方程组：
x[0]·a[0][j] ⊕ x[1]·a[1][j] ⊕ ... ⊕ x[n-1]·a[n-1][j] = b[j]
其中 x[i] 表示是否按下开关 i，b[j] 表示灯 j 的目标状态（与初始状态异或后的需求）。
方法一：二进制枚举
当 n ≤ 20 时，可用位掩码枚举所有 2^n 种开关组合，验证是否满足所有灯的状态要求。枚举时可用位运算加速状态计算。
方法二：模2高斯消元
将方程组视为在 GF(2)（二元域）上的线性方程组，使用高斯消元求解。与普通高斯消元的区别在于：加减法均变为异或运算，无需乘除法。
消元完成后，若存在自由变量，则可通过枚举自由变量的所有组合，找出使按下开关数最少的最优解。
Java完整实现
import java.util.Arrays;
/**
* 电路谜题求解器：二进制枚举 + 模2高斯消元
* 目标：找到最少开关组合使所有灯点亮
*/
public class CircuitPuzzle {
/**
* 方法一：二进制枚举（适用于 n <= 20 的小规模问题）
* @param n 灯/开关数量
* @param effect effect[i] 是一个位掩码，表示开关i影响哪些灯
* @param init 初始灯状态（位掩码，1表示灭需要被翻转）
* @return 最少按动次数，无解返回-1
*/
public int solveByEnumeration(int n, int[] effect, int init) {
int target = (1 << n) - 1; // 所有灯都亮（所有位为1）
int minPresses = Integer.MAX_VALUE;
int bestMask = -1;
// 枚举所有 2^n 种开关组合
for (int mask = 0; mask < (1 << n); mask++) {
int state = init;
int presses = Integer.bitCount(mask);
// 应用选中的开关
for (int i = 0; i < n; i++) {
if ((mask >> i & 1) == 1) {
state ^= effect[i];
}
}
// 检查是否所有灯都亮
if (state == target && presses < minPresses) {
minPresses = presses;
bestMask = mask;
}
}
return minPresses == Integer.MAX_VALUE ? -1 : minPresses;
}
/**
* 方法二：模2高斯消元（适用于 n 较大的情况）
* @param a 增广矩阵，a[i][j]表示开关j对灯i的影响，最后一列是目标状态
* @return 最少按动次数，无解返回-1
*/
public int solveByGauss(int[][] a) {
int n = a.length; // 方程数（灯数）
int m = a[0].length - 1; // 变量数（开关数）
int row = 0;
int[] where = new int[m];
Arrays.fill(where, -1);
// 高斯消元主过程
for (int col = 0; col < m && row < n; col++) {
// 找当前列中第一个值为1的行
int sel = row;
for (int i = row; i < n; i++) {
if (a[i][col] == 1) {
sel = i;
break;
}
}
if (a[sel][col] == 0) continue; // 该列无主元
// 交换当前行与选中的行
int[] temp = a[sel];
a[sel] = a[row];
a[row] = temp;
where[col] = row;
// 消去其他行中该列的1（模2下的高斯消元）
for (int i = 0; i < n; i++) {
if (i != row && a[i][col] == 1) {
for (int j = col; j <= m; j++) {
a[i][j] ^= a[row][j];
}
}
}
row++;
}
// 检查是否有矛盾方程 0 = 1
for (int i = row; i < n; i++) {
if (a[i][m] == 1) return -1; // 无解
}
// 统计自由变量数量
int freeVars = 0;
for (int i = 0; i < m; i++) {
if (where[i] == -1) freeVars++;
}
// 枚举自由变量的所有组合，寻找最少按动次数
int minPresses = Integer.MAX_VALUE;
int totalCombinations = 1 << freeVars;
for (int mask = 0; mask < totalCombinations; mask++) {
int[] ans = new int[m];
int f = 0;
// 设置自由变量的值
for (int i = 0; i < m; i++) {
if (where[i] == -1) {
ans[i] = (mask >> f) & 1;
f++;
}
}
// 回代求解主元变量
for (int i = m - 1; i >= 0; i--) {
if (where[i] != -1) {
int sum = a[where[i]][m]; // 右侧常数项
for (int j = i + 1; j < m; j++) {
sum ^= (a[where[i]][j] & ans[j]);
}
ans[i] = sum;
}
}
int presses = 0;
for (int v : ans) presses += v;
minPresses = Math.min(minPresses, presses);
}
return minPresses;
}
/**
* 辅助方法：打印增广矩阵
*/
public void printMatrix(int[][] a) {
for (int[] row : a) {
System.out.println(Arrays.toString(row));
}
}
/**
* 构造一个示例电路谜题
* 3盏灯，3个开关，按下开关i会翻转灯i和灯(i+1)%3
*/
public static int[][] createExample() {
int n = 3;
int[][] a = new int[n][n + 1];
// 开关0影响灯0和灯1
a[0][0] = 1; a[0][1] = 1; a[0][2] = 0;
// 开关1影响灯1和灯2
a[1][0] = 0; a[1][1] = 1; a[1][2] = 1;
// 开关2影响灯0和灯2
a[2][0] = 1; a[2][1] = 0; a[2][2] = 1;
// 目标：所有灯从灭变亮（初始全0，目标全1）
a[0][3] = 1; a[1][3] = 1; a[2][3] = 1;
return a;
}
public static void main(String[] args) {
CircuitPuzzle solver = new CircuitPuzzle();
System.out.println("=== 电路谜题求解演示 ===\n");
// 二进制枚举示例
System.out.println("【二进制枚举法】");
int n = 3;
int[] effect = {0b011, 0b110, 0b101}; // 开关影响关系
int init = 0b000; // 初始全灭
int result = solver.solveByEnumeration(n, effect, init);
System.out.println("最少按动次数: " + result);
// 高斯消元示例
System.out.println("\n【模2高斯消元法】");
int[][] matrix = createExample();
System.out.println("增广矩阵:");
solver.printMatrix(matrix);
int result2 = solver.solveByGauss(matrix);
System.out.println("最少按动次数: " + result2);
// 大规模测试
System.out.println("\n【大规模测试：10盏灯环形电路】");
int bigN = 10;
int[][] bigMatrix = new int[bigN][bigN + 1];
for (int i = 0; i < bigN; i++) {
bigMatrix[i][i] = 1;
bigMatrix[i][(i + 1) % bigN] = 1;
bigMatrix[i][bigN] = 1; // 目标全亮
}
int result3 = solver.solveByGauss(bigMatrix);
System.out.println("10盏灯环形电路最少按动次数: " + result3);
}
}
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 适用规模 |
|---|---|---|---|
| 二进制枚举 | O(2^n × n) | O(1) | n ≤ 20 |
| 高斯消元 | O(n³ + 2^f × n²) | O(n²) | n ≤ 500，f为自由变量数 |
高斯消元后若自由变量 f 较多（f > 20），枚举自由变量仍可能超时，此时可用启发式搜索或折半枚举优化。
扩展思考
- 多解判重：可通过维护一个解向量集合，输出所有满足最少按动次数的开关组合。
- 加权最小解：若每个开关有不同的”按动代价”，问题转化为模2域上的加权最小覆盖，可用迭代加深或 Dancing Links 求解。
- 三维扩展：将灯排成二维网格，每个开关影响周围十字形区域，本质仍是线性方程组，规模增大时高斯消元更具优势。
电路谜题是理解线性代数在离散优化中应用的绝佳案例，也是许多经典谜题（如熄灯游戏、魔方状态求解）的数学基础。
