華容道基本上其棋盤(pán)為橫四格縱五格的盤(pán)面，曹操為占四格的 2x2的正方形棋子；占兩格的為五虎將的關(guān)羽、張飛、趙雲(yún)、馬超與黃忠，其中只有關(guān)羽橫兩格，其餘四將均為豎兩格；還有四個(gè)各占一格的兵(如圖一)。所以在遊戲的時(shí)候，只能利用盤(pán)面上留下的兩個(gè)空格來(lái)移動(dòng)棋子，只要想辦法將曹操移到鄰接曹營(yíng)上方的正中央的位置，即表示我們已成功讓曹操逃回曹營(yíng)，遊戲至此於是結(jié)束。移動(dòng)的步數(shù)愈少愈好。而在移動(dòng)的過(guò)程中我們可以發(fā)現(xiàn)，關(guān)羽跟曹操不能在同一排，關(guān)羽必須要橫讓?zhuān)懿俨庞锌赡芡ㄟ^(guò)向下走，這正好符合了三國(guó)演義中的情節(jié)，所以這項(xiàng)遊戲又被稱(chēng)為「捉放曹」。除了上述標(biāo)準(zhǔn)的盤(pán)面之外，橫擺的五虎將除了關(guān)羽之外，也可以將其他四將橫擺，使得盤(pán)面有更多變化，更富挑戰(zhàn)性。
在正式開(kāi)始寫(xiě)程式求解之前，我們先利用目前已知的資料。華容道的棋盤(pán)為橫四格縱五格，為了辨別棋子在棋盤(pán)上的位置，先對(duì)棋盤(pán)上的每個(gè)格子編號(hào)：左上角為 0，右下角為19，共二十個(gè)格子(表一)。為了識(shí)別每顆棋子，我們也將棋子加以編號(hào)：曹操為1號(hào)，五虎將給予2至6的編號(hào)，剩下四個(gè)兵則編為7至10號(hào)，而以0表示空白(表二)。最後，以棋子的長(zhǎng)寬分類(lèi)，共可分為四類(lèi)：第一類(lèi)為2x2大小，第二類(lèi)為2x1，第三類(lèi)1x2，而第四類(lèi)則為1x1(表三)。
在每個(gè)盤(pán)面要尋找下一步該怎麼走，若檢查每顆棋子可以走的路，棋盤(pán)上共有十顆棋子，則十顆棋子都要檢查，而且大部份的棋子可能都無(wú)法移動(dòng)。為了減少麻煩，改由空白格下手。由於盤(pán)面上只會(huì)有兩個(gè)空格，只要檢查空格周?chē)钠遄邮欠衲芡崭褚苿?dòng)，如此即可減少許多不必要的判斷，而加快搜尋的速度。為了推知空格的位置，首先將棋盤(pán)上所有的格子都先填入 0，再依棋子的位置以及種類(lèi)，將棋子的編號(hào)填入棋盤(pán)內(nèi)，填完之後，即可得知空格的所在。舉例說(shuō)明，下面是我們將棋子編號(hào)填入「橫刀立馬」盤(pán)面之後所得的結(jié)果(表四)：
由此可以得知兩個(gè)空格的位置分別為 17與18。接著則分別判斷每個(gè)空格上下左右四個(gè)方向緊鄰的棋子能否往空格移動(dòng)，若可，更動(dòng)該棋子的位置後則可得到新的盤(pán)面。
由於我們的目的在尋找由給定盤(pán)面開(kāi)始，最終將曹操移動(dòng)至曹營(yíng)上方中央的位置最少需要多少步，因此第一個(gè)念頭即是利用 BFS(Breadth-First Search)配合Branch and Bound的方式求解，如此，第一個(gè)找到的解一定是最佳解。但是，利用BFS需要額外的空間來(lái)存放等待著要被展開(kāi)盤(pán)面的Queue，因此，當(dāng)我們要展開(kāi)的深度很深時(shí)(例如100層以上)，需要耗費(fèi)的空間就很驚人了。所以改而採(cǎi)用DFS(Depth-First Search)來(lái)展開(kāi)Game Tree。為了加快DFS的效率，每當(dāng)找到一個(gè)解時(shí)，則立即記錄下至目前為止的最少步數(shù)，倘若目前步數(shù)超過(guò)最少步數(shù)則不繼續(xù)往下展開(kāi)；除此之外，另外用Binary Search Tree記錄已經(jīng)走過(guò)的盤(pán)面(這些盤(pán)面有一次序值，如下所述)，以及先前走到此盤(pán)面時(shí)的步數(shù)：第一步，先將同一類(lèi)棋子的位置加以排序，例如圖三「三軍聯(lián)防」盤(pán)面中，十顆棋子的位置如表五所示：
原則上，在展開(kāi)一個(gè)盤(pán)面之前，會(huì)先自 Binary Search Tree中搜尋該盤(pán)面是否已經(jīng)展開(kāi)過(guò)，若無(wú)，則繼續(xù)展開(kāi)，若有，則表示此盤(pán)面先前已經(jīng)走過(guò)，所以不展開(kāi)此重複的盤(pán)面，但是除了一種特殊的情況：雖然先前已經(jīng)走過(guò)此盤(pán)面，但當(dāng)時(shí)的步數(shù)比目前走到此的步數(shù)還多，則得重新由此盤(pán)面展開(kāi)一次，並更新Binary Search Tree裡所記錄盤(pán)面的步數(shù)。目前的步數(shù)較少，表示此時(shí)由起始盤(pán)面至此盤(pán)面的解較先前走到此盤(pán)面時(shí)的解為佳，重新展開(kāi)的目的則在於更新Binary Search Tree裡的步數(shù)記錄。圖四顯示啟始盤(pán)面為「 橫刀立馬」的展開(kāi)情況。
|
盤(pán)面名稱(chēng)
|
啟始盤(pán)面
|
最少步數(shù)
|
展開(kāi)盤(pán)面總數(shù)
|
執(zhí)行時(shí)間
|
盤(pán)面名稱(chēng)
|
啟始盤(pán)面
|
最少步數(shù)
|
展開(kāi)盤(pán)面總數(shù)
|
執(zhí)行時(shí)間
|
|
左右佈兵
(又名兵臨曹營(yíng)
)
|
O##O
O##O
H[]H
HHHH
HH
|
34步
|
3859
|
71秒
|
層層設(shè)防
|
H##H
H##H
O[]O
O[]O
[]
|
103步
|
30375
|
1474秒
|
|
橫刀立馬
|
H##H
H##H
H[]H
HOOH
OO
|
81步
|
23853
|
1835秒
|
兵將聯(lián)防
|
O##O
H##H
H[]H
O[]O
[]
|
121步
|
36557
|
1127秒
|
|
將守角樓
|
H##H
H##H
O[]O
HOOH
HH
|
70步
|
23111
|
1660秒
|
四路進(jìn)兵
|
##OH
##OH
OO
[][]
[][]
|
65步
|
13753
|
1005秒
|
|
屯兵東路
|
##HH
##HH
[]OO
HHOO
HH
|
74步
|
20935
|
1245秒
|
比翼橫空
|
[]##
[]##
[][]
O OH
O OH
|
28步
|
5779
|
307秒
|
|
插翅難飛
|
H##O
H##O
[]OO
H[]H
HH
|
63步
|
42290
|
3023秒
|
夾道藏兵
|
##OH
##OH
[][]
[][]
OO
|
76步
|
13753
|
858秒
|
|
重重包圍
|
H##O
H##O
H[]H
H[]H
OO
|
74步
|
42271
|
2738秒
|
水洩不通
|
O##H
O##H
[][]
[][]
OO
|
80步
|
13600
|
813秒
|
|
雲(yún)遮霧障
|
H##H
H##H
H[]O
H[]O
OO
|
81步
|
42165
|
3080秒
|
將擋後路
|
[]##
[]##
[][]
[]OO
OO
|
21步
|
2761
|
137秒
|
|
守口如瓶
|
O##O
H##H
HH H
OH O
[][]
|
100步
|
43669
|
2483秒
|
前呼後擁
|
OO##
[]##
[][]
[][]
OO
|
22步
|
6234
|
173秒
|
|
三軍聯(lián)防
(又名交錯(cuò)堵道
)
|
##HH
##HH
[][]
O[]O
OO
|
69步
|
16227
|
1046秒
|
調(diào)兵遣將
|
##OO
##OO
[][]
[][]
[]
|
52步
|
5078
|
240秒
|
|
四將聯(lián)防
(又名四將連關(guān)
)
|
##[]
##[]
HH[]
HHOO
OO
|
40步
|
5476
|
126秒
|
巧過(guò)五關(guān)
|
O##O
O##O
[][]
[][]
[]
|
33步
|
6052
|
189秒
|
計(jì)算步數(shù)的方式有兩種：第一種為只要棋子移動(dòng)一格就算一步，第二種狀況則為若兩個(gè)空格相鄰，棋子得以連續(xù)移動(dòng)兩格只算一步。依據(jù)文獻(xiàn)上的記錄推測(cè)，前人文獻(xiàn)計(jì)算步數(shù)的方法應(yīng)為後者，故本程式亦採(cǎi)用後者為計(jì)算步數(shù)的方式。程式所得到的結(jié)果，與先前得到的文獻(xiàn)資料比較後 ,有以下三種狀況(表六)。
|
與前人資料相符者
|
|||||||
|
盤(pán)面名稱(chēng)
|
起始盤(pán)面
|
資料數(shù)據(jù)
|
執(zhí)行結(jié)果
|
盤(pán)面名稱(chēng)
|
起始盤(pán)面
|
資料數(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步
</
分享到：
發(fā)表評(píng)論
wapysun
最新評(píng)論
|
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
評(píng)論