利用電腦探討中國古代益智遊戲－－「華容道」之解法

Use Computers to Study the Solutions of the Chinese Game "Hua Rong Daw"

在本文中，我們嘗試設計演算法，利用電腦找出中國古代流傳下來的益智遊戲-「華容道」的最少步數，以驗證前人資料上所記載的最少步數是否正確。此遊戲中許多盤面之解答的移動步數超過100步，因此不能直接用暴力法搜尋，目前文獻上尚未見到電腦之解法，只有一些人為的解法有記錄，也有一些程式將這些人為的、不是最佳的解法作展示。因此我們構思如何解決此困難之問題。在此論文中，我們發展了一些技術，目標是求出完全的最佳解，並實際撰寫程式測試，要求在可容忍的時間內解出。程式的執行結果與先前得到的前人資料有所出入，有些與資料記載吻合，有的則較記錄為多，還有一些比資料上的少上三至五步之多。驗證了一下程式輸入到檔案的最佳解，發現程式所求得比資料記載還要少的結果應是正確的。至於程式求得較資料為多的部分，可能是前人的文獻資料有誤，因為資料上只記載著各盤面最少步數的解題記錄，並無參考的解法。

In this paper, we will design algorithms to derive the solutions for the Chinese game "Hua Rong Daw". In addition, we want to verify and compare these results with the previous literatures. Since many initial configurations of this game need more than 100 steps to reach the final configurations, we could not search the entire game tree with the "brute force" approach. Previously, there are no computer solutions for this hard problem, but there are many manual trials that are found in many documents. In this paper, we explore some techniques for totally solving this game. The results show that some previous results are not the optimal solutions. We also list our optimal solutions in this paper.