基于四皇后問(wèn)題的回溯法求解及算法實(shí)現(xiàn)

聶 華

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

0 引言

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

1 基本思想

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

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

2 四皇后問(wèn)題的求解過(guò)程

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

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

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

圖1 四皇后問(wèn)題的一種解空間樹(shù)

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

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

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

圖2 四皇后問(wèn)題的另一種解空間樹(shù)

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

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

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

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

解決四皇后問(wèn)題的算法描述如下：

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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