華容道演算法

㈠ 華容道的解法步驟

華容道"近在咫尺"通關步驟(117步)
張下，關下，卒下右，上卒下二，趙左，中卒上二，右卒左上，右卒左二，曹上，張右，關下，右卒下左，曹左，黃下，馬右，下卒右上，曹上，卒右二，卒下左，趙下，卒左下，卒左二，曹上，左卒上右，趙右，二卒下二，曹左，馬左，黃上，下卒右上，張上，關右，趙下，上卒右，中卒上，趙左，上卒下二，右二卒左，張左，黃下，馬右，曹右，卒上二，卒左上，卒左二，張上，卒上右，關左，黃下，張右，左卒右下，張左，黃上，關右，卒下，中卒左，黃左，馬下，曹右，下卒右上，張上，趙上，二卒上，關左，黃下，馬下，曹下，上二卒右二，張上，中卒上左，曹左，馬上，黃右，卒右下，曹下，上卒下左，卒左下，張右，左卒上右，趙上，曹左，上卒下二，馬左，黃上，中卒右下，馬下，中卒右，卒下，張左，黃上，馬右，曹右，趙下，張左，二卒左，黃左，馬上，曹右，上卒下一，上卒右，趙上，關上，下二卒左二，曹下，馬下，黃下，張右，趙上，二卒上，關上，右卒上左，曹左 華容道已經被研究過多年，也總結了許多關口的走法，為讓各位喜歡華容道的朋友少走彎路，我把一些走法整理出來，與大家分享。

下面的走法沿用L．E．Hordern的記錄方法，即在多數情況下只要指明走哪一個棋子就夠了，只有少數情況下才指明如何走。這時用以下符號來表示。L向左；R向右；U向上；D向下；！只走一格；＃必須拐彎（指最小棋子）。沒有這些符號時，表示直走，到頭為止（一格或兩格）。棋子編號見圖1。當然，這只是指出了如何過關，大家也不必死記硬背這些步驟，關鍵要從此研究出過關的必要條件，而達到通關的目的。

（1） 橫豎皆將

6 4 5 7 ＃ 9 6 8 3 5 7 9 L 2 A 7 5 1 7 L A 2 4 5 9 L 4 5 8＃3 1 9 L 4 5 8＃3 1 9 L 4 5＃ 2A 9 # 4 1 3 6 8 5 2 A 9 7 4 3 5 8 6 D 3 A 9 1 7 4 3 1 2 2 6R 5＃ 8＃ A 9 1 7 4 3 1 A 9 1 7 2 6 8 5 A 9 3 4 2 6 5 # A

（2）守口如瓶之一

5 7L 2 A 1 3 6 4 1 A 2 7＃ 9 8 4 1 6 ＃4 1 6 5 ＃7 9 5 6 ＃1 4 7 ＃ 9 5＃2 A 7 ＃9 4 1 8 6 D 5 2 A 7 3 9 1 5 6 7 1 4 D 1 A 7 1 3 9 1 4 2 8 R 5 ＃6＃A 7 1 3 9 1 4 A 8 3 2 8 6 5 A 7 1 9 2 8 5＃A

（3）守口如瓶之二

7＃9 8 6 ＃3 1 A 2 4 7 R 2 A 1 3 6 ＃8 9 7＃4 A 5 6 ＃8 9 7 # 8 9 3 6＃ 51 6 U 5 1 A 4 81 2U 8 1 1 7 9 3 5 2＃8 7 ＃ 4 A 2＃8 5 3 9 1 7 4 A 2 6 8 3 7 1 9 5 D 3 9 2 1 6 8 3 5 4 9 R 1＃ 7＃ A 2 1 6 8 3 5 A 2 1 6 4 A 7 1 A 2 3 8 4 9 1＃A

（4）層層設防之二

9 L8＃4 2 A 1 3 5 2 4 8 9 6 7 2 5 3 1 L，A 4 5 2 7 6 9 8 2 7 6 # 7 8＃ 7 9 3 6 # 5 8 ＃4 A 6＃ 5 3 8 9 2 4 A 6 1 5 8＃ A 6 1 1 5 8 3 4 7 2U 9 7 2 A 6 1＃ 4 A 6 3 2 6＃ 7 9 A 1＃3 2 8 5 3 1 A 9 7 1# A 4 3 2 # A 1 6＃ 8 A 1 4 3 1＃ 4 3 9 7 8 6 D A 6 2 1 4 3 9 7 6 8 A 9 7 8 ＃A

（5）Top secret

7 5 3 2 1 4 6 7 L A 1＃4 6 7 1 1 3 5 9 8 A 1 4 2 5 3＃ 4 7 R 6 2 4 1 A 8 9 3 D 5 1 4 2 7 U 6 U A 1 3 9 8 3 D 1 D A 7D 6D 2 5 4 9 8 3 1 A 9 8 1＃A

（6）三軍聯防

6 7 4 3 7＃ 3 4 2 1 A 7 5 8 4 6 9＃ 6 4 8 3 9 L 2 1 A 5＃ 3 8 9 U 4 6 2 1 A5 7

