華容道\\開窗等經典智力問題的求解算法研究

摘 要:本文在前人對華容道、孔明棋、九宮拼圖問題求解算法研究的基礎上，針對這些經典智力問題的特點，利用廣度優先和深度優先搜索思路設計算法，并對算法進行搜索減枝優化，設計出了一個相對優化的算法。對于開窗問題，本文通過對該問題規則的分析，設計出了一種效率較高的求解算法。通過使用C#語言編寫程序實現算法以及軟件的求解功能，經測試與運行證實了本文求解算法的正確性和有效性，并給出了算法的核心C#代碼。

關鍵詞:搜索算法華容道孔明棋開窗游戲九宮圖程序設計

中圖分類號:TP312文獻標識碼:A文章編號:1674-098X(2011)09(b)-0002-05

Researching the algorithm of solving classic mental problems of RoomEscape，fenestration and so on

Cui Yong-xiong1，Zhang Cong2，Pang Xu3

(University of Science and Technology Beijing，mathematical and physical college，

Dept of math，Xueyuan Road No.30 Haidian District Beijing 100083)

Abstract:Based on the predecessors' researches of solving algorithm to games，such as RoomEscape，Peg solitaire and Jiugong puzzles，according to the characteristics of the classic intelligence issues，this article，using the ideas of breadth first algorithm and depth first algorithm to design an algorithm，optimizing the algorithm by search pruning，designed a more optimizied algorithm.For fenestration problem，based on the analysis of this problem rules，this article designed a kind of high efficiency solving algorithm.By programming with c # language to realize this algorithm and the functions of this software，after testing and operating，the correctness and effectiveness of the solving algorithm in this paper are confirmed，and the core c # codes of the algorithm are given.

Key words:search algorithm;RoomEscape;Peg solitaire;fenestration game;Jiugong puzzles;program design

1 引言

隨著電子計算機的應用逐漸普及，程序設計以及算法設計的相關技術飛速發展，大量優秀的算法不斷涌現，例如:蟻群算法，遺傳算法，禁忌搜索算法等。但是大部分的算法主要用于科研及工程計算，而不被大眾所了解。為了將優秀的算法應用到實際當中，展現算法的獨特魅力，普及算法相關知識。本文嘗試用計算機通過簡單易懂的算法和程序設計解決華容道、孔明棋、九宮圖、開窗經典智力問題，并研究在這些經典智力問題背后所蘊含的數學原理。

2 經典問題背景及概述

2.1 華容道問題背景及概述

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

為了使問題一般化，我們對華容道問題作如下表述。

棋盤:棋盤為一個大小為m行n列的矩形凹槽，凹槽的邊緣處有若干格大小的一個出口。

棋子:華容道的棋子為若干枚均為大小不一的矩形棋子，矩形的長和寬均為整數，棋子均在棋盤中且角度與棋盤平行。棋子中有一個較大的為目標棋子。

游戲過程:游戲開始時棋子都在棋盤中且棋盤中仍有一些空位。游戲過程中每步可以將任意一個棋子在不離開棋盤的情況下滑動到與之相鄰的空位中去。棋子始終不能重疊、旋轉或離開棋盤。游戲的目的為經過若干步移動使目標棋子完全覆蓋出口位置。對于我們的程序要求求出最少步數的解。

2.2 孔明棋問題背景及概述

孔明棋，也有人叫它跳彈珠，或者叫它「Pegged」。關于孔明棋的流傳，有許多的傳說，有人說是三國時代孔明所發明的益智棋，失傳后輾轉流傳至日本，歐美，成為外國普及的益智游戲。另外也有一種說法，說它真正的名字叫作十字棋，據傳是發明于法國，是一個被囚的法國貴族，在獄中為了打發時光，而想出來的。后來在18世紀末期傳至英國，才漸漸流行至世界各地。

這種游戲的魅力在于，玩法非常的簡單，但是其中變化卻是數不盡的，解法更是不只一種，所以不論其形式如何變化，總是能帶給人們無窮的樂趣。

游戲規則:

