怎樣來點燈

| 第一次接觸 | 他山之石 | 磨刀霍霍 | 另類玩法 | 目前的一小步 | 請跨出一大步 |
第一次接觸
  • 你玩過這樣的遊戲嗎?
    1. 在一個方形的盤面中,有 n 行 m 列的燈排列成長方形。
    2. 一般的玩法 ( 也是最有挑戰性但又不致於太困難的玩法 ) 是把 25 盞燈排列成 5 列 5 行。
    3. 每一盞燈都附有一個開關,可以切換自己和上下左右共五盞燈的亮、暗(亮的變暗、暗的變亮)。
    4. 遊戲者可以開啟或關閉任何一盞燈的開關,以完成把所有燈都點亮的任務。
  • 第一次接觸點燈遊戲,你的感覺如何?會不會和尤怪一樣,東點一下、西點一下,摸不著頭緒?
他山之石
  • 花了一段時間的摸索嚐試之後,仍然掌握不到重點,心想:既然是資訊時代,就利用電腦網路來搜尋 別人的研究心得吧!或許可以得到一些啟發。
  • 首先以平日最慣常使用的奇摩來搜尋,為了不錯過任何可能的資訊,以 "點燈遊戲"一找,哇!共找到了兩百多個 相關的網頁,以同樣的理由,尤怪發揮刻苦耐勞的精神,一個個網頁點進去看,但都失望而出,發現所有的網頁 都是只擺了一個 Java Applet 的遊戲及極簡單的玩法說明,此外就什麼都沒了。
  • 在瀏覽過上百個網頁之後,終於找到了下面這個連結:
    http://iicm.cc.ntu.edu.tw/communication/c1_4/page03.html
    內容是:「一個有趣的益智遊戲「點燈」之電腦解法及分析」, 作者為國立臺灣師範大學資訊教育系的蔡明原及林順喜。(以下稱蔡文)
  • 由蔡文中尤怪得到了以下心得:
    1. 如果以盤面上某一盞燈的亮與不亮來思考,我們很難記住解題的過程,造成同一盞燈重覆被點, 非常沒有效率。
    2. 如果把所有的燈分成點與不點兩種狀態,點某盞燈奇數次之後的結果都是一樣的;點某盞燈偶數次 和沒有點是一樣的。
    3. 點亮一盞燈會影響上下左右及自己五盞燈,換句話說,每一盞燈受自己及上下左右五盞燈的影響, 如果這五盞燈裡,有奇數盞被點了,這盞燈就會亮,如果是偶數就不會亮。
    4. 先點某一盞燈和後點某一盞燈的結果並沒有任何不同,所以我們可以用 1 和 0 來記錄每一盞燈點與不點的狀態, 再經由記錄狀態來判斷目前的點燈盤面是否已將所有的燈點亮。
    5. 如果沒有目標的亂點,那麼一個 5 * 5 的盤面將有 2 25 = 33,554,432 種狀況,若採用更大的盤面, 那更是個天文數字,所以一定要使用有效率且簡便的方法。
    6. 作者提出的方法是只考慮第一列燈的狀況,因為當第一列決定之後,其餘各列所有的燈也被決定了。
    7. 現在問題被大大的簡化了,以 5 * 5 盤面而言,現在只要考慮 2 5 = 32 種狀況就好了。 若是 2 * 6 這一類的長方形盤面,只要選擇短邊來考慮,那麼要考慮的情況只有 2 2 = 4 種 狀況而已,出奇的簡單吧。
  • 哈!哈!也許你比尤怪聰明,但尤怪直到看完本篇文章之後,才發現尤怪確實被這個遊戲的發明者作弄了, 他成功的讓遊戲者把燈的亮、暗和開關的開、關混淆了,以致於摸不著頭緒。
