關燈游戲和線性代數聯系緊密，對于一個 的燈陣，用線性方程組+高斯消元法求解，時間復雜度為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
新聞熱點
疑難解答
