華容道擺法(華容道擺法大全)

求華容道擺法

num=0 num=1 num=2 num=34 9 4 9 4 9 4 9 5 9 4 9 5 9 9 9 5 9 9 8 8 8 8 8 8 2 8 2 8 2 3 2 0 3 2 0 1 31 0 1 1 1 1 1 0 1 1 1 3 num=4 num=5 num=6 num 0 2 1 3 1 2 3 1 31 1 1 3 1 1 1 3 1 1 1 1 3 1 1 1 0 1 3 3 3 num=8 num=9 num 8 0 8 0 8 0 1 1 1 1 1 1 1 1 1 2 0 3 1 2 1 3 1 1 1 2 0 3 num=12 num=13 num=13 num=9 9 9 5 4 9 4 9 9 8 1 8 1 0 11 0 2 3 0 2 3 8 3 1 0 2 3 1 2 3 1 2 3 1 3 1 3 1 1 2 3 1 2 3 3 3 3 num=16 num=17 num=19 4 9 5 4 9 9 9 5 4 9 4 9 5 9 4 9 5 9 5 5 5 5 5 5 9 4 9 5 9 9 5 9 1 0 1 0 1 2 0 2 8 2 8 2 3 8 2 3 8 2 31 2 3 1 3 1 0 1 3 0 1 1 1 1 1 1 1 1 1 3 1 3 1 3 1 3 Num=20 Num=21 Num=234 9 5 9 4 9 9 5 9 5 9 5 9 5 9 5 9 5 1 2 3 1 2 3 1 2 3 1 2 3 8 2 3 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 1 1 num=24 num=26 num 3 1 0 2 3 0 2 38 1 8 1 8 1 8 1 1 num=29 num=30 num 4 1 0 3 4 1 3 4 1 34 1 34 2 3 4 4 1 3 4 1 3 8 1 3 8 1 8 8 8 0 0 0 num=32 num=33 num 1 1 3 1 34 1 3 4 1 3 4 1 3 0 8 8 8 8 8 0 0 num=36 num=37 num=38 num=399 9 2 5 9 2 9 5 9 9 5 9 5 9 5 9 5 9 5 9 0 51 1 1 1 1 1 1 2 14 1 3 4 3 4 3 1 3 2 34 8 8 8 3 NU M=40 NUM=41 NUM=42 NUM=42 NUM=430 9 9 9 9 9 9 5 9 5 9 5 9 5 9 5 9 5 1 1 2 1 0 2 1 0 2 1 0 2 14 2 3 4 2 3 4 2 3 4 3 4 3 4 3 4 3 4 3 4 8 8 3 4 8 3 4 8 3 8 8 8 8 3 3 num=44 num=45 num=46 num 2 0 3 4 5 0 2 5 0 2 4 5 24 8 8 8 8 0 8 0 num=48 num=49 num=50 num