孔明棋是屬于一個人就可以玩的游戲，它是由33個棋子排成井字型盤面，一般流傳的玩法是先取去中央的那個棋子，便可以展開游戲。游戲時，是將棋子跳過鄰近的棋子，到達一個旁邊空著的位置，被跳過的棋子則從棋盤上取開;跳的路徑可以前，后，左，右，但不可對角跳，直到剩下最后的一顆棋子，游戲便結束了。這是一種流傳很廣的益智游戲，也有很多種變形的棋盤擺法

為了使問題一般化，我們對華容道問題作如下表述:

棋盤:棋盤可以看作一個m行n列個位置組成的位置的矩陣。但是矩陣中有些位置不可以放棋子，可以認為不是棋盤的一部分。

棋子:孔明棋的棋子每個都相同，都恰好占用一個位置。

游戲過程:孔明棋的初始狀態為:棋盤上有若干個棋子，每個棋子都在一個可用的位置上，每個位置最多有一個棋子，也有的位置上沒有棋子。可行的操作為:可隨意選中棋盤上的一個棋子，沿該棋子的上、下、左、右四個方向觀察，若某方向上與該棋子相鄰的位置上有棋子，而下一個位置為空，則選中的棋子可以“跳過”相鄰的棋子放到空位上，而被“跳過”的棋子則從棋盤上移走;如此反復直到棋盤上只剩下一個棋子則游戲勝利。若棋盤上還有2個以上棋子但已無法操作，則游戲失敗。

2.3 九宮圖問題背景及概述

所謂九宮拼圖問題是指這樣一種游戲:將分別標有數字1，2，3，…，8的八塊正方形數碼牌任意地放在一塊3行3列的棋盤上。放牌時要求不能重疊。于是，在3行3列的棋盤上出現了一個空格。

現在要求按照每次只能將與空格相鄰的數碼牌移動到空格的位置上，最后直到所有數碼牌按

行優先順序排好，空格在最后一個位置，如圖1就是一個。

從初始狀態到目標狀態的例子:

當然，市面上的此類游戲棋盤往往遠大于3×3，棋子上印有精美的圖案進行拼圖，但本質與原問題相同。

為了使問題一般化，我們對華容道問題作如下表述:

棋盤:一個m行n列的矩形陣列，陣列中每個位置可以放最多一個棋子。

棋子:一共有m×n-1個棋子，分別標有1，2，3，…，m×n-1的整數。

游戲過程:初始狀態時所有棋子都放在棋盤中，這時會有一個空位，每步操作中空位上、下、左、右中的一個棋子可以移動到空位中，這時棋子原來的位置就會留下新的空位。如此一直操作下去，直到所有棋子按行優先的順序排好，空位在最后一個位置則游戲結束。對于我們的程序要求解出步數最少的解決方案。

2.4 開窗問題背景及概述

開窗問題主要流行于“文曲星”等電子產品，游戲的規則如下:

棋盤為m行n列的共m×n個格子(經典的玩法一般為5×5個格子)。每個格子可能有有黑白兩種狀態。游戲開始時每個格子的顏色被指定為黑色或白色。游戲中的可行操作為:可任意指定一個格子，則該格子顏色變化(由黑變白或由白變黑)，同時該格子上、下、左、右相鄰的格子顏色也發生變化(超出棋盤的不考慮)，其他格子不變，進行若干次這種操作使得全部棋盤變成一種指定顏色(如黑色)則游戲勝利。

以上這些智力問題是純粹的數學問題，受現實條件的限制較小，研究過程不需要太多資金，不受太多其他物質條件的限制。

這些問題的規模不大，通過套用前人搜索算法的相應模板，經過適當的分析和算法優化，利用計算機進行搜索，可以設計出個人微型計算機可以承受的求解方法:

(1)傳統的華容道有10個棋子和20個空格，狀態數最多為10！種，孔明棋有33個位置，狀態數最多為，八數碼問題狀態數最多為9!種，開窗的具有無后效性，這些狀態量不是特別大，有計算機搜索解決的可能。

(2)有些狀態是不可能達到的，應用在搜索減枝上可以大幅優化算法。

3 經典問題的研究方法

3.1華容道問題

3.1.1 問題分析及程序設計基本思路[1]

由于每個棋子的大小不一而且無法確定在多少步之后能得出最優解，利用數學直接分析華容道問題可能的求解方向較為困難。所以我們準備利用計算機廣度優先搜索的方法予以解決。一般來說搜索的思路是這樣的:首先定義一個類(hrr_node)，表示某一個棋盤的狀態，其中存儲了棋盤運行到哪一步時棋盤的信息(例如此時每個位置上棋子的編號(a[i，j])，已經走了多少步(depth)等等)。