磨刀霍霍
  • 當然是因為限於篇幅,蔡文中僅列出演算法及結果分析,對於想自己深入探討的人而言,幫助還是有限。 恰巧程式的撰寫是尤怪唯一比之常人稍可自傲的一點,所以就由尤怪來提供一些方便大家研究的工具吧!
  • 一盞燈的點與不點和一盞燈的亮與不亮還是容易叫人混淆,所以尤怪認為採用「開關的開與關」這個名詞來記錄 遊戲可能較佳,範例如下圖:當開關被設定成開啟時,以 1 記錄之,當開關被設定成關閉時,以 0 記錄之。 為了讓讀者更容易理解,尤怪也將在此記錄下每一盞燈的亮暗情況一併顯示在記錄右側。
    開關的設定狀態及燈炮的亮暗情形說明
    在 3 * 3 的盤面中,第一列的開關只有 2 3 = 8 種不同的設定狀況, 這是其中的一種;當我們逐一在 8 種狀況中作試誤後可發現:這是唯一有解的狀況。
    現在考慮第二列開關的設定,這時能影響第一列燈亮暗的開關只剩下該盞燈下方的開關了, 以左圖為例,第 2 列第 1 行的開關如果設定為開啟,將把第 1 列第 1 行的燈變暗, 而且第二列的其他開關並不能影響到此燈的亮暗。
    所以在考慮第二列開關的設定時,只要尋找第一列為暗的燈,把他下方的開關開啟即可。 其他的開關則不能開啟,第二列開關的設定因此被唯一決定了。
    現在考慮第三列開關的設定,為了將第二列的燈全部點亮,只能將第二列為暗的燈 下方之開關設定為開啟,而這恰好點亮了所有的燈。
    ( 圖 1 ) 3 * 3 盤面的解
  • 再以 4 * 4 的盤面來示範當第一列的開關設定後,其餘各列將受影響而唯一決定的事實:
    開關的設定狀態及燈炮的亮暗情形說明
    在 4 * 4 的盤面中,第一列的開關共有 2 4 = 16 種不同的設定狀況, 現在測試第一種:第一列的所有開關全部設定為關閉。
    現在考慮第二列開關的設定,這時能影響第一列燈亮暗的開關只剩下該盞燈下方的開關了, 所以為了使第一列的燈全部被點亮,只能把第二列的開關全部設定成開啟。
    現在考慮第三列開關的設定,因為第二列第 1、4 盞燈這時是暗的,所以第三列的第 1、4 個 開關必須被設定成開啟,而其他的開關則要關閉。
    現在考慮第四列開關的設定,同理,為了將第三列的燈全部點亮,第四列只能全部 設定為開啟,結果發現所有的燈恰巧全部被點亮了,所以這也是一種解法。
    ( 圖 2 ) 4 * 4 盤面的解
  • 4 * 4 盤面的解法並不是唯一的,下面是另一種解答:
    開關的設定狀態及燈炮的亮暗情形說明
    將第一列的第 2 個開關設定成開啟,其餘的開關全部設定為關閉。
    因為第一列的燈只剩第 4 盞是暗的,所以第二列的開關只有第 4 個要設定成開啟。
    因為第二列的燈只剩第 1 盞是暗的,所以第三列的開關只有第 1 個要設定成開啟。
    因為第三列的燈只剩第 3 盞是暗的,所以第四列的開關只有第 3 個要設定成開啟。 此時恰好把所有的燈點亮了,所以這也是一個解。
    ( 圖 3 ) 4 * 4 盤面的另一個解
  • 在一個 n * m ( n ≦ m ) 的盤面中,如果用 n * m 個 1 和 0 來記錄解法雖也可以,但是要佔用太多的篇幅, 既然第二列以後的開關受第一列開關的影響被唯一確定,那麼何不只記錄第一列開關的設定就好了呢?一般而言, 如此做並不會有太大問題,只是在判斷解法是否為全等時,必須多費一番手腳,但兩相權衡之下,尤怪還是決定 採用只記錄第一列的方式,所以圖 1 的解法就記錄成 (101);圖 2 及 圖 3 則記錄成 (0000) 及 (0010)。
  • 怎麼解要由人來思考,但計算、重覆的事還是電腦比較專長,下面這個小程式,可幫我們把指定 盤面的解法全部列出來,解之後的數字表示的是開關變換總數 ( 也就是需要點燈的次數 ):
    請列出 * 盤面的所有解---->
    ( 程式 1 )列出指定盤面所有解的程式
  • 有些人或許會像尤怪一樣,眼見為憑。是不是可以提供一個程式:「可依照第一列的開關設定,調整其餘各列的開關, 從而判斷該開關設定是否為盤面解法的程式」?當然可以,下面這個就是了:
    請判斷
    * 盤面的操作結果---->
    ( 程式 2 )列出指定盤面所有解的程式
  • 有了上面兩個工具之後,我們可以更深入的去探討點燈遊戲的解。首先,如果你有耐心的話,可以驗証一下蔡文中 所提到的:20 * 20 以下的盤面中都會有解的事實,但因為本程式採用的程式語言是 VBScript ,執行的速度比 編譯式的程式語言慢多了,所以當盤面太大時,可是真的要耐心等候哦!
  • 全等的解:
    1. 請利用程式 1 求 4 * 4 盤面的解,結果應該是有16個解:(0000)、(1000)、(0100)、(1100)、 (0010)、(1010)、(0110)、(1110)、(0001)、(1001)、(0101)、(1101)、(0011)、(1011)、(0111)、 (1111)。這在蔡文的「(表9) 1*1至20*20之矩型盤面解法總數統計」 中也可查到,是 16 個沒錯。
    2. 由前文,4 * 4 盤面的第一列開關設定情況僅有2 4 = 16 種狀況,意思就是:不管第一列 的開關怎麼設定,都可把燈全部點亮。
    3. 請再用程式 2 把 (0111) 這個解輸入,請電腦把完整的開關設定顯示出來,結果應如同下圖:
      開關的設定狀態及燈炮的亮暗情形說明
      請和 圖 2 (0000) 的解對照一下,這個解的開關設定其實只是將圖 2 的設定方式 向左旋轉 90度而已。
      ( 圖 4 ) 4 * 4 盤面的全等解
      相信你可以發現:這其實只是 (0000) 解法向左旋轉 90 度的結果,同理類推:(1111)、(1110) 也都可以 旋轉得出。
    4. 類似 4 * 4 盤面的解 (0000)、(0111)、(1111)、(1110), 其開關設定可以用旋轉、鏡射方式轉換者,我們稱這些解為全等的。
    5. 在一個 n * n 的盤面中,某一個解的全等解最多可有 8 個(含本身)。例如在 9 * 9 的盤面中, (011111111)、(111111110)、(000011110)、(011110000)、(111011001)、(100110111)、 (100010000)、(000010001) 都是全等的解。
    6. 在一個 n * m ( n ≠ m ) 的盤面中,某一個解的全等解最多可有 4 個(含本身)。例如在 5 * 7 的盤面中, (10000)、(00001)、(11010)、(01011) 都是全等的解。
  • 最佳解:
    1. 一個 n * m 的盤面中,可能有很多個非全等的不同解法,我們把其中需要變換開關設定次數最少的解, 稱為最佳解。
    2. 以 4 * 4 的盤面為例,從圖 2 及 圖 3 中可知: (0000)、(0010) 都是 4 * 4 盤面的解,但是 (0000)的開關變換總數 ( 也就是點燈的次數 ) 共需 10 次,而 (0010)的開關變換總數只需 4 次, 那麼何者為優,不是很明顯了嗎?請在程式 1 中求 4 * 4 盤面的所有解,可以看到其他解開關變換 數都不比 4 少,所以 (0000)為 4 * 4 盤面的最佳解。
    3. 對於任一個 n * m 的盤面,非全等的最佳解是不是唯一的呢?經尤怪檢視之後發現:不是。 例如在 3 * 5 的盤面中,(100)、(010) 都是開關變換總數等於 6 次的最佳解,但是這兩個解並不全等, 請利用程式 2 驗証即可。