9 9 2 1 9 9 24 5 1 2 4 5 1 2 4 5 1 2 4 5 1 24 0 8 8 4 5 8 8 4 5 8 8 4 5 8 8num=52 num=53 num=54 num=551 0 1 3 1 0 1 3 1 0 1 3 0 1 1 30 9 9 3 1 9 9 3 1 9 9 3 1 9 9 31 9 9 2 0 9 9 2 4 9 9 2 4 9 9 24 5 1 2 4 5 1 2 4 5 1 2 4 5 1 24 5 8 8 4 5 8 8 0 5 8 8 0 5 8 8num=56 num=57 num=58 num=591 1 1 3 1 1 1 3 1 1 1 3 1 1 1 30 9 9 3 4 9 9 3 4 9 9 3 4 9 9 34 9 9 2 4 9 9 2 4 9 9 2 4 9 9 24 5 1 2 0 5 1 2 5 0 1 2 5 0 0 20 5 8 8 0 5 8 8 5 0 8 8 5 1 8 8num=60 num=61 num=62 num=631 1 1 3 1 1 0 3 1 1 3 0 1 1 3 24 0 0 3 4 1 0 3 4 1 3 0 4 1 3 24 9 9 2 4 9 9 2 4 9 9 2 4 9 9 05 9 9 2 5 9 9 2 5 9 9 2 5 9 9 05 1 8 8 5 1 8 8 5 1 8 8 5 1 8 8num=64 num=65 num=66 num=671 1 3 2 1 1 3 2 1 0 3 2 0 1 3 24 1 3 2 4 0 3 2 4 1 3 2 4 1 3 24 0 9 9 4 1 9 9 4 1 9 9 4 1 9 95 0 9 9 5 0 9 9 5 0 9 9 5 0 9 95 1 8 8 5 1 8 8 5 1 8 8 5 1 8 8num=68 num=69 num=70 num=714 1 3 2 4 1 3 2 4 1 3 2 4 1 3 24 1 3 2 4 1 3 2 4 1 3 2 4 1 3 20 1 9 9 5 1 9 9 5 1 9 9 5 0 9 95 0 9 9 5 0 9 9 5 0 9 9 5 0 9 95 1 8 8 0 1 8 8 1 0 8 8 1 1 8 8num=72 num=73 num=74 num=754 1 3 2 4 1 3 0 4 1 0 3 4 1 0 34 1 3 2 4 1 3 0 4 1 0 3 4 0 1 35 9 9 0 5 9 9 2 5 9 9 2 5 9 9 25 9 9 0 5 9 9 2 5 9 9 2 5 9 9 21 1 8 8 1 1 8 8 1 1 8 8 1 1 8 8num=76 num=77 num=78 num=794 0 1 3 0 4 1 3 5 4 1 3 5 4 1 34 0 1 3 0 4 1 3 5 4 1 3 5 4 1 35 9 9 2 5 9 9 2 0 9 9 2 9 9 0 25 9 9 2 5 9 9 2 0 9 9 2 9 9 0 21 1 8 8 1 1 8 8 1 1 8 8 1 1 8 8num=80 num=81 num=82 num=835 4 1 3 5 4 0 3 5 4 3 0 5 4 3 25 4 0 3 5 4 0 3 5 4 3 0 5 4 3 29 9 0 2 9 9 1 2 9 9 1 2 9 9 1 09 9 1 2 9 9 1 2 9 9 1 2 9 9 1 01 1 8 8 1 1 8 8 1 1 8 8 1 1 8 8num=84 num=85 num=86 num=875 4 3 2 5 4 3 2 5 4 3 2 5 4 3 25 4 3 2 5 4 3 2 5 4 3 2 5 4 3 29 9 1 1 9 9 1 1 9 9 1 1 9 9 1 19 9 0 0 9 9 8 8 9 9 8 8 9 9 8 81 1 8 8 1 1 0 0 1 0 0 1 0 0 1 1num=88 num=89 num=90 num=915 4 3 2 5 4 3 2 5 4 3 2 5 4 3 25 4 3 2 5 4 3 2 5 4 3 2 5 4 3 20 0 1 1 1 0 0 1 1 1 0 0 1 1 8 89 9 8 8 9 9 8 8 9 9 8 8 9 9 0 09 9 1 1 9 9 1 1 9 9 1 1 9 9 1 1num=92 num=935 4 3 2 5 4 3 25 4 3 2 5 4 3 21 1 8 8 1 1 8 89 9 0 1 0 9 9 19 9 0 1 0 9 9 1

誰知道華容道總共有多少種布局？

闖過華容道

華容道遊戲很難用數字方法求解。作者所編計算機程序HRDE可以對任何布局解出答案。用它發現了文獻上有不少答案實際上並非最少步法。

關於華容道遊戲