華容道的狀態類:

class hrr_node

{

public int[，] a;//記錄每個格子屬于哪個棋子

public int[，] type;//記錄每個格子屬于棋子的形狀代碼

public int depth = 0;

public hrr_node next， par， son;}

然后將初始狀態作為一個類的一個實例(start)記錄下來。然后初始狀態上可能可以進行一種或多種合乎規定的操作，每個操作都會將局面變成一個新的狀態，將每個狀態都作為一個結構記錄下來。若這些狀態中沒有達到最終目標的狀態(即將目標棋子移到出口)，那么就依次繼續處理這些狀態，產生更多的狀態……如此下去，直到問題已經解決或者已經沒有狀態可處理為止。

為了實現這些操作，在(hrr_node)類中遞歸定義了next， par， son三個指針，其中next指針指向下一個待拓展狀態，par指向拓展出該狀態的狀態，son指向最優解的下一步。由于最優解無法事先得知，son需要在求出最優解后再賦值。賦值son指針的代碼:

if (solved)

{

hrr_node p = answer;

while (p.par != 1)

{

p.par.son = p;

p = p.par;

}

}

3.1.2 算法細節的改進[2]

為了避免重復記錄某些狀態，可以用一個數據結構將所有已經出現過的狀態按順序以鏈式存儲存在一起。然后每當新出現一個狀態就將其與所有已經出現過的狀態進行對比，若該狀態已經出現過那么就舍棄該節點，那么就能節省出處理該狀態及其衍生出的狀態的時間空間，也能避免程序死循環的出現。

為了找到步數最少的解，我們依照每個局面的depth的大小從小到大處理狀態，即先處理從初始狀態depth=0的狀態(即初始狀態start)，再處理depth=1的狀態(即從初始狀態一步可以到達的狀態)，再處理depth=2的狀態(即從初始狀態兩步可以到達的狀態)……依此類推。這樣就可以保證第一個找到的解就是步數最少的解。

為了進一步提高程序的效率，需要進行搜索減枝:某些局面雖然相互不同，但從求解的角度本質相同，例如經典的華容道中有很多棋子的大小、方向均相同，圖2兩個棋盤狀態的區別僅僅是兩個相同大小的棋子互換位置，則這兩個狀態視為相互重復的狀態。而圖3中的兩個棋盤狀態，由于出口相對于棋盤中軸線對稱，棋子的分布互為鏡像，故這兩個棋盤局面本質也相同，可只求解其中depth較小的一個即可。

為了判斷兩個棋子的形狀是否相同，可在輸入時標示每個棋子的形狀代碼，然后對于每個棋盤狀態求出每個位置上棋子對應的形狀代碼(記錄在hrr_node類的public int[，] type;中)。由于棋子不可以旋轉，所以只要兩個狀態的type數組完全相同，則這兩個狀態一定符合上述的第一種情況，可視為相互重復的狀態。

3.2 孔明棋問題

3.2.1 問題分析及程序設計基本思路

基本思路與華容道相同，即搜索的思路。所不同的是:

因為針對具體的孔明棋，求出其最優解的步數是確定的，所以本文用深度優先算法進行求解。由于孔明棋每步必然有一個棋子移出棋盤，故初始狀態有n個棋子若有一個可行解，則必恰好在n-1步剩下一個棋子，故不需考慮最優，只需求出一組解即可。為了節省資源，可以先求解depth較大的分支。由于先求解深度較大的分支，故可以用遞歸的方式較簡單的寫出代碼:

public int search(Diamond_note a)

{if (a.depth > ans.depth)

{ ans = a; }

if (a.depth == maxdepth)

{ solved = true; return 0;}

else

{

for (int i = 0; i < m; i++)//橫向

for (int j = 0; j < n - 2; j++)

if (map[i， j] map[i， j + 1] map[i， j + 2])

{

if (a.a[i， j] a.a[i， j + 1] (!a.a[i， j + 2]))

//三個位置依次為:有子、有子、無子

{

Diamond_note p = new Diamond_note(m， n);

for (int ii = 0; ii < m; ii++)

for (int jj = 0; jj < n; jj++)

p.a[ii， jj] = a.a[ii， jj];

p.depth = a.depth + 1;

p.a[i， j] = 1; p.a[i， j + 1] = 1; p.a[i， j + 2] = true;

p.par = a;

search(p);

if (solved)

return 0;

}

//此處省略了“無子、有子、有子”的情況及縱向的兩種情況的相關代碼

}

return 0;} } }

