一. 游戲簡(jiǎn)介

華容道，古老的中國(guó)游戲，以其變化多端、百玩不厭的特點(diǎn)與魔方、獨(dú)立鉆石棋一起被國(guó)外智力專家并稱為“智力游戲界的三個(gè)不可思議”。它與七巧板、九連環(huán)等中國(guó)傳統(tǒng)益智玩具還有個(gè)代名詞叫作“中國(guó)的難題”。華容道游戲取自著名的三國(guó)故事，曹操在赤壁大戰(zhàn)中被劉備和孫權(quán)的“苦肉計(jì)”、“火燒連營(yíng)”打敗，被迫退逃到華容道，又遇上諸葛亮的伏兵，關(guān)羽為了報(bào)答曹操對(duì)他的恩情，明逼實(shí)讓，終于幫助曹操逃出了華容道。游戲就是依照“曹瞞兵敗走華容，正與關(guān)公狹路逢。只為當(dāng)初恩義重，放開(kāi)金鎖走蛟龍”這一故事情節(jié)，通過(guò)移動(dòng)各個(gè)棋子，幫助曹操?gòu)某跏嘉恢靡频狡灞P最下方中部，從出口逃走。不允許跨越棋子，還要設(shè)法用最少的步數(shù)把曹操移到出口。曹操逃出華容道的最大障礙是關(guān)羽，關(guān)羽立馬華容道，一夫當(dāng)關(guān)，萬(wàn)夫莫開(kāi)。關(guān)羽與曹操當(dāng)然是解開(kāi)這一游戲的關(guān)鍵。四個(gè)劉備軍兵是最靈活的，也最容易對(duì)付，如何發(fā)揮他們的作用也要充分考慮周全。“華容道”有一個(gè)帶二十個(gè)小方格的棋盤，代表華容道。棋盤下方有一個(gè)兩方格邊長(zhǎng)的出口，是供曹操逃走的。棋盤上共擺有十個(gè)大小不一樣的棋子，它們分別代表曹操、張飛、趙云、馬超、黃忠和關(guān)羽，還有四個(gè)卒?！叭A容道”有幾十種布陣方法，如“橫刀立馬”、“近在咫尺”、“過(guò)五關(guān)”、“水泄不通”、“小燕出巢”等等玩法。棋盤上僅有兩個(gè)小方格空著，玩法就是通過(guò)這兩個(gè)空格移動(dòng)棋子，用最少的步數(shù)把曹操移出華容道。這個(gè)玩具引起過(guò)許多人的興趣，大家都力圖把移動(dòng)的步數(shù)減到最少。

二. 華容道游戲的歷史

游戲華容道的故事來(lái)源是三國(guó)演義中關(guān)云長(zhǎng)義釋曹操。但是這個(gè)游戲的起源，卻不是一般人認(rèn)為的是“中國(guó)最古老的游戲之一”。實(shí)際上它的歷史可能很短。

姜長(zhǎng)英在他所著《科學(xué)思維鍛煉與消遣》中說(shuō)，“估計(jì)它的歷史只不過(guò)有幾十年。從前人的筆記中沒(méi)有發(fā)現(xiàn)有玩具華容道的記載?！苯壬约菏窃?943年夏第一次看到這個(gè)玩具。目前所見(jiàn)到關(guān)于華容道最早的文字記載就是姜先生1949年出版的《科學(xué)消遣》。

據(jù)西北工業(yè)大學(xué)林德寬教授說(shuō)，他在1938年在陜西省城固縣的鄉(xiāng)下見(jiàn)過(guò)小孩玩用紙片做的華容道。

20世紀(jì)50年代，蘇州師大的許莼舫先生的《趣味數(shù)學(xué)》詳細(xì)分析了華容道游戲，給出了100步的解法。

文革期間，華容道游戲已經(jīng)相當(dāng)流行。

2002年崔樂(lè)泉所著《忘憂清樂(lè)——古代游藝文化》中對(duì)中國(guó)古代種種游戲玩具作了介紹，其中有七巧板可九連環(huán)，卻沒(méi)有華容道。

由此可見(jiàn)，在沒(méi)有新的歷史資料發(fā)現(xiàn)之前，華容道的歷史不超過(guò)幾十年的說(shuō)法是可信的。

華容道游戲?qū)儆诨瑝K類游戲，就是在一定范圍內(nèi)，按照一定條件移動(dòng)一些稱作“塊”的東西，最后滿足一定的要求?；瑝K類游戲究其起源，最早的可以說(shuō)是中國(guó)古代的“重排九宮”。那應(yīng)該是產(chǎn)生于出現(xiàn)河圖洛書(shū)的時(shí)代，有數(shù)千年歷史。1865年，西方出現(xiàn)“重排十五”游戲，特別是薩姆.洛伊德在1878年推出“14－15”游戲，風(fēng)行一時(shí)。此后，各種各樣的滑塊類游戲不斷涌現(xiàn)。哈代（L.W.Hardy）發(fā)明三角旗游戲并在1909年取得專利。再往后，法國(guó)出現(xiàn)紅鬃烈馬游戲。可以設(shè)想，這個(gè)游戲傳到中國(guó)，本土化成為華容道游戲。