另類玩法
  • 一般的點燈玩法是將燈由全暗點成全亮,尤怪在研究本問題當中,想到了另一種玩法:是不是可以由 某一種花式點成另一種花式?此時一般玩法的演算法是否可套用到這另類的玩法上呢?
  • 經尤怪的粗淺探討,在這另類的玩法之下,只需考慮第一列開關設定的演算法仍是正確可套用的。例如 下面這個遊戲是要由週圍全亮中間暗的花式點成中央全亮週圍暗的花式:
    另類玩法一例,由週圍全亮中間暗的花式點成中央全亮週圍暗的花式。
    這個玩法的解十分簡單,因為第一列的開關不管怎麼設定全都是正確的解。現在我們 採用第一列全部關閉的解法,那第二列自然要全部開啟,才能使第一列的燈變暗了!
    接著考慮第三列開關的設定,為了熄去第二列兩邊的亮燈而維持中央的亮燈, 一定要使第三列的開關兩旁的開啟而中央的關閉
    最後,為了熄去第三列兩邊的亮燈而點亮中央的暗燈, 一定要使第四列的開關全部開啟,而這恰好完成了指定的花式。
    ( 圖 5 ) 有解的另類玩法
  • 一般由全暗到全亮的玩法,任何 n * m 的盤面都是有解的,但在這另類的玩法之下,是不是由任一花式到 另一花式也全部有解呢?答案是否定的。例如下面這個遊戲是要由全暗點成中央的斜角為亮的花式:
    另類玩法一例,由全暗點成中央的斜角為亮的花式,這是無解的。
    ( 圖 6 ) 無解的另類玩法
目前的一小步
  • 在一個 n * m ( n 行 m 列,n ≦ m ) 的盤面中,只須考慮第一列開關的 2 n 種不同之開啟 或關閉的設定情況即可。這些不同的設定情況可以用 n 個 1 或 0 來記錄。 例如:在 2 * 4 的盤面中,共有 (00)、(01)、(10)、(11) 四種設定方式,而唯一的解是 (00)。
  • 如果是一般由全暗到全亮的玩法,任何 n * m 的盤面都是有解的,而且解法有時不只一種;當解法不唯一時, 我們稱將開關做最少變更的解法為最佳解,非全等的最佳解不一定是唯一的。
  • 如果是由某一種花式到另一種花式的玩法,則可能會有無解的情況發生。至於如何判斷是否有解,目前尚無具體方式。
  • 本網頁的所有程式都由 VBScript 程式撰寫而成,如果讀者有興趣研究或更改,請檢視網頁原始碼即可。
請跨出一大步
    對於本遊戲,尤怪認為讀者還有許多的研究空間:
  • 是否可找到更佳的演算法,可由 n * m 的盤面中馬上帶出解法,不必再逐一試誤?
  • 如何判定何種花式之間的轉換是有解的,何者是無解的?
參考資料
 
 
 
本網頁建置日期:91.12.09 | 最近更新日期:91.12.09  | 回上頁 | 回首頁 |