3 9＃ A 1 2 4 6 8 9 A 1 2 4 6 9＃ A 3 7 5 1 2 4 6 9 8 A 4 6 8＃A

（7）堵塞要道

5 9 6 7 4＃2 A 3 ＃7 5 6 9 8 4 2 D A 3 1 7 5 6 9 8 4 2 D A 1 3 D 7 5 6 9 8 4 2 A 9 8 2＃A

（8）水泄不通

9 7 6 8 9 U 7 6 5 4 8 9 U 5 4 9 A 1 3＃ 8 A 1 2 9 1＃ 4 5 A 3＃ 21＃ 4 5 6 7 A 5 4 1＃ 2 3 ＃5 4 2 1 9 D 3 8 5 4 A 7 6 1＃ 9 3 8＃5 4 A 1 9 6 7 1 9 D A 4 5 2 8 3 U 6 7 9 1 A 6 7 1＃A

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

A 4 3 ＃2 A 4 3 ＃1 5 2 ＃7 6 A 3 ＃1 2 ＃7 6 9 8 A 6 7 2 0＃1 3 ＃6 7 1 2 5 D 3 4 6 7 A 8 9 2＃ 5 3 4＃ 6 7 A 2 5 9 8 2 5 D A 7 6 1 4 3 U 9 8 5 2 A 9 8 2＃ A

華容道問題用計算機求解，一般採用廣度搜索的方法，其原理很簡單，就是把下一步可能有的走法全部算出來，比如第一步有五種走法，將這五種走法的下一步走法分別算出來，可能會有三十步，在繼續將這三十步走法的下一步走法分別算出來，可能會更多，以此類推，直到達到目標狀態（曹操在出口位置）為止。

在解華容道的問題上，我覺得有兩個問題比較棘手。

其一、演算法的效率。

其二、獲得最優解法。

我是這樣解決的：

1、 要提高演算法的效率，首先要知道演算法的瓶頸在什麼地方，在得出每一個狀態（走完一步各個棋子的位置）都要和前面的狀態進行比較，以保證不重復，隨著步數的增多，狀態數會大幅度增加，這是，和前面的狀態比較這一過程成了整個演算法的效率。解決的辦法，從兩個地方著手，其一，增加每一步比較的速度。在程序中，用5*4的數組表示一個狀態，這樣，每一次比較要比較二十個數，因為數組中每個數定義從0-7，用三個二進制位可以表示，3*20=60位，用一個64位數就可以表示（有的資料說用四個位元組就可以，我實在想不出來），這樣每次比較一個64位數就可以了。其二、減少比較的狀態，這是提高效率的關鍵。比較的時候不要和前面所有的狀態都進行比較，只要和前兩步的所有狀態進行比較就可以了。經過以上的優化，在解橫刀立馬時，大約需要一，兩秒鍾就可以了，（我的機器，賽揚1.1OC1.46）。

2、 獲得最優解法，比如橫刀立馬是81步，這里的一步指移動一個棋子，可以把一個卒子向一個方向移動兩格，或者卒子拐彎移動兩格，或者一個將向一個方向移動兩格（橫將橫著移，豎將豎著移）都是一步。獲得最優解法的關鍵是把下一步可能有的走法全部算出來，不能遺漏。我是根據空格來算走法的的，分三種情況：

① 、卒子拐彎移動，如果有連著兩個空格（橫向的），則如果在它的上面或下面（有四個位置）有卒子的話，那麼可以拐彎移動，有四種走法。如果兩個空格是豎向的，那麼，空格的左右如果有卒子，也可以拐彎移動，也有四種走法。

②、向一個方向移動兩格，這里可能出現的情況有：卒子向一個方向移動兩格，橫將橫著移兩格，豎將豎著移兩格

③、考慮向一個方向移動一格的情況，這里情況很多，我不一一列舉了。

以上的演算法很麻煩，很大一部分程序用來寫這個了，如果大家有更簡單的，可以告訴我，但一個原則，必須把所有的走法全部考慮。 我知道的只有這些了，希望採納。

㈡ 華容道的擺法及名稱和解法

名稱：橫刀立馬

橫刀立馬是華容道的最優解法，一共有81步，由計算機通過窮舉法得出。

解法按照下圖每小格一步一步操作即可，每張圖18步，最後一張圖9步。

1、1-18步。

(2)華容道演算法擴展閱讀

最早系統研究游戲華容道的是蘇州大學數學教授許蒓舫先生。1952年，他在《數學漫談》中對這個游戲作了詳細的分析，總結出8條規則。這8條可以歸納為以下4點：

1、四個小兵必須兩兩在一起，不要分開；

2、曹操，關羽，大將移動時前面應有兩個小兵開路；

3、曹操移動時後面還應有兩個小兵追趕；

4、以上三種狀況，其中各塊都可局部（不妨礙其他地方）任意移動。

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

㈢ 華容道這個游戲具體解法是什麼

華容道以其變化多端、百玩不厭的特點與魔方、獨立鑽石棋一起被國外智力專家並稱為“智力游戲界的三個不可思議”。游戲中不允許跨越棋子，成功完成的標志就是幫助曹操從初始位置移到棋盤最下方中部的出口逃走。

你喜歡玩這個游戲嗎？