有沒(méi)有玩過(guò)“亮燈游戲”驼鞭？
有一個(gè)5*5的燈陣秦驯，初始狀態(tài)全是滅的，選擇一個(gè)燈進(jìn)行點(diǎn)亮挣棕，點(diǎn)亮的同時(shí)若其上下左右存在燈译隘，則需要將其一同點(diǎn)亮，如何操作可以點(diǎn)亮所有的燈洛心？
來(lái)拆解一下這個(gè)解謎：
首先燈只有點(diǎn)亮和熄滅兩個(gè)狀態(tài)固耘，可以計(jì)作1和0，初始狀態(tài)是一個(gè)5*5的矩陣词身，值均為0厅目，目標(biāo)通過(guò)一系列操作，把所有值修改成1法严。
其次损敷，一個(gè)燈的狀態(tài)被改變兩次，等于恢復(fù)初始值深啤，所以對(duì)于矩陣中的每個(gè)值嗤锉，要么操作一次，要么不操作墓塌。
再看影響范圍瘟忱，位于中間部分的點(diǎn)，一次操作影響5個(gè)值苫幢；位于邊上的點(diǎn)访诱，一次操作影響4個(gè)值；位于角上的點(diǎn)韩肝，一次操作影響3個(gè)值触菜。
然后來(lái)看點(diǎn)燈操作的實(shí)質(zhì)，若原來(lái)狀態(tài)是0哀峻，則操作過(guò)后變?yōu)?涡相，反之，原來(lái)狀態(tài)是1剩蟀，則操作之后變?yōu)?催蝗。這個(gè)操作本質(zhì)上可以看做和1進(jìn)行異或運(yùn)算，0^1=1; 1^1=0育特。
最后來(lái)看最終解的形態(tài)丙号，值得注意的是，燈的狀態(tài)和操作的順序無(wú)關(guān)，先點(diǎn)A再點(diǎn)B和先點(diǎn)B再點(diǎn)A達(dá)到的終態(tài)是一樣的（參考下圖）犬缨，所以最后的解應(yīng)該也是一個(gè)5*5矩陣喳魏，其中值為1代表這個(gè)燈需要點(diǎn)，值為0代表這個(gè)燈不需要點(diǎn)怀薛。點(diǎn)燈順序不重要刺彩。
綜合以上幾點(diǎn)，點(diǎn)燈問(wèn)題本質(zhì)上就被抽象為一個(gè)異或方程組枝恋，以3*3為例：
xn的取值0或1迂苛，代表該位置燈是否操作。
x1位置燈的狀態(tài)受x1,x2,x4是否被點(diǎn)的影響鼓择，最終目標(biāo)狀態(tài)為1三幻，所以可以寫(xiě)成：x1x2x4=1
同理對(duì)應(yīng)x2位置，可得x1x2x3x5=1呐能，對(duì)于x5位置念搬，x2x4x5x6^x8=1
這樣，有n個(gè)燈和n個(gè)位置摆出，就可以構(gòu)建異或方程組朗徊。
根據(jù)本科線(xiàn)性代數(shù)的知識(shí)，方程組可以寫(xiě)成Ax=B的格式偎漫，通過(guò)高斯消元法來(lái)求解爷恳。求解方法是先通過(guò)線(xiàn)性變化，把矩陣轉(zhuǎn)換為上三角陣象踊，然后倒序確定所有變量的值温亲。具體過(guò)程去翻教材或者百度吧。
下面來(lái)看具體代碼實(shí)現(xiàn)杯矩。
首先定義一個(gè)Pos類(lèi)栈虚，表示謎題矩陣中的元素，包含值史隆、所在行魂务、列、統(tǒng)一編號(hào)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;
}
}
然后來(lái)看主程序粘姜，大致包括這么幾個(gè)階段：
- 讀取初始謎題矩陣
- 將謎題矩陣轉(zhuǎn)換為異或方程組
- 求解方程組
- 給出解答矩陣
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代表終態(tài)熔酷，根據(jù)初始值和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++){
//判斷上下左右四個(gè)方向是否有燈
Pos offsetPos = pos.getPosByOffset(towards[i][0],towards[i][1]);
if(!offsetPos.isInside()){
continue;
}
//若有留储，則該位置的燈會(huì)受到index開(kāi)關(guān)影響翼抠，需要加進(jìn)方程組咙轩。
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行阴颖，為消元構(gòu)成上三角矩陣做準(zhǔn)備活喊，若該列所有行均為0，則跳至下一列進(jìn)行判斷量愧。
// 以下為消元過(guò)程钾菊，若有一行第i列為1，則與第i行進(jìn)行異或偎肃，確保其第i列位置為0煞烫，一輪循環(huán)后，當(dāng)前i階矩陣即變?yōu)樯先顷? 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--){
//若矩陣一行左側(cè)所有元素為0累颂，而右側(cè)不為0滞详，則方程無(wú)解
if(!legalJudge(i)){
haveLegalAnswer = false;
break;
}
pos = pos.getPosByIndex(i);
//從上三角矩陣右下角獲取解
answer[pos.getX()][pos.getY()] = A[i][total+1];
//遍歷檢查上方行數(shù)該列是否為0，若不為0紊馏，則將結(jié)果列異或進(jìn)行消元
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! ");
}
}
}
對(duì)于開(kāi)頭的問(wèn)題料饥，初始矩陣就是5*5的值均為0的二維數(shù)組，求解結(jié)果如下：
