Simulation

Simulation就是「模擬」。撰寫程式，去模擬一個行為。

通常一個Simulation的問題，會詳述定義程式的功能與效果，並且規定一套固定的運作流程，程式必須有樣學樣、執行動作。程式設計人員不需要額外設計複雜的演算法，只需要照著題目的描述，建構適當的資料結構來儲存資訊，撰寫行為相仿的程式碼，就可以了。

Simulation主要是在考驗程式設計人員編寫程式碼的功力，而非考驗程式設計者的急智和創意。Simulation可說是程式設計的基本功──問題說得清清楚楚，不用設計複雜的演算法，只要照著規定做就好。這類題目很適合程式設計的初學者。

另外，有一些目前尚未解決的經典問題，由於目前沒有好的演算法，所以只能乖乖的照著問題要求來模擬。這一類的問題也就變成Simulation的問題了。

UVa 10550

舉例：轉骰子（Dice Rotation）

有兩個骰子，上面的點數順序，可能是亂的或是重複的。請辨別兩個骰子一不一樣。骰子經過旋轉後，如果六個對應的面，上面的點數皆相同，則骰子視為相同。

骰子一共有六個面──上下前後左右。我們可以用六個變數，來個別存六個面上頭的點數。用陣列也行。

int dice[6];

讓陣列的第0格存入上面的值、第1格存左面的值，以此類推。當然也可以採用不同的方法來存。

若要讓骰子旋轉，則有三種旋轉方向。一、水平方向，二、垂直方向，三、順時鐘／逆時鐘方向。若要寫成程式，也不難。這裡示範水平方向朝西的旋轉。

void turn_west(int dice[6]) { int temp; temp = dice[1]; dice[1] = dice[2]; dice[2] = dice[3]; dice[3] = dice[4]; dice[4] = temp; }

要辨別兩個骰子一不一樣，則必須好好的旋轉其中一顆骰子，再跟另一顆比對。必須將骰子所有可能的情形都轉出來才行。我個人偏好這麼個轉法：水平方向轉一圈，順時針方向轉一圈，垂直方向轉一下，將以上動作連續做四次。如此可轉出所有情形。當然也可以採用不同的方法來轉。

bool same(int a[6], int b[6]) // 兩個骰子是否相同 { int i, j; for (i=0; i<4; i++) { for (j=0; j<4; j++) { turn_west(); if (equal(a,b)) return true; } for (j=0; j<4; j++) { turn_clockwise(); if (equal(a,b)) return true; } turn_north(); if (equal(a,b)) return true; } return false; } bool equal(int a[6], int b[6]) // 對應的六個面是否全都一樣 { for (int i=0; i<6; i++) if (a[i] != b[i]) return false; return true; }

UVa 253 10877

舉例：撲克牌（Poker）

撲克牌相信大家都玩過，試著用程式模擬一場撲克牌遊戲吧！

http://mathworld.wolfram.com/Cards.html

http://mathworld.wolfram.com/topics/CardGames.html

UVa 127 131 162 170 178 181 451 462 555

舉例：下棋（Board Game）

使用棋盤進行的遊戲。例如象旗、西洋棋、將旗、圍棋、五子棋、黑白棋。考慮人工智慧之前，先來模擬下棋規則、設計一支下棋程式吧！

UVa 220 852 10196 10363 10996 11210

舉例：生命遊戲（The Game of Life）

生命遊戲是相當有名的數學問題。以關鍵字「數學 生命遊戲」可以搜尋到許多資料。另外生命遊戲也有個專有名詞叫做cellular automation，也可以試著往這方面找資料。

生命遊戲是這樣的：現在有一個二維的方格平面，每個格子都有一個細胞，可能是生的，可能是死的。而我們知道一開始哪些格子有細胞，細胞的生命狀況會隨時間變動，規則如下：

復活：一個死的細胞，若是它的八個鄰居，有三個細胞是活的，則在下一刻復活。
存活：一個活的細胞，若是它的八個鄰居，有兩個或三個細胞是活的，則在下一刻存活。
死於孤單：一個活的細胞，若是它的八個鄰居，只有零個或一個細胞是活的，則在下一刻死亡。
死於擁擠：一個活的細胞，若是它的八個鄰居，有四個以上的細胞是活的，則在下一刻死亡。