最早系統(tǒng)研究游戲華容道的是蘇州大學(xué)數(shù)學(xué)教授許莼舫先生。1952年，他在《數(shù)學(xué)漫談》中對(duì)這個(gè)游戲作了詳細(xì)的分析，總結(jié)出8條規(guī)則。這8條可以歸納為以下4點(diǎn)：

1，四個(gè)小兵必須兩兩在一起，不要分開(kāi)；

2，曹操，關(guān)羽，大將移動(dòng)時(shí)前面應(yīng)有兩個(gè)小兵開(kāi)路；

3，曹操移動(dòng)時(shí)后面還應(yīng)有兩個(gè)小兵追趕；

4，以下三種狀況，其中各塊都可局部（不妨礙其他地方）任意移動(dòng)。

在此基礎(chǔ)上，許莼舫提出了100步解法。下就是許先生的解法，可能由于初始狀況的不同，這里只需要98步。

后來(lái)，美國(guó)一個(gè)律師托馬斯.萊曼(Thomas B.Lenann)發(fā)現(xiàn)一個(gè)新的解法，由加德納公布在1964年3月《科學(xué)美國(guó)人》上，有81步，稱加德納解法。

游戲華容道有不同的開(kāi)局，根據(jù)5個(gè)矩形塊的放法分類，除了5個(gè)都豎放是步可能的以外，有一橫式，二橫式，三橫式，四橫式，五橫式。下面舉幾個(gè)例子。

研究華容道游戲，除了其歷史外，至少有以下幾個(gè)問(wèn)題：

1，有多少種開(kāi)局；

2，判斷有解；

3，給出最優(yōu)解；

4，計(jì)算機(jī)求解。

因此，華容道是個(gè)數(shù)學(xué)游戲,可以鍛煉人的思維，讓人的思維更活躍。

國(guó)內(nèi)國(guó)外都有一些華容道的愛(ài)好者研究者。姜長(zhǎng)英先生1985年發(fā)起組織“華容道研究會(huì)”，他們有了不少結(jié)果。特別是原北京工業(yè)學(xué)院副院長(zhǎng)齊堯的網(wǎng)絡(luò)研究，可以說(shuō)完全解決了華容道游戲方法。他研究了一橫式華容道的各種關(guān)鍵狀態(tài)共54圖，找出其間關(guān)系，畫(huà)出關(guān)系圖。于是任何一橫式華容道都可以經(jīng)少數(shù)幾步到達(dá)某一個(gè)關(guān)鍵狀態(tài)，其解法也就給出了。對(duì)二橫式，三橫式，四橫式，他也都畫(huà)出了關(guān)系圖。

用計(jì)算機(jī)解決華容道游戲， http://www.math.sdu.edu.cn/html/sxjm/examples/ex5.htm上有這樣的說(shuō)法：“筆者編制的軟件HRDE的貢獻(xiàn)是成功地實(shí)現(xiàn)了一種系統(tǒng)搜索 （Systematic searching）算法，它能在較短時(shí)間內(nèi)，對(duì)用戶擺放的任何一種布局判斷是否有解。如果有解，則解出它的最少步法。然后，它會(huì)在屏幕上用動(dòng)畫(huà)方式移動(dòng)棋子以顯示它的運(yùn)算方法。也可以用一連串的圖形來(lái)靜止地顯示每一步的走法，便于用戶仔細(xì)地觀察研究。一般情況下，在已經(jīng)很普及的IBM486計(jì)算機(jī)上解一道題僅需要一兩分鐘，在較慢的286計(jì)算機(jī)上則大約需要十幾分鐘。根據(jù)它的算法的原理可以肯定，它推導(dǎo)出的結(jié)果是絕對(duì)可信的。也就是說(shuō)，它所解出的走法一定是該布局的最少步法。 ”

華容道游戲又有很多發(fā)展，在國(guó)內(nèi)外產(chǎn)生了很多類似的游戲。如推箱子游戲。

推箱子游戲出現(xiàn)在計(jì)算機(jī)中最早起源于1994年臺(tái)灣省李果兆開(kāi)發(fā)的倉(cāng)庫(kù)世家，又名倉(cāng)庫(kù)番，箱子只可以推, 不可以拉, 而且一次只能推動(dòng)一個(gè)， 勝利條件就是把所有的箱子都推到目的地 。現(xiàn)在網(wǎng)上有很多種推箱子游戲。