華容道基本上其棋盤為橫四格縱五格的盤面，曹操為占四格的 2x2的正方形棋子；占兩格的為五虎將的關(guān)羽、張飛、趙雲(yún)、馬超與黃忠，其中只有關(guān)羽橫兩格，其餘四將均為豎兩格；還有四個(gè)各占一格的兵(如圖一)。所以在遊戲的時(shí)候，只能利用盤面上留下的兩個(gè)空格來移動(dòng)棋子，只要想辦法將曹操移到鄰接曹營上方的正中央的位置，即表示我們已成功讓曹操逃回曹營，遊戲至此於是結(jié)束。移動(dòng)的步數(shù)愈少愈好。而在移動(dòng)的過程中我們可以發(fā)現(xiàn)，關(guān)羽跟曹操不能在同一排，關(guān)羽必須要橫讓，曹操才有可能通過向下走，這正好符合了三國演義中的情節(jié)，所以這項(xiàng)遊戲又被稱為「捉放曹」。除了上述標(biāo)準(zhǔn)的盤面之外，橫擺的五虎將除了關(guān)羽之外，也可以將其他四將橫擺，使得盤面有更多變化，更富挑戰(zhàn)性。

在正式開始寫程式求解之前，我們先利用目前已知的資料。華容道的棋盤為橫四格縱五格，為了辨別棋子在棋盤上的位置，先對(duì)棋盤上的每個(gè)格子編號(hào)：左上角為 0，右下角為19，共二十個(gè)格子(表一)。為了識(shí)別每顆棋子，我們也將棋子加以編號(hào)：曹操為1號(hào)，五虎將給予2至6的編號(hào)，剩下四個(gè)兵則編為7至10號(hào)，而以0表示空白(表二)。最後，以棋子的長寬分類，共可分為四類：第一類為2x2大小，第二類為2x1，第三類1x2，而第四類則為1x1(表三)。

在每個(gè)盤面要尋找下一步該怎麼走，若檢查每顆棋子可以走的路，棋盤上共有十顆棋子，則十顆棋子都要檢查，而且大部份的棋子可能都無法移動(dòng)。為了減少麻煩，改由空白格下手。由於盤面上只會(huì)有兩個(gè)空格，只要檢查空格周圍的棋子是否能往空格移動(dòng)，如此即可減少許多不必要的判斷，而加快搜尋的速度。為了推知空格的位置，首先將棋盤上所有的格子都先填入 0，再依棋子的位置以及種類，將棋子的編號(hào)填入棋盤內(nèi)，填完之後，即可得知空格的所在。舉例說明，下面是我們將棋子編號(hào)填入「橫刀立馬」盤面之後所得的結(jié)果(表四)：

由於我們的目的在尋找由給定盤面開始，最終將曹操移動(dòng)至曹營上方中央的位置最少需要多少步，因此第一個(gè)念頭即是利用 BFS(Breadth-First Search)配合Branch and Bound的方式求解，如此，第一個(gè)找到的解一定是最佳解。但是，利用BFS需要額外的空間來存放等待著要被展開盤面的Queue，因此，當(dāng)我們要展開的深度很深時(shí)(例如100層以上)，需要耗費(fèi)的空間就很驚人了。所以改而採用DFS(Depth-First Search)來展開Game Tree。為了加快DFS的效率，每當(dāng)找到一個(gè)解時(shí)，則立即記錄下至目前為止的最少步數(shù)，倘若目前步數(shù)超過最少步數(shù)則不繼續(xù)往下展開；除此之外，另外用Binary Search Tree記錄已經(jīng)走過的盤面(這些盤面有一次序值，如下所述)，以及先前走到此盤面時(shí)的步數(shù)：第一步，先將同一類棋子的位置加以排序，例如圖三「三軍聯(lián)防」盤面中，十顆棋子的位置如表五所示：