"華容道"是世界著名的智力遊戲。在國外和魔方、獨粒鑽石並列，被譽為"智力遊戲界三大不可思議"並被編入學校的教科書。日本藤村幸三朗曾在《數理科學》雜誌上發表華容道基本布局的最少步法為85步。後來清水達雄找出更少的步法為83步。美國著名數學家馬丁・加德納又進一步把它減少為81步。此後，至今還未曾見到打破這一記錄的報道。1985~1986年在中國曾有《中國少年報》五種刊物先後舉辦過三次華容道遊戲的有獎比賽，共列出"橫刀立馬"等八種布局（見圖1），征求最少步法的答案。在競賽前有人曾預言可能會創造出新的世界記錄。雖然在1985年9月18日的《北京晚報》上有報道說在比賽中已有人打破了馬丁・加德納的81步記錄。但並未見到進一步的詳細報道，可能實際上並不是同一種布局。因為在此之前也曾經出現過類似的情況。中央電視台在1985年第6期的《電視周報》上就曾登載過有人聲稱打破了馬丁・加德納的81步記錄，但後來被確認是不同的布局。

華容道遊戲的布局可見圖1中的例子。棋盤有20個方格，上麵有大小不等的10個棋子，共占去18個方格。隻有兩個空的方格作為活動的餘地。所有棋子隻能利用這兩個空格在棋盤的平麵上平移而不得跳越其他的棋子，當然也不得越出邊框。遊戲的目標是要把最大的一個棋子（即A，占4格）移到最下部的中央出口處。為了用最少的步數達到目的，顯然必須最合理地運籌所有的棋子。由於形狀不同的棋子互相阻塞，使得本遊戲具有相當大的難度。國際上公認這類問題很難用數學方法來解決。附圖中的"橫刀立馬"就是馬丁・加德納等人所研究的基本布局。後來，又衍生出許許多多新的布局。圖1中隻是極少數幾個例子。

計算機解題的效果

筆者編製的軟件HRDE的貢獻是成功地實現了一種係統搜索（Systematicsearching）算法，它能在較短時間內，對用戶擺放的任何一種布局判斷是否有解。如果有解，則解出它的最少步法。然後，它會在屏幕上用動畫方式移動棋子以顯示它的運算方法。也可以用一連串的圖形來靜止地顯示每一步的走法，便於用戶仔細地觀察研究。一般情況下，在已經很普及的IBM486計算機上解一道題僅需要一兩分鍾，在較慢的286計算機上則大約需要十幾分鍾。根據它的算法的原理可以肯定，它推導出的結果是絕對可信的。也就是說，它所解出的走法一定是該布局的最少步法。

作為一種檢驗，用本軟件對文獻上發表過的若幹布局進行了驗證，得到了一些有趣的結果。

首先，軟件HRDE確認了馬丁・加德納的81步記錄是最少步法。想要打破這一記錄是不可能的。但是它也發現了文獻上發表的另外一些布局的答案實際上並非最少步法。

例如，1986年牛津大學出版的《SLIDINGPIECEPUZZLES》一書中列出了在國外曾經出售過的12種華容道遊戲（書中編號為C15，C23－26，C27a~d，C30，C41，C42a）並給出了最少步法的答案。經過HRDE的驗算，其中11個答案的確是最少步法，但編號為C30名TopSecret的一種布局（見圖1）書中給的67步走法並不是最少步數。最少步法應是63步。比較這兩種走法可以看出差別是在第20至35步（見圖2）。書中走15步而HRDE隻用11步就達到了相同的結果（有一點差別，但不影響後麵的走法）。

又如，1987年出版的《獨立鑽石和華容道》一書中除橫刀立馬以外，還列出26種不同的華容道布局，其中19種有答案經過HPDE的驗算，9種布局的答案確是最少步數。但另外10個答案不是最少步數。部分檢驗結果列在表1。

書中布局名稱原答案的布數HRDE軟件的答案走法總數運算時間（秒）

橫刀立馬818154224

橫豎皆將928158751

守口如瓶之一888157253

