期刊目錄列表 - 44卷第1.2期(1999) - 【數理與科技類】44(1) 四月刊
Directory
利用電腦探討中國古代益智遊戲--「華容道」之解法
作者:魏仲良、林順喜(國立臺灣師範大學資訊教育研究所）
卷期：44卷第1期
日期：1999年4月
頁碼：43-61
DOI：10.6301/JNTNU.1999.44(1).04
摘要：
在本文中，我們嘗試設計演算法，利用電腦找出中國古代流傳下來的益智遊戲-「華容道」的最少步數，以驗證前人資料上所記載的最少步數是否正確。此遊戲中許多盤面之解答的移動步數超過100步，因此不能直接用暴力法搜尋，目前文獻上尚未見到電腦之解法，只有一些人為的解法有記錄，也有一些程式將這些人為的、不是最佳的解法作展示。因此我們構思如何解決此困難之問題。在此論文中，我們發展了一些技術，目標是求出完全的最佳解，並實際撰寫程式測試，要求在可容忍的時間內解出。程式的執行結果與先前得到的前人資料有所出入，有些與資料記載吻合，有的則較記錄為多，還有一些比資料上的少上三至五步之多。驗證了一下程式輸入到檔案的最佳解，發現程式所求得比資料記載還要少的結果應是正確的。至於程式求得較資料為多的部分，可能是前人的文獻資料有誤，因為資料上只記載著各盤面最少步數的解題記錄，並無參考的解法。
關鍵詞：遊戲樹、二元蒐集樹、暴力法
《詳全文》
Journal directory listing - Volume 44 (1999) - Mathematics, Science & Technology【44(1)】April
Directory
Use Computers to Study the Solutions of the Chinese Game "Hua Rong Daw"
Author: Chun-Ling Wei, Shun-Shii Lin(Department of Information and Computer Education, National Taiwan Normal University)
Vol.&No.：Vol. 44, No. 1
Date：April 1999
Pages：43-61
DOI：10.6301/JNTNU.1999.44(1).04
Abstract：
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.
Keywords：Game tree, Binary search tree, Brute force approach