我們可以弄兩張地圖，第一張地圖儲存現在這個時刻的狀態，第二張地圖儲存下一個時刻的狀態。然後兩張地圖交替使用，以節省記憶體空間。可以嘗試將一個細胞延展的過程寫成一個函式，以利於程式碼的閱讀。

bool map1[100][100], map2[100][100]; void extend(int x, int y) // 對座標(x,y)這個位置做延展 { int n = 八個鄰居中，還活著的細胞數目; if (!map1[x][y]) if (n == 3) // 復活 map2[x][y] = true; else // 仍舊死亡 map2[x][y] = map1[x][y]; else if (n == 2 || n == 3) // 存活 map2[x][y] = true; else if (n == 0 || n == 1) // 死於孤單 map2[x][y] = false; else if (n >= 4) // 死於擁擠 map2[x][y] = false; }

為了讓地圖能夠交叉利用、節省空間，將程式碼做點修正。

bool map[2][100][100]; void extend(int t, int x, int y) // 對座標(x,y)這個位置做延展 { int n = 八個鄰居中，還活著的細胞數目; int t1 = t % 2, t2 = (t+1) % 2; if (!map[t1][x][y]) if (n == 3) // 復活 map[t2][x][y] = true; else // 仍舊死亡 map[t2][x][y] = map[t1][x][y]; else if (n == 2 || n == 3) // 存活 map[t2][x][y] = true; else if (n == 0 || n == 1) // 死於孤單 map[t2][x][y] = false; else if (n >= 4) // 死於擁擠 map[t2][x][y] = false; }

這裡提供兩個Applet，相當有趣：

http://www.bitstorm.org/gameoflife/

http://www.math.com/students/wonders/life/life.html

UVa 447 457 10443 10507

舉例：蘭頓的螞蟻（Langton's Ant）

http://mathworld.wolfram.com/LangtonsAnt.html

http://en.wikipedia.org/wiki/Langton's_ant

跟生命遊戲很相像，不過這個遊戲更神奇。

一、格子有黑與白兩種顏色。
二、螞蟻走入白格則右轉，走入黑格則左轉。
三、螞蟻離開格子時，格子顏色顛倒。

驚人的是，乍看完全沒有規律的路線，卻在10647步之後開始循環。原因至今不明。

Modeling

觀察問題的性質，轉化原問題，將之映射到另外一套恰如其分又耳熟能詳的模型（系統）上；亦可自行設計一套別出心裁的模型（系統）。

Simulation與Modeling息息相關。Simulation是嘗試模擬各種行為，Modeling則是觀察各種行為後，歸納一套固定模式，以後就直接套用此模式來模擬類似問題。

舉例：Joseph Problem

「Joseph Problem」有一種解法是把問題映射至queue，數數殺人變成了一連串的push和pop──該映射就是Modeling。

舉例：State Space Search

「State Space Search」將狀態串聯，映射至圖，以圖論演算法來搜尋答案──該映射也是Modeling。

舉例：用生命遊戲作為模型，模擬生命遊戲。

Flood Fill Algorithm

Flood Fill Algorithm的flood是指「淹水」，fill是指「填滿」。這個演算法的功用，舉例來說，就像是小畫家倒墨水的功能，將鄰近同顏色的區塊，一併染成同一個顏色。

電腦中的圖片，都是以一點一點的像素所組成的。簡單的來說，一張圖片，可以想做是一張方格紙，每個格子都對應到圖片上的一點像素。Flood Fill Algorithm會以某一格當做起點，開始向四周淹水，只要鄰近的格子是空的（顏色一樣的），水就會淹過去。

這裡提供一個簡單的程式碼。它往上下左右四個方向淹水。

int picture[11][21]; // 圖片的大小為 11x21，請參考上圖 int flood(int x, int y, int fill_color, int original_color) { if (x>=0 && x<11 && y>=0 && y<21) // 不能超出邊界 if (picture[x][y] == original_color) // 顏色一樣才flood { picture[x][y] = fill_color; flood(x+1, y, fill_color, original_color); flood(x-1, y, fill_color, original_color); flood(x, y+1, fill_color, original_color); flood(x, y-1, fill_color, original_color); } } int main() { // 在座標(5,4)的位置開始，淋上3號顏色 flood(5, 4, 3, picture[5][4]); }

亦可以將淹水的程式碼寫成這種風格：

