陳曉梅 胡春花

摘要：回溯法是用于求解N后問題的常用算法。典型的回溯算法在N后問題的解空間中，用于判斷合法子樹的剪枝函數(shù)的時間效率較低。對于N后問題的任何一個解而言，每個皇后在棋盤上的位置無任何規(guī)律，更像是隨機放置的。因此在回溯算法中引入隨機化方法來解決N后問題，能獲得很好的時間效率。

關(guān)鍵詞：回溯法；隨機化算法；時間效率

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2014）22-5325-03

在 n行n列的棋盤上需要放置n 個皇后，規(guī)定任何 2 個皇后不能放在同一行或同一列或同一斜線上。N皇后問題就是求滿足條件的可行布局數(shù)量，或求出其中一個可行布局。該文討論求N皇后問題的一個可行布局。

回溯法是求解N皇后問題的典型算法。以當(dāng)前普通配置的計算機的運行速度而言，在n值小于28時，典型的回溯法能夠在兩秒鐘之內(nèi)獲得其中一個可行布局。在n值大于100時，由于運行時間過長，無法獲得結(jié)果。引入隨機化算法，將之與典型回溯法結(jié)合，可以有效地提高算法的時間效率。

1 求解N皇后問題的典型回溯算法

用典型回溯法解這個問題的思路是，以完全n叉樹來表示該問題的解空間，樹中根節(jié)點設(shè)為第0層，第i層的節(jié)點表示棋盤在第i行的待選列。算法從n叉樹的根節(jié)點開始，采用深度優(yōu)先的方式進行搜索。對于當(dāng)前的搜索到的某個節(jié)點，算法判斷該節(jié)點是否同時滿足約束條件①和②，若滿足，繼續(xù)按深度優(yōu)先的方式進行搜索；否則，跳過對以該節(jié)點為根的子樹的搜索，回溯至當(dāng)前節(jié)點的父節(jié)點，繼續(xù)按深度優(yōu)先方式進行搜索。當(dāng)搜索至葉子節(jié)點，判斷該節(jié)點滿足約束條件，若滿足，則獲得了關(guān)于該問題的一個合理布局。

在算法中，使用Place函數(shù)作為剪枝函數(shù)，對當(dāng)前節(jié)點使用Place函數(shù)進行合法判斷，跳過不滿足約束條件的子樹，以提高時間效率。Place函數(shù)使用前面的條件①和②作為判斷條件。

典型回溯法求N后問題的一個可行布局的算法如下：

2 使用隨機化算法與回溯法結(jié)合求解N皇后問題

其基本思想是，使用隨機化算法獲得前t行的合理布局，再使用回溯算法獲得后面行的合理布局。函數(shù)Random（n）用于返回0～n-1之間的隨機整數(shù)。函數(shù)QueensLV（t）用于隨機生成棋盤前t 行的一個布局，其返回值為布爾型，表示本次調(diào)用獲取隨機布局成功或失敗。Backtrack（t）是一個遞歸函數(shù)，其根據(jù)前t-1行的確定布局，獲取第t～n行的一個合理布局。其返回值為布爾型，表示本次遞歸獲取第t～n行布局成功或失敗。

3 實驗結(jié)果及分析

使用Dev- C++分別編寫了關(guān)于求N皇后問題的一個合理布局的典型回溯法程序和隨機算法結(jié)合回溯法的程序，在CPU為Core2 Duo 2.10 GHz，操作系統(tǒng)為Windows 7的計算上運行，它們的運行時間如表1所示：

從表1和表2可以看出，使用回溯法與隨機化算法結(jié)合比單純使用回溯法能更快地獲得其中一個可行布局，其程序運行時間明顯優(yōu)于典型回溯法，當(dāng)n為30 時，后者需要接近3分鐘的時間才能獲得一個可行布局，而前者使用4毫秒即可。當(dāng)n值增加到200時，后者可以1秒內(nèi)獲得答案，這是前者所望塵莫及的。分析其原因，是因為對于N后問題的任何一個解而言，每個皇后在棋盤上的位置無任何規(guī)律，更像是隨機放置的。因此在回溯算法中引入隨機方法來求解N后問題的一個可行解，能獲得很好的時間效率。

參考文獻：

[1] 王曉東.計算機算法設(shè)計與分析[M]. 4版.北京：電子工業(yè)出版社，2012.