一個有趣的益智遊戲「點燈」之電腦解法及分析
蔡明原、林順喜
國立臺灣師範大學
資訊教育系
摘要
本文嘗試利用演算法的設計及分析，希望能找出網路上一個有趣的遊戲「點燈遊戲」(All Lights)之電腦解法。程式執行結果發現使用我們所設計的有效率演算法，能在短時間之內解出20*20以下的所有盤面，並發現20*20以下的盤面不論是矩形或方形都有解，差別在於解法之個數，有的是只有唯一解，有的則是有上千組解，而且大盤面與小盤面之間並無相關性，很難以數學方法推測解法。未來希望能找出更好之演算法，以更少的時間解更大的盤面。
我們在網際網路上尋找一些有趣的的遊戲網站時，偶然發現了榮榮益智小站裡面有一個點燈遊戲(http://puma.cs.nthu.edu.tw/~trchen/java/alllights/alllights.html）很有意思
。這個點燈遊戲原稱為all lights game，在下列網站均可找到其Java Applet來玩：
http://www.magic.com.br/public/divert/misc/alllight/index.htm
http://koti.nettilinja.fi/~erkkatah/start/pelit/Alllight/alllight.htm
http://speth08.wu-wien.ac.at/usr/h94/h9451038/games/alllight/alllight.htm
http://www.math.nccu.edu.tw/game/alllight.htm
http://www.alishan.net.tw/koala/game/split-alllight.htm
http://cdrom1.unibase.com/local/wmtk/java/misc/alllight/index.htm
網頁上是一個5＊5的方形盤面，當時我們苦思不得其解，就想說：如果用電腦來解，會不會快一點呢？所以就著手思考找出該遊戲的解法，而該遊戲的玩法如下：(表1)是一個5＊5的點燈遊戲盤面，一開始25盞燈全都是不亮的，其中●表示亮燈，○ 表示暗燈。使用者可以任意點在任何一盞燈上。每按一盞燈時，除了那一盞燈之外，它的上下左右四盞燈也會跟著變化--原來暗的會變亮，原來亮的會變暗。如果能讓所有的燈全亮就成功了。(表2)表示當我們點了B2這個點，B2本身和B1、A2、C2和B3(上下左右四點)的狀態都改變了，原本不亮的燈都亮了。(表3)表示當我們點完(表2)的B2後又點了C3這個點，所以C2和B3這兩個原來因為B2而亮的燈，因為C3的交互作用不亮了。
(表1)
|
|
A |
B |
C |
D |
E |
|
1 |
○ |
○ |
○ |
○ |
○ |
|
2 |
○ |
○ |
○ |
○ |
○ |
|
3 |
○ |
○ |
○ |
○ |
○ |
|
4 |
○ |
○ |
○ |
○ |
○ |
|
5 |
○ |
○ |
○ |
○ |
○ |
(表2)
|
A |
B |
C |
D |
E |
|
|
1 |
○ |
● |
○ |
○ |
○ |
|
2 |
● |
● |
● |
○ |
○ |
|
3 |
○ |
● |
○ |
○ |
○ |
|
4 |
○ |
○ |
○ |
○ |
○ |
|
5 |
○ |
○ |
○ |
○ |
○ |
(表3)
|
A |
B |
C |
D |
E |
|
|
1 |
○ |
● |
○ |
○ |
○ |
|
2 |
● |
● |
○ |
○ |
○ |
|
3 |
○ |
○ |
● |
● |
○ |
|
4 |
○ |
○ |
● |
○ |
○ |
|
5 |
○ |
○ |
○ |
○ |
○ |
2.人腦玩此遊戲和電腦玩有何不同之處？
平常當人們在玩這個遊戲時，就是嘗試錯誤地一直點，直到點出所有的燈都亮起，但是這樣的結果，常常會在同一盞燈上點上好幾次而不自知，而且如果碰巧點出了結果，也很難記起自己點燈的步驟，非常的沒有效率。經過分析後我們發現，所有的燈只有點與不點兩種狀態，點某盞燈奇數次都一樣；點某盞燈偶數次和沒有點是一樣的。所以我們可以用0和1來記錄每一個燈點與不點的狀態，經由記錄狀態來判斷目前的點燈盤面是否已將所有的燈點亮。
另一方面，由於點亮一個燈會影響上下左右及自己五個燈，換句話說，每一個燈受自己及上下左右五個燈的影響，如果這五個燈裡，有奇數個被點了，這個燈就會亮，如果是偶數就不會亮，以下以一個 3*3 的點燈盤面做說明。在一個 3*3 的盤面裡，唯一能讓所有燈點亮的點法就是(表4)打標示”1”的部分。將(表4)中寫上1的地方點了，九個燈都會亮，因為每一個燈四周五個燈被點的次數相加都是奇數次。
(表4)
|
|
A |
B |
C |
|
1 |
1 |
0 |
1 |
|
2 |
0 |
1 |
0 |
|
3 |
1 |
0 |
1 |
當盤面比較小的時候，我們可以用人腦去推測出可能的結果，但是盤面加大，光用人腦去嘗試錯誤是非常耗時的，所以我們希望藉助電腦幫我們算出大盤面的點燈法，並證明每一種n*m的盤面都能找到點燈法，或是找出從小盤面推算出大盤面的方法，目標是找出20*20以下是不是所有的矩形或方形盤面都能找到點燈的解法。因為每一個燈都有點與不點(1或0)的兩種狀態，最直覺的想法就是用電腦窮舉20*20的盤面，但是那將有2400種可能性，如果全部窮舉，光解一個20*20的盤面，就將花掉一輩子的時間，所以我們必須用到一些演算法來把不可能的點燈法剔除，例如點燈法中只要有任何一個點四周的點加起來被點的次數是偶數，就表示該點燈法不可能點亮所有燈，應該馬上終止，測試下一組點燈法。
以下以5*5點燈盤面說明之。首先產生一個5*5的陣列，然後用搜尋方式一格一格填入0與1，尋找可能的點燈法(有點到的燈的在陣列中填入1，沒點到的燈的填入0)，一邊填格子一邊檢查，當搜尋到第25盞燈而且盤面可使所有的燈點亮就輸出結果。而填格時檢查的方法如下：因為每點一盞燈會影響的只有陣列中上一行下一行和自己這一行，所以在利用遞迴產生0與1時，產生到第二行的元素時，就可以檢查該元素上一行所產生的0與1符不符合周圍奇數點燈的條件。如果不合，就退回去再產生上一行的結果。如果符合就再產生下一行，即在第n行檢查第n-1行的元素。而當程式到了產生最後一個元素(本例中最後一個元素是第25格)時，檢查第n行(本例中n就等於5)，如果也合理，此盤面即為所求。方法詳見下表。(表5)表示當我們在陣列的第一行中產生0與1，到了第二行，為了讓A1的點四周及自已保持奇數個燈被點，所以在A2中，我們必須填入1。(表6)表示如果第一行都填0，第二行依上述的說明，為滿足讓第一行元素四周都有奇數的燈被點，勢必都要填入1。(表7)表示依上述的方法再往下填入，會發現填到B5時，為了讓B4四週有奇數點，所以填1，但這樣卻造成A5四周有偶數個燈被點，所以此點燈法無效，盤面需backtracking重新產生解法。(表8)表示經過上述的演算法之後，我們會得出一組5*5的解。整體而言，5*5盤面的解法有四種，即(表8)旋轉四個方向為其解。
(表5)
|
A |
B |
C |
D |
E |
|
|
1 |
0 |
0 |
0 |
0 |
0 |
|
2 |
0/1 |
||||
|
3 |
|||||
|
4 |
|||||
|
5 |
(表6)
|
A |
B |
C |
D |
E |
|
|
1 |
0 |
0 |
0 |
0 |
0 |
|
2 |
1 |
1 |
1 |
1 |
1 |
|
3 |
|||||
|
4 |
|||||
|
5 |
(表7)
|
A |
B |
C |
D |
E |
|
|
1 |
0 |
0 |
0 |
0 |
0 |
|
2 |
1 |
1 |
1 |
1 |
1 |
|
3 |
1 |
0 |
0 |
0 |
1 |
|
4 |
1 |
1 |
0 |
1 |
1 |
|
5 |
0 |
1 |
(表8)
|
A |
B |
C |
D |
E |
|
|
1 |
1 |
1 |
0 |
0 |
0 |
|
2 |
1 |
1 |
0 |
1 |
1 |
|
3 |
0 |
0 |
1 |
1 |
1 |
|
4 |
0 |
1 |
1 |
1 |
0 |
|
5 |
0 |
1 |
1 |
0 |
1 |
這樣的方法，在我們的電腦(Pentium-233 MS-DOS 6.22環境)執行 5 * 5 的盤面只需0.000712秒，而且發現解答具有對稱性，所以我們有下列三個想法(但尚未有結論)：
之後我們進行了程式的修改及結果的統計，發現並非所有盤面都是對稱的，而對稱的形式也有「左右對稱」及「對角線對稱」(如下圖所示)，所以程式不能只考慮對稱的盤面來加速尋找解答的速度。
首先我們修改原來的程式，利用迴圈讓程式尋找1*1至20*20之所有矩型盤面，並計算執行時間及只找其中一組解答，結果讓人驚訝的，發現所有的盤面最少都有一組解(見表9)。而19*19的盤面甚至有65536組解答，而且(1*n)的盤面解法好像有規律性，(1、2、1、1、2、1、1、2、1、…)循環，而(2*n)的盤面則是(1、4、1、2)循環，而(3*n)的盤面則是(1、1、8、1、1、4)循環，但有些似乎又找不出循環的規律。如果我們把對稱的重覆盤面去除，是不是能發現其規律性？是不是能證明不管多大的盤面都能找到點燈的方法？
(表9) 1*1至20*20之矩型盤面解法總數統計
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
|
1 |
1 |
|||||||||||||||||||
|
2 |
2 |
1 |
||||||||||||||||||
|
3 |
1 |
4 |
1 |
|||||||||||||||||
|
4 |
1 |
1 |
1 |
16 |
||||||||||||||||
|
5 |
2 |
2 |
8 |
1 |
4 |
|||||||||||||||
|
6 |
1 |
1 |
1 |
1 |
1 |
1 |
||||||||||||||
|
7 |
1 |
4 |
1 |
1 |
16 |
1 |
1 |
|||||||||||||
|
8 |
2 |
1 |
4 |
1 |
2 |
64 |
4 |
1 |
||||||||||||
|
9 |
1 |
2 |
1 |
16 |
2 |
1 |
1 |
2 |
256 |
|||||||||||
|
10 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
||||||||||
|
11 |
2 |
4 |
8 |
1 |
16 |
1 |
128 |
4 |
2 |
1 |
64 |
|||||||||
|
12 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
||||||||
|
13 |
1 |
2 |
1 |
1 |
2 |
1 |
1 |
128 |
1 |
1 |
2 |
1 |
1 |
|||||||
|
14 |
2 |
1 |
4 |
16 |
2 |
1 |
4 |
1 |
32 |
1 |
4 |
1 |
2 |
16 |
||||||
|
15 |
1 |
4 |
1 |
1 |
16 |
1 |
1 |
4 |
1 |
1 |
256 |
1 |
1 |
4 |
1 |
|||||
|
16 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
256 |
1 |
256 |
||||
|
17 |
2 |
2 |
8 |
1 |
4 |
64 |
16 |
2 |
2 |
1 |
16 |
1 |
8192 |
2 |
16 |
1 |
4 |
|||
|
18 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
||
|
19 |
1 |
4 |
1 |
16 |
8 |
1 |
1 |
4 |
256 |
1 |
8 |
1 |
1 |
64 |
1 |
1 |
8 |
1 |
65536 |
|
|
20 |
2 |
1 |
4 |
1 |
2 |
1 |
4 |
64 |
2 |
1 |
4 |
1 |
2 |
1 |
4 |
1 |
128 |
1 |
4 |
1 |
而在解題的時間方面，20*20以下的盤面，幾乎大都能在一秒內能找出一組答案，但是更大的盤面，解題時間卻要數十秒甚至百秒、千秒，所以如果要以現在的方法來處理很大的盤面，仍需要更好的演算法。(解題時間統計請見表10)在附錄一中我們列出1*1至20*20之矩型盤面解答(只列出一組)。
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
|
1 |
3.27E-05 |
|||||||||||||||||||
|
2 |
1.26E-05 |
3.27E-05 |
||||||||||||||||||
|
3 |
6.70E-06 |
1.84E-05 |
0.00024 |
|||||||||||||||||
|
4 |
2.26E-05 |
4.94E-05 |
0.00024 |
4.61E-05 |
||||||||||||||||
|
5 |
1.34E-05 |
2.85E-05 |
5.28E-05 |
0.00042 |
0.00071 |
|||||||||||||||
|
6 |
1.84E-05 |
0.00012 |
0.00019 |
0.00114 |
9.30E-05 |
0.00765 |
||||||||||||||
|
7 |
4.44E-05 |
4.36E-05 |
6.96E-05 |
0.0004 |
0.00023 |
0.00683 |
0.01221 |
|||||||||||||
|
8 |
2.18E-05 |
0.00011 |
0.00016 |
0.00132 |
0.00164 |
0.00014 |
0.00383 |
0.037 |
||||||||||||
|
9 |
2.43E-05 |
5.36E-05 |
0.00082 |
0.00011 |
0.00239 |
0.00456 |
0.00703 |
0.0275 |
0.00023 |
|||||||||||
|
10 |
6.54E-05 |
0.00021 |
0.00067 |
0.0009 |
0.00288 |
0.00182 |
0.02347 |
0.00741 |
0.17969 |
0.3817 |
||||||||||
|
11 |
3.18E-05 |
6.79E-05 |
0.00012 |
0.0022 |
0.00038 |
0.01004 |
0.00024 |
0.0196 |
0.022 |
0.36876 |
0.00227 |
|||||||||
|
12 |
3.69E-05 |
0.00017 |
0.00039 |
0.00071 |
0.0042 |
0.00334 |
0.01418 |
0.04306 |
0.10167 |
0.10037 |
0.95542 |
2.23239 |
||||||||
|
13 |
8.72E-05 |
7.79E-05 |
0.00013 |
0.00221 |
0.00252 |
0.0163 |
0.03593 |
0.00031 |
0.08639 |
0.1556 |
0.06104 |
0.59683 |
2.7885 |
|||||||
|
14 |
4.02E-05 |
0.0003 |
0.00029 |
0.00017 |
0.0002 |
0.0086 |
0.01004 |
0.06353 |
0.00488 |
0.51312 |
0.19725 |
1.06655 |
0.79233 |
0.22017 |
||||||
|
15 |
4.19E-05 |
9.22E-05 |
0.0014 |
0.00137 |
0.00022 |
0.02037 |
0.02625 |
0.01376 |
0.17512 |
0.06214 |
0.00509 |
1.518 |
1.41711 |
0.66218 |
26.6606 |
|||||
|
16 |
0.00011 |
0.00022 |
0.0011 |
0.00325 |
0.01014 |
0.01641 |
0.01558 |
0.11907 |
0.15756 |
0.46296 |
1.05822 |
0.04907 |
4.55154 |
0.04737 |
3.8103 |
0.18313 |
||||
|
17 |
5.03E-05 |
0.0001 |
0.00018 |
0.00102 |
0.00128 |
0.00032 |
0.00131 |
0.03854 |
0.08987 |
0.55444 |
0.01104 |
1.84682 |
0.00069 |
6.30492 |
1.23102 |
9.21147 |
36.5825 |
|||
|
18 |
5.45E-05 |
0.00039 |
0.0006 |
0.0031 |
0.01002 |
0.00943 |
0.04745 |
0.06114 |
0.00051 |
0.12431 |
1.56661 |
2.49139 |
2.56945 |
15.9228 |
30.2238 |
75.4171 |
119.804 |
174.01 |
||
|
19 |
0.00013 |
0.00012 |
0.0002 |
0.00024 |
0.00066 |
0.00356 |
0.03514 |
0.02003 |
0.00118 |
0.03656 |
0.16968 |
0.19098 |
6.33285 |
0.26802 |
1.19555 |
56.6678 |
16.8956 |
72.375 |
0.00111 |
|
|
20 |
5.87E-05 |
0.00028 |
0.00042 |
0.00185 |
0.00192 |
0.01873 |
0.01003 |
0.00114 |
0.12379 |
0.02564 |
0.16839 |
2.80882 |
4.00948 |
12.8724 |
5.29796 |
0.9085 |
0.21089 |
284.89 |
179.703 |
1605.01 |
此外，雖然實驗發現各行元素都depend on 上一行的結果，但是如何決定第一行的排列方示並沒有有效率的決定方式，目前也還找不出由小的盤面來組合出大盤面的方法。所以如何解出大的盤面，仍是需要進一步努力的方向。
四、結論
目前發現的點燈演算法，是判斷一個燈的四周圍加上自己共五個燈被點的次數是否為奇數。而每個燈都只有”點與不點”兩種狀態。而在程式設計上，在決定一個燈是該點或不該點時，是以上一行的元素做為參考依據。
以上述的演算法，我們將它推廣至1 to 20的任意矩型盤面，發現所有盤面都至少有一組解法，而且大部份的解法都具有對稱性，只是可能是左右對稱或是對角對稱，或是完全對稱，也有不對稱的解法。而且小盤面的解法和大盤面在直觀上沒有絕對的關係。但似乎可以發現解答的個數具有規律性。
目前發現解答的個數具有規律性，這是由於解答盤面具有對稱性，所以解答的個數會出現2n的情況，是否可以去除對稱的解，然後歸納出真正的規律性。然後再試圖證明點燈遊戲是否具有無解之盤面。此外，如何找出更快的點燈演算法，讓大的盤面也能在短時間之內找出解答，也是未來需要再研究的目標，可能可以依點燈法的對稱性及解法針對每一行元素的相依性來尋找更好的點燈法。這仍有待未來研究者之努力。
五、參考文獻
Grimaldi Ralph P. (1994). Discrete and combinatorial mathematics : an applied introduction. 3rd ed.
Ronald E. Walpole & Raymond H. Myers (1993). Probability and Statistics for Engineers and Scientists 5th Edition by Prentice-Hall, Inc.
Wackerly & Mendenhall & Scheaffer (1996). Mathematical Statistics with Applications 5th Edition by Wadsworth Publishing Company.
David Kincaid & Ward Cheney (1996). Numeriacl analysis : mathematics of scientific computing. 2nd ed.
Harry R. Lewis & Christos H. Papadimitriou (1998). Elements of the theory of computation. 2nd ed.
Neapolitan & Naimipour (1996). Foundations of algorithms by D. C. Heath and Company
Horowitz & Sahni (1994). Fundamentals of Data Structures in Pascal 4th Edition by Computer Science Press
Gilbert Strang (1988). Linear Algebra and Its Applications 3rd Edition by Harcourt Brace Jovanovich, Inc.
冼鏡光 (1990). : 名題精選百則 技巧篇 - 使用C語言。格致圖書公司。