关灯游戏
关灯游戏和线性代数联系紧密，对于一个 的灯阵，用线性方程组+高斯消元法求解，时间复杂度为O(m×n)^3。相对于首行枚举算法复杂度O(2^n) ，线代算法的时间复杂度低很多。用线性代数求解关灯游戏是个很不错的选择。
本文用最通俗的语言介绍线代求解关灯游戏原理。由于解释通俗化，细节之处难以严谨表述，说得不好的地方，请大神轻拍。
线性方程组求解关灯游戏的原理
问题：
一个2×2灯阵，初始局面右下方3盏灯亮，左上角一盏灯不亮，如下图所示。请用线性代数求解，找到可以使得所有灯都熄灭的开关操作。
解：
我们对四盏灯的开/关操作分别记为 x1、x2 、x3 、x4 ，如下图所示：
我们用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
相关阅读
萨莎 · 格雷（Sasha Grey）是本世纪最为引人注目的色情明星之一，在她的色情电影职业生涯中，其经典的印度少女扮相以及曾经拍过的
本篇文章为大家分析了一款第三方游戏下载平台——TapTap ，TapTap 致力于向玩家推荐真正好玩的正版游戏，以及向开发者提供测试、反馈
Tracert(traceroute)&Ping 工作原理分析
一、tracert工作过程分析 Tracert 命令用 IP 生存时间 (TTL) 字段和 ICMP 错误消息来确定从一个主机到网络上其他主机的路由。首
学原生js的语法其实是容易的，最主要的练习逻辑思维。对于刚刚学完js的语法的我来说，写这个打地鼠游戏真的花费了我一整天的时间。整
在淘宝游戏交易平台如何购买？ 第一步：找到宝贝后，点击立即购买。 第二步：在接下来的页面中填写收货信息，请务必认真填写，否则将无法收