有没有玩过“亮灯游戏”？
有一个5*5的灯阵，初始状态全是灭的，选择一个灯进行点亮，点亮的同时若其上下左右存在灯，则需要将其一同点亮，如何操作可以点亮所有的灯？
来拆解一下这个解谜：
首先灯只有点亮和熄灭两个状态，可以计作1和0，初始状态是一个5*5的矩阵，值均为0，目标通过一系列操作，把所有值修改成1。
其次，一个灯的状态被改变两次，等于恢复初始值，所以对于矩阵中的每个值，要么操作一次，要么不操作。
再看影响范围，位于中间部分的点，一次操作影响5个值；位于边上的点，一次操作影响4个值；位于角上的点，一次操作影响3个值。
image.png
然后来看点灯操作的实质，若原来状态是0，则操作过后变为1，反之，原来状态是1，则操作之后变为0。这个操作本质上可以看做和1进行异或运算，0^1=1; 1^1=0。
最后来看最终解的形态，值得注意的是，灯的状态和操作的顺序无关，先点A再点B和先点B再点A达到的终态是一样的（参考下图），所以最后的解应该也是一个5*5矩阵，其中值为1代表这个灯需要点，值为0代表这个灯不需要点。点灯顺序不重要。
image.png
综合以上几点，点灯问题本质上就被抽象为一个异或方程组，以3*3为例：
image.png
xn的取值0或1，代表该位置灯是否操作。
x1位置灯的状态受x1,x2,x4是否被点的影响，最终目标状态为1，所以可以写成：x1x2x4=1
同理对应x2位置，可得x1x2x3x5=1，对于x5位置，x2x4x5x6^x8=1
这样，有n个灯和n个位置，就可以构建异或方程组。
根据本科线性代数的知识，方程组可以写成Ax=B的格式，通过高斯消元法来求解。求解方法是先通过线性变化，把矩阵转换为上三角阵，然后倒序确定所有变量的值。具体过程去翻教材或者百度吧。
下面来看具体代码实现。
首先定义一个Pos类，表示谜题矩阵中的元素，包含值、所在行、列、统一编号index等。
class Pos {
private int x;
private int y;
private int row;
private int col;
int getX() {
return x;
}
void setX(int x) {
this.x = x;
}
int getY() {
return y;
}
void setY(int y) {
this.y = y;
}
int getRow() {
return row;
}
void setRow(int row) {
this.row = row;
}
int getCol() {
return col;
}
void setCol(int col) {
this.col = col;
}
Pos getPosByIndex(int index){
this.setX((index-1)/this.col);
this.setY((index-1)%this.col);
return this;
}
int getPosIndex(){
return this.x*this.col + this.y + 1;
}
boolean isInside() {
return this.x >= 0 && this.x < this.row && this.y >= 0 && this.y < this.col;
}
Pos getPosByOffset(int dx, int dy){
Pos pos = new Pos();
pos.row = this.row;
pos.col = this.col;
pos.x = this.x + dx;
pos.y = this.y + dy;
return pos;
}
}
然后来看主程序，大致包括这么几个阶段：
- 读取初始谜题矩阵
- 将谜题矩阵转换为异或方程组
- 求解方程组
- 给出解答矩阵
public class XorLinearEquation {
private static final int[][] towards = {{0,1},{0,-1},{1,0},{-1,0}};
private static int total;
private static int[][] A; //异或方程组
private static int[][] puzzle; //谜题矩阵
private static int[][] answer; //解答矩阵
private static boolean haveLegalAnswer;
private static void getEquations(){
int rows = puzzle.length;
int cols = puzzle[0].length;
answer = new int[rows][cols];
total = rows * cols;
A = new int[total +2][total +2];
Pos pos = new Pos();
pos.setRow(rows);
pos.setCol(cols);
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
pos.setX(i);
pos.setY(j);
getEquationByPos(pos);
}
}
}
private static void getEquationByPos(Pos pos){
int index = pos.getPosIndex();
//自身位置必然受影响，total+1代表终态，根据初始值和1异或确定：若初始值为0，则影响总和需要为1；反之，影响总和需要为0。
A[index][index] = 1;
A[index][total+1] = puzzle[pos.getX()][pos.getY()]^1;
for(int i=0;i<4;i++){
//判断上下左右四个方向是否有灯
Pos offsetPos = pos.getPosByOffset(towards[i][0],towards[i][1]);
if(!offsetPos.isInside()){
continue;
}
//若有，则该位置的灯会受到index开关影响，需要加进方程组。
int index2 = offsetPos.getPosIndex();
A[index][index2] = 1;
}
}
private static void swap(int line1, int line2){
int temp;
for(int i=1;i<=total+1;i++){
temp = A[line1][i];
A[line1][i] = A[line2][i];
A[line2][i] = temp;
}
}
private static void gauss(){
// 高斯消元法
int temp;
for(int i=1;i<=total;i++){
temp = i;
for(int j=i+1;j<=total;j++){
if(A[temp][i]==0 && A[j][i]==1){
temp = j;
break;
}
}
if(A[temp][i]==0){
continue;
}
if(temp!=i){
swap(temp,i);
}
// 以上代码作用：尝试寻找第i列不为0的行，并将其交换至第i行，为消元构成上三角矩阵做准备，若该列所有行均为0，则跳至下一列进行判断。
// 以下为消元过程，若有一行第i列为1，则与第i行进行异或，确保其第i列位置为0，一轮循环后，当前i阶矩阵即变为上三角阵
for(int j=i+1;j<=total;j++){
if(A[j][i]==0){
continue;
}
for(int k=i;k<=total+1;k++){
A[j][k]^=A[i][k];
}
}
}
Pos pos = new Pos();
pos.setRow(puzzle.length);
pos.setCol(puzzle[0].length);
answer = new int[pos.getRow()][pos.getCol()];
for(int i=total;i>=1;i--){
//若矩阵一行左侧所有元素为0，而右侧不为0，则方程无解
if(!legalJudge(i)){
haveLegalAnswer = false;
break;
}
pos = pos.getPosByIndex(i);
//从上三角矩阵右下角获取解
answer[pos.getX()][pos.getY()] = A[i][total+1];
//遍历检查上方行数该列是否为0，若不为0，则将结果列异或进行消元
for(int j=i-1;j>=1;j--){
if(A[j][i]==1){
A[j][total+1]^=A[i][total+1];
}
}
}
}
private static boolean legalJudge(int index){
for(int i = 1;i<=total;i++){
if(A[index][i]!=0){
return true;
}
}
return A[index][total + 1] == 0;
}
private static void showAnswer(){
for (int[] anAnswer : answer) {
System.out.println(Arrays.toString(anAnswer));
}
}
public static void main(String[] args){
// initialize puzzle
puzzle = new int[5][5];
//====================================
// Solve by Gauss elimination
haveLegalAnswer = true;
for (int[] aPuzzle : puzzle) {
System.out.println(Arrays.toString(aPuzzle));
}
System.out.println("===============");
getEquations();
gauss();
if(haveLegalAnswer) {
showAnswer();
} else {
System.out.println("The puzzle has no solution! ");
}
}
}
对于开头的问题，初始矩阵就是5*5的值均为0的二维数组，求解结果如下：
image.png