守口如瓶之二1009962556

層層設防之二12212053740

三軍聯防746543622

堵塞要道434049318

水泄不通807928311

四路皆兵676628312

五虎攔路40392482

兵將連環767528312

插翅難飛626276580

層層設防之一10210247227

這些布局的新的走法請見本文末。

表1包含了上述競賽的題目。《動手做》的競賽題是:橫刀、守口之一、層層之二、四路進兵。《文化娛樂》的題目是:橫刀、守口之二、層層之二、水泄不通。《中國少年報》、《父母必讀》和《少年科學畫報》的題目是:橫刀、插翅難飛、層層之一。

一個布局可能的走法越多，計算機解它所用的時間也越多。因此表中列出的運算時間反映了解答該布局的難度。可以看到，橫刀立馬並不是最難的，五虎攔路則相對較易。國外對每種布局的難易也有所評估，但筆者以為計算機的反映也許更有根據些。

此書中還有七種布局沒有答案。現將HRDE得到的最少步數列於表2。

書中布局名稱HRDE軟件的答案運算時間（秒）

齊頭並進6022

兵分三路7218

將湧曹營6223

橫馬當關8347

前當後堵4221

兵擋將阻8741

兵臨城下5620

HRDE程序的算法原理

HRDE采用的算法原理很簡單，也很直觀。簡言之，就是利用計算機快速處理大量數據的能力。讓它把每個布局的所有可能的走法毫無遺漏地羅列出來，然後從中找出步數最少的走法。因此，隻要保證不遺漏掉任何走法，運算的結果就是可靠的。具體到每一步，可能存在的走法並不多，保證這一點並不難。

編寫此程序的要點是:（一）選擇最佳的編碼方法，既要用最少字節表達每個布局以節省內存，又要利於解析該布局的各種可能的走法，還要能夠在數以萬計的布局中迅速進行搜尋和對比。本程序表達每個布局隻用4個字節；（二）解析每一步的走法時，保證不遺漏掉任何可能存在的走法；（三）必須設法避免一切重複的和鏡像相同的走法，否則數據量之大會難以應付；（四）為了最後追溯出某種走法的全過程，采用了樹狀鏈式數據結構，每一布局都有指針指向上一步布局的地址。

筆者首次編成此程序是在1985年。當時是在CROMEM－COZ2D微機上用匯編語言實現的。由於64K內存不夠用，運行中還必須把數據放到軟盤上。解一道題要長達2~5小時之久。1994年才把此程序移植到IBM486微型機上，增加了彩色動畫顯示。解題時間大大縮短到三分鍾左右，達到了可實用的速度。

HRDE在解題時，每推進一步就把這一步可能有的走法的數目顯示在屏幕上。實際運行的情況是，第一步一般隻有2~8種走法。但每種走法之後又有若幹種走法，因此從第二步起走法的數目不斷增加。大約30步之後會達到極大值。此後略有減少。多數布局還會出現第二次極大值。個別布局（例如水泄不通）還出現第三次極大值。最大的極大值就是這一布局可能有的走法的數目。一般在200至800之間（10棋子），或1400左右（11棋子〕，或1800之間（12棋子）。這數目包括所有走得通和走不通的走法，但不包括一切重複的和鏡像相同的走法。當然，這是計算機不加選擇地羅列所有走法的結果。如果由人來選擇，其中有些走法肯定不必考慮的。

如果某個布局的走法的數目達到極大值之後迅速降為零，軟件就報告這一布局是走不通的。

可見，HRDE是研究華容道遊戲的一種有力工具。用它來研究各種布局的走法也許能發現一些規律。在研究數學方法時，它至少能起到驗證的作用。

HRDE也是遊戲程序

本軟件也是一個高雅的智力遊戲。有助於增進邏輯思維能力。人們可以隨意設計一種新布局。然後用按鍵移動棋子。每一步都將被計算機記錄下來（省去了記錄和塗改的麻煩），每步的圖形會依次排列在屏幕上（每屏顯示24步，然後滾動），可以一覽無遺。此外還提供了以下功能:

