基于四皇后問題的回溯法求解及算法實現

聶 華

（陜西職業技術學院,陜西 西安,710100）

0 引言

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

1 基本思想

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

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

2 四皇后問題的求解過程

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

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

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

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

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

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

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

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

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

3 四皇后問題的算法實現

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

其實在解決四皇后問題時，并不一定要真的構建出這樣的一棵解空間樹，它完全可以通過一個遞歸回溯來模擬。所以解空間樹只是一個邏輯上的抽象。當然也可以用樹結構真實地創建出一棵解空間樹，不過那樣會比較浪費空間資源。

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

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

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

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

4 結束語

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

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

[2]黃建民、羅杰.八皇后問題的非遞歸算法設計[J]計算機與現代化,2004（5）

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