" 點燈遊戲 494512243 資工二乙 陳宣筑壹、前言
「點燈遊戲」，就是在一個方形的盤面中，有N行M列的燈排成長方形，最普遍的玩法就是把25盞燈排成5列5行(表格1)，每一盞燈都有一個開關，每點燃(表格2)或關閉一盞燈都會影響到他和他的上、下、左、右共五盞燈的狀態(亮的變暗，暗的變亮)。遊戲者以控制燈的開關把所有燈都點亮則完成遊戲。
平常我們玩這個遊戲的時候就是一直去嘗試不同的方式點然後找解，但是人腦的記憶力有限，有些地方我們會重複做了但卻忘記了，如此便消耗了不少時間。以5*5的點燈盤面來說會有2^25=33,554,432種情形。如果用來解其他更大的盤面，那會是一個天文數字，所以一個有效率的解方式必須要有的！！
如果我們把所有的燈分成”點”與”不點”兩種狀態，點某盞燈奇數次之後的結果都是一樣的；點某盞燈偶數次 和沒有點是一樣的。所以我們可以用 1 和 0 來記錄每一盞燈點與不點的狀態， 再經由記錄狀態來判斷目前的點燈盤面是否已將所有的燈點亮。
「Depend on 上一行」的方法是在找資料的時候看到的，與其慢慢的一個一個帶，這個方法只需要去尋找第一列的點燈方式然後利用Backtracking的方式判斷是否會有解，當第一列被決定之後，其餘各列剩下的燈也被決定了，如此一來5*5的點燈盤面便只須要去判斷2^5=32種情形。同理，N*M(N<=M)的盤面也只需用2^N種情形判斷就可以了。
以下為解法:
首先產生一個5*5點燈盤面，用搜尋的方式一格一格填入0(沒點到)與1(有點到)尋找可能的方法。
因為每點一盞燈會影響的只有陣列中上一列下一列和自己這一列，所以在利用遞迴產生0與1時，產生到第二列的元素時，就可以檢查該元素上一列所產生的0與1符不符合周圍奇數點燈的條件。如果不合，就退回去再產生上一列的結果。如果符合就再產生下一列，即在第n列檢查第n-1列的元素。 而當程式到了產生最後一個元素時，檢查第n列(本例中n就等於5)，如果也合理，此盤面即為所求。 如果第一列都填0，第二列依上述的說明，為滿足讓第一列元素四周都有奇數的燈被點，勢必都要填入1。 依上述的方法再往下填入，會發現填到B5時，為了讓B4四週有奇數點，所以填1，但這樣卻造成A5四周有偶數個燈被點，所以此點燈法無效，盤面需backtracking重新產生解法ex:10100不是5*5盤面的解參、結論
目前的結論:
在一個 n * m ( n 行 m 列，n <= m ) 的盤面中，只需要考慮第一列開關的 2^N 種不同之開啟 或關閉的設定情況即可。這些不同的設定情況可以用 n 個 1 或 0 來記錄。
現在這份報告在做動作的依據是以前一列的燈為參考依據，且發現使用這種方法在N<=20的狀況下皆有解，並且部份具有對稱性，雖然還沒有找到具有規律性的解法，但是已經省下不少的時間。
未來的發展:
其實點燈遊戲的解法還有很多種，像是”拼圖法”、”骨牌法”、”鏡射”，其實拼圖法是我原本想要研究的題目，但是因為知識上及時間上的不足無法完成，或許拼圖法在解盤面更大的點燈遊戲會比現再這個方法好用且方便也不一定。肆、心得
原本想利用演算法的分析來尋找是否有固定的規則來解這個問題，但是深入了解後發現發明這個遊戲的人真厲害，隨著點燈盤面格式的不同，發現以各行元素都depend on上一列的結果在20*20以下的盤面不管是M*N或N*N都有解，而且有些只有唯一解，但是有些又有超多組解，根本就很難以某種固定的規格形式去求出解。但是這個方法和土法煉鋼去找解的方法比較起來，實在有效率很多。
伍、 參考資料
http://www.shes.hcc.edu.tw/~oddest/math172.htm 怎樣來點燈
http://www.shes.hcc.edu.tw/~oddest/math171.htm
http://iicm.cc.ntu.edu.tw/communication/c1_4/page03.html [@more@]"