// 四個方向 const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, 1, -1}; // 判斷是否超出邊界 bool on_picture(int x, int y) // 位於圖片上 { return x>=0 && x<11 && y>=0 && y<21; } void flood(int x, int y, int fill_color, int original_color) { // 不能超出邊界 if (!on_picture(x, y)) return; // 顏色一樣才flood if (picture[x][y] != original_color) return; picture[x][y] = fill_color; for (int i=0; i<4; i++) { // 求出下一個預定要淹沒的位置 int next_x = x + dx[i], next_y = y + dy[i]; flood(next_x, next_y, fill_color, original_color); } }

實作時要特別注意，避免淹過水的地方又反反覆覆淹了很多次。這會使程式的效率大幅下降，其執行速度之慢，可讓程式在有生之年都不會結束。

言盡於此。這裡有許多類似於Flood Fill Algorithm的演算法，可以參考看看：http://www.codeproject.com/gdi/QuickFill.asp。

兩點是否在同一區塊

Flood Fill Algorithm除了可以達到小畫家中倒墨水的效果之外，還可以找出地圖上某兩點是不是屬於同一區塊。

判斷座標(5,4)和座標(10,10)是不是屬於同一區塊的方法：

int picture[11][21]; bool visit[11][21]; // 新增一個二維陣列，紀錄淹到水的區域 void flood(int x, int y, int original_color) { if (x>=0 && x<11 && y>=0 && y<21) if (picture[x][y] == original_color && !visit[x][y]) { visit[x][y] = true; flood(x+1, y, original_color); flood(x-1, y, original_color); flood(x, y+1, original_color); flood(x, y-1, original_color); } } int main() { // 初始化 for (int i=0; i<11; i++) for (int j=0; j<21; j++) visit[i][j] = false; // 從其中一個點開始淹水，看看會不會淹到另一個點 flood(5, 4); if (visit[10][10]) cout << "兩點相連" << endl; else cout << "兩點不相連" << endl; }

不同區塊的數目

找出這張圖總共有幾個區塊。只需修改一下main function：

int main() { for (int i=0; i<11; i++) for (int j=0; j<21; j++) visit[i][j] = false; int count = 0; for (int x=0; x<11; x++) for (int y=0; y<21; y++) if (!visit[x][y]) { count++; flood(x, y, picture[x][y]); } cout << "總共有" << count << "個區塊" << endl; }

計算距離

找出由某一點開始，到其他所有點的距離。常用來解決走迷宮之類的問題。

