关灯游戏和线性代数联系紧密，对于一个 的灯阵，用线性方程组+高斯消元法求解，时间复杂度为O(m×n)^3。相对于首行枚举算法复杂度O(2^n) ，线代算法的时间复杂度低很多。用线性代数求解关灯游戏是个很不错的选择。
本文用最通俗的语言介绍线代求解关灯游戏原理。由于解释通俗化，细节之处难以严谨表述，说得不好的地方，请大神轻拍。
线性方程组求解关灯游戏的原理
问题：
一个2×2灯阵，初始局面右下方3盏灯亮，左上角一盏灯不亮，如下图所示。请用线性代数求解，找到可以使得所有灯都熄灭的开关操作。
我们用1代表操作，用0代表未操作，即 的取值为0或1。对四盏灯的亮/灭状态分别记为 L1、L2 、L3 、L4 ，如下图所示：
我们用1代表亮着的灯，用0代表熄灭的灯，根据局面的初始状态，很显然有
接下来观察局面，
能影响L1灯的亮/灭状态的操作只有 x1、x2 、x3 ；
能影响L2灯的亮/灭状态的操作只有 x1、x2 、x4 ；
能影响L3灯的亮/灭状态的操作只有 x1、x3 、x4 ；
能影响L4灯的亮/灭状态的操作只有 x2、x3 、x4 ；
定理1：对同一盏灯开/关操作偶数次，等于操作0次；对同一盏灯操作奇数次，等于操作1次。
所以我们将 x1、x2、x3、x4 及其系取值限定在0或者1两个数值，以后不再说明(不怕蛋疼的话，可以对操作次数不限定，这样一来将有无穷多个解，这些解都是在基础解上对每盏灯再重复操作偶数次，本质上相同)。
假如一开始所有灯都熄灭，并且假设将 x1、x2、x3、x4 全体操作一遍后，灯阵的亮/灭状态为当前状态。根据定理1，那么将 x1、x2、x3、x4 全体再操作一遍，灯阵就又回到全熄灭状态。x1、x2、x3、x4 就是我们想要的答案，于是列方程组：
游戏问题转换成了求解方程组问题。上面方程组不难求解，用初中的知识足够了。有一点要注意，方程组是在二元域{0,1}内求解，也就是运算过程中，所有数值的取值范围都只能是0或者1。二元域运算规则和常规运算规则有所不同，具体如下(不要问我二元域运算规则为什么是这样的，要问就问什么是灯？或者灯为什么会亮？之类的问题)：
加法：0+0=0,0+1=1,1+0=1,1+1=0
减法：0-0=0,0-1=1,1-0=1,1-1=0
乘法：0×0=0，0×1=0，1×0=0，1×1=1
除法：0/0=无意义，0/1=0，1/0=无意义，1/1=1
注：有限域上的运算符号并不是上面那个样子，而是一些圈、叉之类的奇怪符号。这里一方面不方便打出这些符号，另一方面也为了让读者便于理解，所以仍旧采用“＋、－、×、／”形式。我们看到，加减法都等价于二进制位运算中的“亦或”运算；乘法等价于二进制位运算中的“与”运算；除法在这里用不到，直接无视。
方程组求解结果为：
这是方程组唯一的解，所以这个游戏局面解法是唯一的，标记在游戏局面见下图：
到这里，线代原理就介绍完毕了。怎么样，线代解法原理很简单吧，无非就是求解线性方程组问题。而计算机求解线性方程组，我们在增广矩阵中用高斯消元法，时间复杂度为O(m×n)^3，判断游戏有没有解，可以用矩阵的秩来判断方程组有没有解，有多少个解。
用线性代数搜索所有解法的C/C++代码如下：
#include<iostream>using namespace std;int Row,Column,MAXN;void init(int **matrix) //初始化系数矩阵{ int i,j,k; for(i=0; i<Row; i++) for(j=0; j<Column; j++) { k=i*Column+j; matrix[k][k]=1; if(i>0)matrix[(i-1)*Column+j][k]=1; if(i<Row-1)matrix[(i+1)*Column+j][k]=1; if(j>0)matrix[i*Column+j-1][k]=1; if(j<Column-1)matrix[i*Column+j+1][k]=1; }}void Gauss(int **matrix,int *solution) //高斯消元{ int i,j,k,x,y=0,rand_coefficient,rand_matrix,rank1,rank2,inc=0; for(k=0; k<MAXN&&y<MAXN; k++,y++) //增广矩阵转换为阶梯矩阵 { x=k; for(i=k+1; i<MAXN; i++) if(matrix[i][y]>matrix[x][y])x=i; if(x-k) //交换矩阵行数据 for(j=y; j<MAXN+1; j++) { matrix[k][j]=matrix[k][j]^matrix[x][j]; matrix[x][j]=matrix[k][j]^matrix[x][j]; matrix[k][j]=matrix[k][j]^matrix[x][j]; } if(matrix[k][y]==0) { k--; continue; } for(i=k+1; i<MAXN; i++) //消元 if(matrix[i][y]) for(j=y; j<MAXN+1; j++)matrix[i][j]^=matrix[k][j]; } for(rand_coefficient=rand_matrix=i=0; i<MAXN; i++) //计算系数矩阵的秩和增广矩阵的秩 { for(rank1=rank2=j=0; j<=MAXN; j++) { if(j<MAXN)rank1|=matrix[i][j]; rank2|=matrix[i][j]; } rand_coefficient+=rank1; rand_matrix+=rank2; } if(rand_coefficient<rand_matrix) //系数矩阵秩小于增广矩阵秩，局面无解 cout<<"此局面无解!/n/n"; else //枚举并回代求解 { for(k=1<<(MAXN-rand_coefficient); k>0; k--) { for(i=MAXN-1; i>rand_coefficient; i--) { matrix[i-1][MAXN]+=matrix[i][MAXN]>>1; matrix[i][MAXN]&=1; } for(i=0; i<MAXN; i++)solution[i]=matrix[i][MAXN]; for(i=MAXN-1; i>=0; i--) //回代 for(j=i-1; j>=0; j--) if(matrix[j][i])solution[j]^=solution[i]; for(i=0; i<MAXN; i++) //输出答案 (i%Column)?cout<<solution[i]<<" ":cout<<endl<<solution[i]<<" "; inc++; //解数量计数器 PRintf("/n"); matrix[MAXN-1][MAXN]++; } cout<<"/n共计"<<inc<<"个解/n"; }}int main(void){ int i,j; char C; cout<<"/n 关灯游戏(Lights out)解题程序(线代解法)/n"; cout<<"请输入行数："; cin>>Row; cout<<"请输入列数："; cin>>Column; MAXN=Column*Row; int **matrix=new int*[MAXN+4]; //增广矩阵，二维数组 for(i=0; i<MAXN+4; i++)matrix[i]=new int [MAXN+4]; int *solution=new int[MAXN+2]; //解数组 for(i=0; i<MAXN+4; i++) for(j=0; j<MAXN+4; j++)matrix[i][j]=0; init(matrix); //初始化系数矩阵 cout<<"请选择，是否输入指定初始局面?(Y/N)：",cin>>C; if((C=='Y')||(C=='y')) { cout<<"请输入初始局面(1代表亮灯，0代表灭灯，灯与灯之间用空格隔开，换行用回车)：/n"; for(i=0; i<MAXN; i++)cin>>matrix[i][MAXN]; } else for(i=0; i<MAXN; i++)matrix[i][MAXN]=1; //默认初始化局面为灯全亮 Gauss(matrix,solution); for(int i=0; i<MAXN+4; i++)delete []matrix[i]; delete []matrix; delete []solution; cout<<"/n/n求解完毕，请按任意键退出程序。"; cin.ignore(),cin.ignore(); //暂停显示 return 0;} 上面代码可以搜索任意局面的全部解，允许用户输入任意初始局面，已经非常方便使用了。如果还觉得使用上面代码太麻烦，笔者将其制作成软件，截图如下：
软件在这里下载：关灯游戏解题程序1.0版 https://pan.baidu.com/s/1geNMxcZ
新闻热点
疑难解答