由于不同深度的局面棋子數不同，故判斷重復局面時只需比較同一深度的局面(即depth的大小相同的局面)即可，即減去其他相同深度的重復分枝。

3.2.2 算法細節的改進

孔明棋的經典棋盤具有良好的對稱性:以棋盤的幾何中心為原點，則x軸，y軸，以及x+y=1，x-y=1均為其對稱軸，故對于任意一個新生成的局面，考察其在如下8種映射下是否與已生成的局面重復:，，， ，，， ，，若重復則該局面可以舍去，只需求解之前的一個局面即可。

3.3 九宮拼圖問題

3.3.1 問題分析及程序設計基本思路

這個問題與華容道問題有一定的相似性，故基本思路相同。但由于該問題其本身的特點，算法還有很大改進的余地。

3.3.2 算法細節的改進

首先引入逆序對及逆序數的概念[3]:

逆序對:對于一個包含N個非負整數的數組A[1.n]，如果有iA[j]，則稱(A[i]，A[j])為數組A中的一個逆序對。

例如，數組(3，1，4，5，2)的逆序對有(3，1)，(3，2)，(4，2)，(5，2)，共4個。

逆序數:一個排列中逆序的總數就稱為這個排列的逆序數。逆序數為偶數的排列稱為偶排列;逆序數為奇數的排列稱為奇排列。

如2431中，21，43，41，31是逆序對，逆序數是4，為偶排列。

可以證明，若將某一局面中的棋子按行優先順序寫成一列(空格不算，恰為一個全排列)，并計算其逆序數，若棋盤的列數為奇數，則游戲中的操作不影響這個逆序數的奇偶性。

因此，若棋盤的列數為奇數，可以計算初始狀態和目標狀態的逆序數的奇偶性，若相同則繼續解，若不同則可知無解。當然若行數為偶數則可以以列優先的排列進行考慮。

3.4 開窗問題

問題分析及程序設計基本思路因為每個格子只有兩種顏色(白和黑)，對其每操作一次，則該格子的顏色改變一次，所以經過分析可以得知，操作的順序不影響操作的結果，對一個格子操作偶數次等價于操作0次(即不操作);操作奇數次等價于操作1次，故最后的解答的形式可以表示為一個數組a(i，j)。

其中m，n為棋盤的行數和列數。

因為每個格子(i，j)有兩種顏色(白和黑)，窗口一共有m*n個格子，所以一共有種可能，導致計算量非常大，以至于在給定時間內無法求出最優解。進一步分析可知，格子(i，j)的顏色只與以下因素有關:格子(i，j)的初始顏色，以及a(i，j)，a(i-1，j)，a(i+1，j)，a(i，j-1)，a(i，j+1)。假設已經確定第一行的每個格子是否操作，則對于格子(1，j)，由于格子(1，j)的初始顏色以及a(1，j) a(i，j-1)，a(i，j+1)都已確定，則該格子的顏色只能由a(i+1，j)來調整。模擬第一行的操作過程后，若a(1，j)仍為白色，則必須a(2，j)=1才能使格子(1，j)滿足條件;同理當a(1，j)為黑色時，可知a(2，j)=0，這樣a(2，j)()也已經確定，依此類推可推出所有a(i，j)的值()，最后驗證最后一行格子是否都恰為黑色即可。

那么如何確定第一行格子是否操作呢？由于第一行格子個數不是很多，所以可以枚舉第一行每個格子是否操作，共需枚舉種可能(n為列數)。對于每種可能按以上方法進行遞推，找出其中可使最后一行均為黑色的方案即可，從而明顯地降低了計算復雜度。求解過程程序實現如下:

int m， n;//棋盤大小

bool[，] a;// 模擬該格的狀態

bool[，] mark;// 該位置是否應該進行“操作”