int picture[11][21]; int dist[11][21]; void flood(int x, int y, int d, int original_color) { if (x>=0 && x<11 && y>=0 && y<21) if (picture[x][y] == original_color && d < dist[x][y]) { dist[x][y] = d; flood(x+1, y, d+1, original_color); flood(x-1, y, d+1, original_color); flood(x, y+1, d+1, original_color); flood(x, y-1, d+1, original_color); } } int main() { for (int i=0; i<11; i++) for (int j=0; j<21; j++) dist[i][j] = 0; flood(5, 4, 0, picture[5][4]); // 找出和座標(5,4)到其他點的距離 }

以Connected Component作為模型

以圖論的觀點，Flood Fill Algorithm其實就是運用Depth-first Search找到Connected Component。

Flood Fill Algorithm應用廣泛。練習題目也不少。

UVa 260 280 352 469 572 601 657 776 782 784 785 871 10267 10336 10946

Social Balance Theory

從前有一位心理學者認為，人與人之間的關係，可以粗略分為兩種：互相喜歡、互相討厭。這種關係稱做Sentiment Relation，是一種雙向關係，而且擁有喜歡與討厭兩種類型。假使兩人之間好惡分明，沒有亦敵亦友的情況，就會形成Sentiment Relation。

   like            hate
A<------>B      A<------>B

另外Sentiment Relation還具有相當特殊的性質，有點像是transitivity、symmetry、antisymmetry的總合。這種性質的最佳寫照，諸如同仇敵愾、合縱連橫等等，翻成白話就是這樣：

1. 朋友的朋友就是我的朋友。
2. 朋友的敵人就是我的敵人。
3. 敵人的朋友就是我的敵人。
4. 敵人的敵人就是我的朋友。

在Sentiment Relation所形成的社交結構當中，如果產生了好與惡的矛盾，那麼這樣的社交結構就是不平衡的；如果好與惡合理，那麼這樣的社交結構就是平衡的。心理學者相信，當社交結構不平衡的時候，個體會嘗試改變自己的觀點，讓社交結構趨向平衡。

balance:

      A                A           like   like
like / \ like    hate / \ hate      ----A----
    /   \            /   \         /  ha|te  \
   B-----C          B-----C       B-----C-----D
     like             like         hate   hate
 
imbalance:

      A                A           like   like
hate / \ hate    like / \ like      ----A----
    /   \            /   \         /  ha|te  \
   B-----C          B-----C       B-----C-----D
     hate             hate         like   like

後來心理學者進一步發現，當社交結構達到平衡，所有人可以分成兩大陣營，使得陣營內部的關係都是互相喜歡，陣營與陣營之間的關係都是互相討厭。

說了這麼多終於要提到重點。現在問題來了，假設社交結構是平衡的，而我們也知道一些兩兩相互喜歡、相互討厭的資訊時，我們該如何確認誰在同一陣營、誰在不同陣營呢？

以Bipartite Graph作為模型

把社交結構看做是Bipartite Graph，Bipartite Graph的兩側分別是兩大陣營。首先利用Graph Traversal走訪喜歡的邊，找出所有連通分量，並各自縮成一點。然後再度利用Graph Traversal走訪討厭的邊，嘗試建立Bipartite Graph，如果無法建立則表示社交結構不平衡。

以聯集為基礎來建立新模型

當x與y是朋友：
　x及朋友、y及朋友，都是好朋友。
　x的敵人、y的敵人，都是好朋友。

當x與y是敵人：
　x及朋友、y的敵人，都是好朋友。
　x的敵人、y及朋友，都是好朋友。

用Disjoint Sets的union，把好朋友們聯集在一起。要判斷同一陣營，就看看大家是不是同一群好朋友；要判斷不同陣營，就看看對方的敵人是不是跟自己是同一群好朋友。由於一開始每個人都沒有敵人，所以替每個人都設定一個虛擬的假想敵。

#define _x (x + 100) // x的假想敵 #define _y (y + 100) // y的假想敵 // Disjoint-set Forest int p[100 + 100]; // 前百人為本尊，後百人為假想敵。 int init() {for (int i=0; i<200; ++i) p[i] = i;} int find(int x) {return x == p[x] ? x : (p[x] = find(p[x]));} int union(int x, int y) {p[find(x)] = find(y);} bool if_like(int x, int y) { return find(x) == find(y); // return find(_x) == find(_y); } bool if_hate(int x, int y) { return find(x) == find(_y); // return find(_x) == find(y); } // 結交朋友 void like(int x, int y) { if (if_hate(x, y)) return; // imbalance union(x, y); union(_x, _y); } // 樹立敵人 void hate(int x, int y) { if (if_like(x, y)) return; // imbalance union(x, _y); union(_x, y); }

UVa 10158 10505 10608

System of Difference Constraints in Linear Programming

問題：給定變數x1到xN，並給定一些xi-xj≤c的式子，作為條件限制。請判斷有沒有解，如果有解就求出其中一組解。

這個問題可以巧妙的轉換成最短路徑問題。x1到xN看做是圖上的N個點，一條xi-xj≤c的限制式子看做是一條xj到xi的邊，其權重是c。

如果無解，那麼圖上有負環。如果有解，那麼圖上各點的最短路徑長度就是其中一組解。為了讓圖上各點都有最短路徑長度值，可參考Johnson's Algorithm的做法。

UVa 515 ICPC 2058

2-Satisfiability（2-SAT）

X0、X1、……是變數，變數的值只會是true或者false。變數可以重複出現在式子當中，變數還可以加上not運算子。每個括號裡面只有兩個變數，or與and的格式是固定的。

如何設定變數的值，讓整個式子成為true呢？

簡易分析

2-SAT式子主要以and銜接。每個括號必須都是true，整個式子才是true。

括號內部只有一個or，「左右都是true」或者「左true右false」或者「右true左false」，整個括號才是true。

2-Satisfiability，換句話說

2-SAT是要設定每一個變數的值，讓整個式子成為true。

一個變數的值只會是true或者false。一個變數X，要嘛X = true，要嘛X = false。至於X = false也可以寫成notX = true。

2-SAT的解答，就是每個變數X，「X = true」與「notX = true」兩個選一個。要不選X，要不選notX，不會一起選。X與notX有著勢不兩立的關係。

2-SAT問題，換句話說，每個變數X，都看成兩個元件X與notX，然後選一個當作解答，讓每個括號成立，讓整個式子成立。

一個括號當中共有兩個元件，如果其中一個確定不選，就必須選另一個了，如此括號才會成立。

UVa 10319 11294 11861 11930 ICPC 3211 4452

以有向圖作為模型

學過「Topological Sort」的讀者，可以發現，把「受限關係」建立成有向圖，是一個很常見的模式。

一、將變數相互影響的情形，表示成一張有向圖。
　　替每個變數X建立兩個點，分別代表X = true與notX = true。
　　變數有N種，有向圖上就有2N個點。
二、依序處理每個括號。
　甲、當括號內變數不同時，例如(A or B)。
　　回、不選A（選了notA），就一定要選B：建立一條notA -> B的邊。
　　回、不選B（選了notB），就一定要選A：建立一條notB -> A的邊。
　乙、當括號內變數相同時，例如(A or A)。
　　回、一定要選A，一定不能選notA：建立一條notA -> A的邊。
　　　　（從A可以觸及的節點一定都要選。）
　丙、當括號內變數相同，卻一正一反時，例如(A or notA)。
　　回、不管是選A或是選notA，結果都會是true：不必建立邊。

對稱性

【待補文字】

判斷式子是否可以成為true

三、檢查每一個節點：
　甲、如果某個變數X和notX都不得不選，就產生矛盾：有環經過X與not X。
　　　因此整個式子為false。
　乙、如果都沒有發生矛盾，表示至少會有一種合理的設定方式。
　　　因此整個式子為true。

如果有一個環同時經過X和notX，則整個式子為false。

想要檢驗圖上是否有環經過X與notX，一個簡單的做法是：收縮圖上所有環，看看X與notX是否收縮於在同一點。如此就不必窮舉圖上所有的環。

實作時，可以不必縮環，直接看看X與notX是否在同一個Strongly Connected Component即可──SCC即是一群交疊在一起的環。請參考「Component」。

找出其中一組變數設定方式，讓整個式子成為true。

四、每一對X與notX都從中選出一個作為2-SAT的解答。
　　有向圖上有2N個點，總共會選出N個點。

把clause全部建成圖。如果令X = true，那麼X暨子孫就必須通通都選，同時notX暨祖先也必須統統不選；如果令notX = true，那麼情況恰恰顛倒。

一、建立有向圖。
二、尋找所有Strongly Connected Component。
三、收縮每個Strongly Connected Component，成為有向無環圖DAG。
四、依序判斷每個變數是否為解：
　甲、嘗試X作為解：若X的子孫存在非解者，則X非解。
　乙、嘗試notX作為解：若notX的子孫存在非解者，則notX非解。
　丙、確認X與not X何者為解後，將其子孫確實標記為解。

逐一嘗試，時間複雜度為O(VE)。能找出字典順序最小的解。

const int N = 10; // 變數的數量 bool adj[20][20]; // adjancecy matrix int visit[20]; // DFS visit record int sat[20]; // 紀錄一組變數設定方式 // 令A為0，not A為10；B為1，not B為11。 int not(int a) {return a<N ? a+N : a-N;} /* // 另外一種方式：令A為0，not A為1；B為2，not B為3。 int not(int a) {return a&1 ? a : a+1;} int not(int a) {return a^1;} */ bool dfs_try(int i) { if (visit[i] == 1 || sat[i] == 1) return true; if (visit[i] == 2 || sat[i] == 2) return false; visit[i] = 1; visit[not(i)] = 2; for (int j=0; j<N+N; ++j) if (adj[i][j] && !dfs_try(j)) return false; return true; } void dfs_mark(int i) { if (sat[i] == 1) return; sat[i] = 1; sat[not(i)] = 2; for (int j=0; j<N+N; ++j) if (adj[i][j]) dfs_mark(j); } void two_satisfiability() { // 輸入clause memset(adj, false, sizeof(adj)); int a, b; while (cin >> a >> b) { map[not(a)][b] = true; map[not(b)][a] = true; } // 找出一組解 for (int i=0; i<N; ++i) { memset(visit, 0, sizeof(visit)); if (dfs_try(i)) {dfs_mark(i); continue;} memset(visit, 0, sizeof(visit)); if (dfs_try(not(i))) {dfs_mark(not(i)); continue;} // 無解則立即結束。 return; } // 印出一組解。 for (int i=1; i<N; ++i) if (sat[i] == 1) cout << i; else /*if (sat[i] == 2)*/ cout << "not" << i; }

找出最小一組變數設定方式，讓整個式子成為true。

一、建立有向圖。
二、尋找所有Strongly Connected Component。
三、收縮每個Strongly Connected Component，成為有向無環圖DAG。
四、尋找縮圖的Topological Ordering。
五、在縮圖上，以Topological Ordering的反序，列出解。

時間複雜度為O(V+E)。

bool adj[20][20]; // adjancecy matrix int visit[20]; int sat[20]; // 紀錄一組變數設定方式 int finish[20], scc[20], n = 0; void DFS1(int i) { visit[i] = true; for (int j=0; j<N+N; ++j) if (map[i][j] && !visit[j]) DFS1(j); finish[n++] = i; } void DFS2(int i) { scc[i] = n; visit[i] = true; for (int j=0; j<N+N; ++j) if (map[j][i] && !visit[j]) DFS2(j); } void two_satisfiability() { ...... // Kosaraju's Algorithm：尋找拓樸順序。 n = 0; // 時刻 memset(visit, false, sizeof(visit)); for (int i=0; i<N+N; ++i) if (!visit[i]) DFS1(i); // Kosaraju's Algorithm：找出強連通分量。 n = 0; // 強連通分量的編號 memset(visit, false, sizeof(visit)); for (int k=N+N-1; k>=0; --k) { int i = finish[k]; if (!visit[i]) DFS2(i), n++; } // 檢查是否有解，無解則立即結束。 for (int i=0; i<N; ++i) if (scc[i] == scc[inv(i)]) return; // 找出一組解 memset(sat, 0, sizeof(sat)); for (int k=0; k<N+N; ++k) { int i = finish[k]; if (!sat[scc[i]]) { sat[scc[i]] = 1; sat[scc[not(i)]] = 2; } } // 印出一組解 for (int i=1; i<N; ++i) if (sat[scc[i]] == 1) cout << i; else /*if (sat[scc[i]] == 2)*/ cout << "not" << i; }

點燈遊戲

此遊戲的目的是操作開關以熄滅（或點燃）所有燈。按下一個燈上的開關後，會連帶影響自己及其四周的燈，亮變暗、暗變亮：http://oddest.nc.hcc.edu.tw/math171.htm。

這篇文章將介紹最廣為人知的解法，是以線性函數當作模型：http://mathworld.wolfram.com/LightsOutPuzzle.html。以下文章只點到為止。

點燈遊戲的性質

無論開關們同時按和分開按、先按和後按，其造成的影響都一樣。
一個開關按兩次，跟按零次一樣，會相互抵銷。按開關次數可以模二。按開關可想成是與1做xor。
一個燈受開關們影響兩次，會相互抵銷，變成沒有影響，不論燈經過了任何點燃還是熄滅。

確立模型

該問題得以函數當作模型來表示之：f(按下的開關) = 盤面，f就是遊戲規則，是固定的。只要求出f的反函數，就可以用盤面求得按下的開關。巧妙的是，f是線性函數，故可以解聯立線性方程式來找到反函數。

加法封閉性：f(同時按下開關A和B) = f(按下開關A) + f(按下開關B)，加法定義為xor。
倍率封閉性：f(按下開關A一共k次) = k * f(按下開關A)，k模二後，乘法即可定義為and。

附帶一提，有一種常見的函數模型是：g(舊盤面) = 新盤面，g為一種按開關的方式。這種模型更加常見，但這裡並不適用此模型來解決問題。

解聯立線性方程式

要解聯立線性方程式，可以用高斯消去法或其他解聯立方程式的方法：http://mathworld.wolfram.com/LinearAlgebra.html。解聯立方程式是中級學校的數學教材，故省去不提。

時間複雜度為O((H*W)^3)，H和W分別為盤面的長和寬，而三次方是高斯消去法的時間複雜度。

判斷盤面是否有解

解聯立方程式之時，同時也可以驗證盤面是否有解。f如果有反函數，則表示值域和對應域中的元素一一對應；這也就是說，無論一開始燈是如何亮著的，必恰有一組獨特的操作方式，每個燈只按一次或零次，就能熄滅（點燃）所有燈。f如果有反函數，不論盤面長得如何，都一定有解。

然而，當f沒有反函數時，則不能確定盤面是否有解，這種情況下是一個NP-Complete問題。

UVa 10309 10318