原則上，在展開一個(gè)盤面之前，會(huì)先自 Binary Search Tree中搜尋該盤面是否已經(jīng)展開過，若無，則繼續(xù)展開，若有，則表示此盤面先前已經(jīng)走過，所以不展開此重複的盤面，但是除了一種特殊的情況：雖然先前已經(jīng)走過此盤面，但當(dāng)時(shí)的步數(shù)比目前走到此的步數(shù)還多，則得重新由此盤面展開一次，並更新Binary Search Tree裡所記錄盤面的步數(shù)。目前的步數(shù)較少，表示此時(shí)由起始盤面至此盤面的解較先前走到此盤面時(shí)的解為佳，重新展開的目的則在於更新Binary Search Tree裡的步數(shù)記錄。圖四顯示啟始盤面為「 橫刀立馬」的展開情況。

計(jì)算步數(shù)的方式有兩種：第一種為只要棋子移動(dòng)一格就算一步，第二種狀況則為若兩個(gè)空格相鄰，棋子得以連續(xù)移動(dòng)兩格只算一步。依據(jù)文獻(xiàn)上的記錄推測(cè)，前人文獻(xiàn)計(jì)算步數(shù)的方法應(yīng)為後者，故本程式亦採用後者為計(jì)算步數(shù)的方式。程式所得到的結(jié)果，與先前得到的文獻(xiàn)資料比較後 ,有以下三種狀況(表六)。

與前人資料相符者
盤面名稱	起始盤面	資料數(shù)據(jù)	執(zhí)行結(jié)果	盤面名稱	起始盤面	資料數(shù)據(jù)	執(zhí)行結(jié)果
左右佈兵	O##O O##O H[]H HHHH HH	34步	34步	橫刀立馬	H##H H##H H[]H HOOH OO	81步	81步
水洩不通	O##H O##H [][] [][] OO	80步	80步
步數(shù)較前人資料記錄少者
三軍聯(lián)防	##HH ##HH [][] O[]O OO	74步	69步	四路進(jìn)兵	##OH ##OH OO [][] [][]	67步	65步
步數(shù)較前人資料記錄多者
插翅難飛	H##O H##O []OO H[]H HH	62步	63步 </ 分享到： 華容道游戲 | RSS收藏閱讀軟件最近更新 2007-01-19 13:30 瀏覽 300 評(píng)論(0) 相關(guān)推薦 評(píng)論 發(fā)表評(píng)論 您還沒有登錄,請(qǐng)您登錄后再發(fā)表評(píng)論 wapysun 瀏覽: 4880685 次 性別: 來自: 杭州 最近訪客 更多訪客>> first_class Lovefire_ rickqin px915 文章分類 全部博客 (27229) 軟件技術(shù) (2) 編程開發(fā) (0) 生活休閑 (2) 安卓開發(fā) (0) 數(shù)據(jù)庫 (0) 社區(qū)版塊 我的資訊 (0) 我的論壇 (0) 我的問答 (0) 存檔分類 2012-06 (77) 2012-05 (587) 2012-04 (177) 更多存檔... 最新評(píng)論 lehehe ： wifi,ip定位,google似乎不能返回?cái)?shù)據(jù)了,現(xiàn)在我們都 ... Google WIFI/IP定位技術(shù)初探 wx_hello ： 求噴碼器軟件； java程序向噴碼器輸送字符，噴碼器噴出來。 ... RS232串口 小記 sdt1005 ： 引用[list][url][flash=200,200][fl ... GROUP BY 子句及其擴(kuò)展 a465492689 ： 太有用了，謝謝分享！ Oracle 表空間 yinren13 ： 支持視頻會(huì)議！！我們公司現(xiàn)在就在用視頻會(huì)議turbomeeti ... 視頻會(huì)議 聲明：ITeye文章版權(quán)屬于作者，受法律保護(hù)。沒有作者書面許可不得轉(zhuǎn)載。若作者同意轉(zhuǎn)載，必須以超鏈接形式標(biāo)明文章原始出處和作者。 ? 2003-2015 ITeye.com. All rights reserved. [ 京ICP證110151號(hào) 京公網(wǎng)安備110105010620 ]

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