聶 華

（陜西職業(yè)技術(shù)學(xué)院,陜西 西安,710100）

0 引言

回溯法是一種非常有效，適用范圍相當(dāng)廣泛的算法設(shè)計思想。許多復(fù)雜的問題，規(guī)模較大的問題都可以使用回溯法求解，因此回溯法又有“通用解題方法”的美稱。本文將利用四皇后問題作為實(shí)例，討論回溯法的求解過程。

1 基本思想

回溯法解決皇后問題的基本思想是：在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根節(jié)點(diǎn)出發(fā)深度探索解空間樹。當(dāng)探索到某一節(jié)點(diǎn)時，要先判斷該結(jié)點(diǎn)是否包含問題的解，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去；如果該結(jié)點(diǎn)不包含問題的解，那就說明以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹一定不包含問題的最終解，因此要跳過對以該結(jié)點(diǎn)為根的子樹的系統(tǒng)探索，逐層向其祖先結(jié)點(diǎn)回溯。這個過程叫做解空間樹的“剪枝”操作。

如果應(yīng)用回溯法求解問題的所有解，要回溯到解空間樹的樹根，這樣根結(jié)點(diǎn)的所有子樹被探索到才結(jié)束。如果只要求解問題的一個解，那么在探索解空間樹時，只要搜索到問題的一個解就可以結(jié)束了。

2 四皇后問題的求解過程

許多復(fù)雜的問題都可以用回溯法的思想來求解，例如經(jīng)典的N皇后問題。

N皇后問題的描述為：求解如何在一個N×N的棋盤上無沖突的擺放N個皇后棋子。在國際象棋里，皇后的移動方式為橫豎交叉的，因此在任意一個皇后所在位置的水平、豎直，以及45°斜線上都不能出現(xiàn)皇后棋子

N皇后問題的解法很多，可以用回溯法解決N皇后問題。以四皇后問題為例，可以構(gòu)建出一棵解空間樹，通過探索這棵解空間樹，可以得到四皇后問題的一種解。這樣的解空間樹有4棵。如圖1所示為皇后問題的一種解空間樹。

圖1 四皇后問題的一種解空間樹

由于版面的限制，該解空間樹并不完整。該解空間樹的根結(jié)點(diǎn)為第一個皇后的一種擺法，它還有另外3種擺法，因此一共可以構(gòu)造出4棵解空間樹。通過探索上述這棵解空間樹，可以搜索出由根結(jié)點(diǎn)這種棋面所產(chǎn)生的所有四皇后的解（如果有解）。

如圖1所示，根結(jié)點(diǎn)派生出4個子結(jié)點(diǎn)。每個結(jié)點(diǎn)都示意出前兩個皇后可能擺放的位置。每個子結(jié)點(diǎn)又可派生出4個子結(jié)點(diǎn)，每個結(jié)點(diǎn)都示意出前3個皇后可能擺放的位置……整個解空間樹為一棵四叉的滿樹，包含85個結(jié)點(diǎn)。

應(yīng)用回溯法求解四皇后問題，從根結(jié)點(diǎn)出發(fā)，深度優(yōu)先搜索整個解空間樹。當(dāng)訪問到根結(jié)點(diǎn)的第一個孩子時，發(fā)現(xiàn)該結(jié)點(diǎn)不包含問題的解。也就是說，該結(jié)點(diǎn)所示的皇后的擺法不符合四皇后問題的要求，于是停止向下探索，回溯到根結(jié)點(diǎn)，以盡快找到問題的答案。實(shí)踐證明，如圖1所示的解空間樹中不包含四皇后問題的解。于是需要探索第二棵解空間樹，如圖2所示。

圖2 四皇后問題的另一種解空間樹

按照上述的探索過程深度優(yōu)先搜索如圖2所示的解空間樹，最終可以搜索出四皇后問題的一個解，它的搜索路徑在圖中用粗體表示，葉結(jié)點(diǎn)為四皇后問題的一種解。圖中用虛線描繪的結(jié)點(diǎn)之間的連線表示在此執(zhí)行剪枝操作。

3 四皇后問題的算法實(shí)現(xiàn)

上一節(jié)已經(jīng)詳細(xì)介紹了回溯法解決四皇后問題的基本過程。在這里將給出具體的算法描述和程序清單。

其實(shí)在解決四皇后問題時，并不一定要真的構(gòu)建出這樣的一棵解空間樹，它完全可以通過一個遞歸回溯來模擬。所以解空間樹只是一個邏輯上的抽象。當(dāng)然也可以用樹結(jié)構(gòu)真實(shí)地創(chuàng)建出一棵解空間樹，不過那樣會比較浪費(fèi)空間資源。

解決四皇后問題的算法描述如下：

在該算法中，用一個二維數(shù)組Q[4][4]存放棋盤布局。[i][j]=0表示不放置皇后，Q[i][j]=1表示放置皇后。在這里采用了遞歸回溯的方法深度優(yōu)先搜索解空間樹，可以將四皇后問題全部解找到并輸出。函數(shù)Queen()包括兩個參數(shù)，參數(shù)j為放置的皇后所在棋盤的列數(shù)，最開始調(diào)用Queen()時，j的初始值為0，由它課派生出第一棵解空間樹。j的取值范圍是0～3，對應(yīng)著4棵解空間樹。當(dāng)j的值等于4時，表明已得到一個四皇后的解，程序返回。參數(shù)(*Q)[4]為指向二維數(shù)組每一行的指針。

在該算法中調(diào)用了子函數(shù)isCorrect(i,j,Q),它的功能是判斷棋盤中Q[i][j]的位置是否可以放置一個皇后。它的算法描述如下：

該算法的設(shè)計思想是，以Q[i][j]為中心，分別判斷二維數(shù)組Q的行、列、左上方、右下方、右上方、左下方的狀態(tài)。如果存在1（有皇后棋子），則表明Q[i][j]的位置不能放置皇后，返回0：否則可以放置皇后，返回1。

4 結(jié)束語

綜上所述，用回溯法求解四皇后問題時簡單易懂，特別適用于求解那些涉及到尋求一組解的問題或者求滿足某些約束條件的最優(yōu)解的問題。本文中很好的詮釋了回溯法解四皇后問題的算法設(shè)計思想。不僅四皇后問題，例如八皇后問題、子集和數(shù)問題、圖的著色問題、哈密頓環(huán)問題和0/ 1 背包問題等許多復(fù)雜的問題，規(guī)模較大的問題都可以使用回溯法求解。該方法這對于今后其他問題的研究會有很大幫助。

[1][美]Adam Dro zdek.數(shù)據(jù)結(jié)構(gòu)與算法( Java 語言版)[M].周翔,王建芬,黃小青,等譯.北京:機(jī)械工業(yè)出版社,2003.139～ 143.

[2]黃建民、羅杰.八皇后問題的非遞歸算法設(shè)計[J]計算機(jī)與現(xiàn)代化,2004（5）

[3]盧開澄.組合數(shù)學(xué)(第2版)[M].北京:清華大學(xué)出版社,1991.