
緣起
學生時,家中有人帶回木製的華容道,曾經試著要解開它,開局應該是"橫刀立馬"(如圖1),不過沒有成功,當時學校作業剛好寫過求解"智慧拼盤"的程式,想說就直接改成求解華容道吧!經過修改後真的成功解出,不過不是最佳解。當時大哥還很有耐心的印出過程,並試著去除重覆的部份,去除重覆是可利用電腦完成的,但當時已不想花時間做更深入的研究了,其實利用"廣度優先搜尋法"就可找到最佳解了
(參1),容後說明。

|
華容道:橫刀立馬 (圖1)(註1)
|
遊戲的來源與玩法
遊戲取名自《三國演義》中,曹操敗走華容道,關雲長義釋曹操的故事。但是這個遊戲的起源,並不是一般人認為的
“中國最古老的遊戲之一”。華容道遊戲的歷史應該很短,有資料可查的是,英國人 John Harold Fleming
在1932年申請了專利,並且還附上橫刀立馬的解法(參2)(參3)。而法國也有 "紅鬃烈馬"(Red Donkey) 遊戲,(圖3)(參4),
日本則是"箱入り娘" (圖4) 及 "將棋版本的華容道" (圖5) 。
華容道(Klotski)是一種滑塊類遊戲,在一個方形盤中(4x5的方格尺寸)放置了大小不同的方塊,目標是在只滑動方塊而不從棋盤中拿走的情況下,將最大的一塊(2X2的方塊)移到下方有一個兩方格邊長的出口。
(參3)
各式華容道遊戲盤

|

|
木製華容道 - 中國 (圖2)
|
紅鬃烈馬(Ane Rouge ) - 法國 (圖3)
|

|

|
箱入り娘 - 日本 (圖4)
|
將棋版本的華容道 - 日本 (圖5) |
遊戲技巧
早年有位中國數學教育家 - 許蒓舫先生,於1952年,在《數學漫談》書中對這個遊戲作了分析,總結出8條規則。(參5)
這8條可以歸納為以下4點:(參6, 參7)
1. 四個小兵中,必須兩兩常在一起,不要分開。
2. 曹操、關羽等大將移動時,前面應有兩個小兵開路。
3. 曹操移動時後面還應有兩個小兵追趕。
4. 以下三種狀況,其中各塊都可局部(不妨礙其他地方)任意移動。
(1)
|
(2)
|
(3)
|
|
|
|
一大將,兩小兵,可任意迴旋
|
三大將,兩小兵,可任意迴旋
|
曹操, 關羽, 及四小兵,可任意迴旋
(曹操也可換成兩大將)
|
* 關於上述三種狀況可參考 華容道遊戲 Level 3-40,此關左下邊符合狀況1,右邊符合狀況2,最後過關動作符合狀況3。
華容道與程式
華容道的求解過程,除了找到答案外,更要找出最少步數,若能列出每一步驟所有可能狀態,並去除先前已出現過的狀態,如此一步步列出,直到找到解答即為最佳解,可嘗試列出所有可能 (圖6);但幾乎很難以人工完成,為達此目的可利用"廣度優先搜尋法"來實作。

|
試著列出華容道所有可能步驟 - 以最少步數為 3步的佈局為例 (圖6)
|
另外程式中使用 HashMap 來判斷狀態是否重覆,HashMap是一種以雜湊方式去實作的對應,每個 key 對應到一組 value
(參8)。所以需要將每個華容道的狀態轉換成一個 Key 值,用來判斷是否已重覆出現,方法如下:
為了加快比對的速度,希望Key值是一個整數,而華容道的方塊形式有 1X1、 2X1、 1X2、 2X2 及 空格(1X1) 共 5 種,
若以二進位表示需 3-bits,而盤的大小為 4X5 的 20 個方格,即每個方格以 3-bits 表示需 60-bits (20X3 = 60),所以可以
用 64-bits 整數表示一個盤的狀態。
但 JavaScript 的數字是 64-bits 的浮點數 (floating point),而最大整數只能放 52-bits (參9)。所以用 60-bits 表示一個 Key值,
是無法放入 JavaScript 的數字中。不過遊戲中 2X2 的方塊只會有一個,所以改為 1X1、2X1、1X2 及 空格 (1X1) 4 種,可
用 2-bits 表示,再記錄 2X2 左上角的位置用
4-bits 表示(0 - 14), 共(5X4 - 4) X 2 + 4 = 36 bits,如此就可放入一個數字中。
以圖例說明:
圖例1:

