緣起
學生時，家中有人帶回木製的華容道，曾經試著要解開它，開局應該是"橫刀立馬"(如圖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)。
參考資料
|