1）隨時可以退回去任意步數再重走；

2）如果重複了以前已經走過的圖形，或鏡像與之相同的圖形，軟件會提示用戶，用不著自己去逐個查找；

3）隨時可以把用戶的走法存入磁盤，便於以後繼續研究；

4）隨時可用動畫方式顯示走法；

5）可以和計算機的答案比較，看是否是最少步數；

6）無論哪一步都可以要求計算機幫助，計算機會指出當前情況下的最佳走法。

顯然，HRDE也可以方便地用於華容道遊戲的競賽。當然，競賽中必須禁止使用計算機解題的功能。

軟件運行中有菜單及命令提示，不必事先學習就能使用。HRDE全部用匯編語言編寫，因此占內存少、運行速度快。即便如此，由於處理的數據量較大，計算機至少要提供256k內存供本軟件使用。

限製應用此軟件的條件是:最大棋子隻允許一個:最小棋子允許有4~8個（棋子總數相應為10~12個），其餘棋子任選；棋盤上隻許有兩個空格。不滿足這些條件軟件將拒絕運行。

另一個限製是，遊戲的目標必須是把棋子A移動到出口處。國外文獻上有一些遊戲的目標是要把某些棋子移動到指定的新位置。HRDE目前還不能解決這類題目。但經過少量修改應該是可以實現的。

國內外文獻中已發表的某些華容道布局的答案實際上並不是最少步數。以下是運行HRDE軟件得到的最少步法。我們沿用L.E.Hordern的記錄方法，即在多數情況下隻要指明走哪一個棋子就夠了，隻有少數情況下才需要指明如何走。這時用以下符號來表示。L向左；R向右；U向上；D向下；，隻走一格；＃必須拐彎（指最小棋子）。沒有這些符號時，表示直走，到頭為止（一格或兩格）。棋子編號見圖1。

（1）橫豎皆將（原文92步，現81步）

6457＃9683579L2A7517LA2459L458＃319L458＃319L45＃2A9#4136852A9743586D3A917431226R5＃8＃A917431A9172685A934265#A

（2）守口如瓶之一（原文88步，現81步）

57L2A13641A27＃98416＃4165＃7956＃147＃95＃2A7＃94186D52A739156714D1A71391428R5＃6＃A713914A832865A719285＃A

（3）守口如瓶之二（原文10O步，現99步）

7＃986＃31A247R2A136＃897＃4A56＃897#8936＃516U51A4812U81179352＃87＃4A2＃8539174A26837195D3921683549R1＃7＃A216835A2164A71A238491＃A

（4）層層設防之二（原文122步，現120步）

9L8＃42A1352489672531L，A4527698276#78＃7936#58＃4A6＃538924A6158＃A611583472U972A61＃4A6326＃79A1＃328531A971#A432#A16＃8A1431＃439786DA621439768A978＃A

（5）Topsecret（原文67步，現63步）

75321467LA1＃467113598A14253＃47R6241A893D51427U6UA13983D1DA7D6D2549831A981＃A

（6）三軍聯防（原文73步，現65步）

67437＃3421A758469＃64839L21A5＃389U4621A57

39＃A124689A12469＃A375124698A468＃A

（7）堵塞要道（原文43步，現40步）

59674＃2A3＃7569842DA317569842DA13D7569842A982＃A

（8）水泄不通（原文80步，現79步）

97689U765489U549A13＃8A1291＃45A3＃21＃4567A541＃23＃54219D3854A761＃938＃54A196719DA45283U6791A671＃A

（9）四路進兵（原文67步，1166步）

A43＃2A43＃152＃76A3＃12＃7698A6720＃13＃67125D3467A892＃534＃67A259825DA76143U9852A982＃A。

本文到此結束，希望對大家有所幫助呢。