|
(圖7)
|
圖例2:

|
(圖8)
|
利用上述的 Key
值,經雜湊函數(Hash Function) 轉成一索引值(index),將 key-value 放入連結串列 (Linked List) (參8)。
若新狀態的 Key 值,經由雜湊函數求出的索引值內已有 key-value 存在,就必需與同一索引值中所有連結串列的 Key 值比較,
若没有相同 Key 值,表示新狀態未出現過,就加到連結串列內,反之則表示,之前已出現過相同狀態,必需捨棄 (圖9) 。

|
華容道 HashMap 的方式 (圖9)
|
求解華容道
一般華容道最少步數的算法,並不是每移動一格算一步,而是移動同一方塊不管幾格均視為一步,另外有些電腦遊戲於
直線移動多格算一步,但有轉彎另外算一步 (參10)。
所以程式有加入參數,可支援三種不同模式:(1) 移動同一方塊視為一步 (2) 直線移動視為一步 (3) 每移動一格算一步
程式中的佈局取自: (1) 發芽網 (JavaScript Game) (參11) (2) unblock it 2 (Flash Game) (參10) (3) 出路 (Android Game) (參12)
華容道遊戲
華容道遊戲是以 JavaScript 寫成,動態動作是以 KineticJS javascript framework 完成,程式中會記錄過關資訊到瀏覽器的
LocalStorage,但不能永遠保存,另提供使用者自行定義新佈局,同樣放於 LocalStorage (註2),若造成資料遺失概不負責 !
如果希望保留所有過關資料,推薦使用"發芽網"(參11);網站經註冊後,應可保留過關紀錄於伺服器內。
目前於 IE 10(10.0.9200.16660),Firefox 23.0 及 Chrome 28.0.1500.95 m 中均能正常運作(註3),但由於遊戲中的展示模式
需利用 JavaScript 引擎計算過關步驟,Firefox v22 以前的版本求解非常慢(註4),以 "橫刀立馬" 為例:
|
Firefox v21 及之前版本 |
約 4.0 秒 |
Firefox v23 |
約 0.20 秒 |
IE 10 |
約 0.15 秒 |
Chrome 28 |
約 0.15 秒 |
|
IE10 與 Chrome 速度差不多,但以 Chrome 較順暢!
遊戲約收集了 480 個佈局,含 發芽網、unblock it 2、出路 及自創關,並去除重覆佈局,相信只有超人才能全部玩完。
程式原始碼
GitHub: https://github.com/SimonHung/Klotski
Simon's GitHub Projects: https://simonhung.github.io
【後記】
(1) 原本"橫刀立馬",一直無法解開,看過上面的遊戲技巧說明後,居然有一次解開了,不過還是要好幾百步,
若經華容道小遊戲的提點,可降至約一百多步 (還是很爛~ 哈哈哈...)。
(2) 原本想加入自動產生關卡的功能,不過已經沒力了,希望下個遊戲可加入此功能!
【註解】
(註1) Chrome 29,點選華容道遊戲時,若有聲無影,請在連結處按右鍵選"在分頁中開啟連結",應該可正常使用 (參18)。
(註2) LocalStorage 為 JavaScript 的 local cache 不同的瀏覽器可能需要不同的設定才能開啟。
(註3) 測試環境為 Windows 7,64-bits,CPU:Intel Core2 Duo P8700 @ 2.53GHz,RAM:4GB。
(註4) FireFox v22 以後使用 OdinMonkey;新的 Module for JavaScript Engine (參13)。
參考資料
|