public bool solve()//求全變成1的方法

{

int max=2^n;

for (int k = 0; k < max; k++)//對第一行進行枚舉

{

int r = k;

bool[，] temp = new bool[m， n];

for (int i = 0; i < m; i++)//復制原局面

for (int j = 0; j < n; j++)

temp[i， j] = a[i， j];

for (int j = 0; j < n; j++)//生成函數 a 的第一行

{

if (r % 2 == 1)

{

mark[0， j] = true;

change(0， j， temp);

}

else

mark[0， j] = 1;

r = r / 2;

}

for(int i=1;i

for(int j=0;j

if (temp[i - 1， j])

{

mark[i， j] = true;

change(i， j， temp);//在(i，j)位置模擬進行一次操作

}

else

{

mark[i， j] = 1;

}

bool check = true;

for (int j = 0; j < n; j++)//驗證最后一行是否符合條件

{

if (temp[m - 1， j])

{

check = 1;

break;

}

}

if (check)

return true;//有解

}

for (int i = 0; i < m; i++)//還原

for (int j = 0; j < n; j++)

mark[i， j] =1 ;

return 1 ;//無解

}

4 程序實現及結果

我們的程序使用C#語言在Visual Studio 2008環境下編寫。程序運行正常，對簡單的情況能較快得出正確結果，對于較簡單情形下的無解情況、或較復雜情況下符合某些條件的無解情況可以較快判斷，但對于較復雜的情況運行效率不高，可能是由于調試模式占用資源較多以及C#本身效率不如C語言導致的。

4.1 獨立鉆石棋

對于獨立鉆石棋的經典棋盤，棋子數不大于15時程序能在數秒內算出解法如圖4，解法可以通過界面上的左右箭頭觀察每一步的走法。如圖5。

4.2 九宮拼圖

對于由于逆序對數奇偶性不同而無解的情況，程序可以立即判斷。對于一般的情況，程序的求解速度根據棋盤初始的具體情況有很大差異。一旦求出解必為步數最少的解，解可以通過可以通過界面上的左右箭頭觀察每一步的走法。如圖6。

4.3 華容道

棋盤大小可以任意調整，出口也可以不設置在邊界處。但程序只能對很簡單的情況進行求解，對于較復雜的情況求解時間很長。一旦求出解必為步數最少的解，解可以通過可以通過界面上的左右箭頭觀察每一步的走法。如圖7。

4.4 開窗

開窗的求解程序由于是動態規劃算法，求解的效率很高。求出一組解后，只需對所有有“*”標志的格子點擊一遍即可驗證解的正確性。此外試驗發現，對于5X5的棋盤，有些初始狀態無解。

如圖8。

5 結語

本文針對華容道、孔明棋、九宮圖經典問題的各自規則特點，利用在算法中融入深度和廣度搜索思想，并對算法進行搜索減枝優化，設計出了一個相對簡單而又行之有效的的算法;對于開窗問題，本文不僅設計出了一種效率較高的求解算法，而且還利用編寫好的C#程序對開窗等問題的可解性進行試驗。雖然是基于前人對經典問題的研究而設計出求解算法，本文也有自己的創新點:

(1)前人對于九宮拼圖、華容道、獨立鉆石棋求解的程序的編寫大多基于C或C++語言，運行結果比較抽象，輸入數據也較難調節。本文主要使用C#語言進行編寫，具有圖形界面，操作簡便，運行結果也比較直觀。

(2)由于開窗問題前人的討論較少，本文通過對該問題規則的分析，設計了一套高效率的算法，并進行了編程實現。

(3)前人對于這些智力問題的研究主要局限于經典的棋盤局面，在本文的研究中所有棋盤的大小都已擴展為m行n列、而對于獨立鉆石棋的問題，棋盤的形狀限制也有一定放寬，對更廣泛的情況進行研究。

(4)證明了開窗問題不一定有解，九宮拼圖在一定條件下必有解。

參考文獻

[1]鄭凱，智算華容道[J]，家庭電腦世界，2002年7月:120.

[2]林宣治，華容道問題最優解的搜索策略[J]，漳州師范學院學報(自然科學版)，2003，第16卷第4期:36～41.

[3]王萼芳，石生明，高等代數[M]，北京:高等教育出版社，2003年7月:52～54.