一種求解n皇后問題的概率回溯復合算法

徐少飛，張立臣，李鵬

（陜西師范大學計算機科學學院，西安 710119）

0 引言

八皇后問題是指在一個8×8的國際象棋棋盤上隨機擺放八個皇后［1］，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，要求求出所有的可行解。一個八皇后問題的可行解如圖1所示。

圖1 八皇后問題的一個可行解

n皇后問題是八皇后問題的推廣，是指在一個n×n的棋盤上放置n個皇后，使任意兩個皇后不能相互攻擊。我們知道，傳統的回溯算法可以求解n皇后問題，但其時間復雜度是指數型的，算法效率較低。目前不少學者對傳統回溯算法進行改進，文獻［2］利用了n皇后問題解的對稱性質對回溯法進行了改進，但優化效果并不明顯；文獻［3］和文獻［4］利用基于位運算的回溯算法進行求解，在整個解空間中搜索，仍沒有降低算法的時間復雜性。為了研究更高效、簡潔求解n皇后問題一組可行解的算法，本文將傳統的回溯算法與概率算法相結合，將棋盤分割為兩部分，前半部分使用概率算法求解，后半部分采用回溯算法求解，并合理設置影響算法性能的分割系數和回溯方式。實驗結果表明，相比于傳統的回溯算法，該算法能夠有效地縮短求解時間，因而可以極大拓展在規定時間內可求解問題的規模。

1 n皇后問題求解模型的建立

約定第i個皇后放在棋盤的第i行，設其所在的列為xi(i=1,2,3,…,n)，這樣問題的解就是n個皇后所在列的序號組成的一個n元一維向量(x1,x2,x3,…,xn)，解空間是從1到n的全排列。約束條件是這n個皇后在棋盤上的位置(1,x1),(2,x2),(3,x3),…,(n,xn)不在同一列和同一對角線上。

即對于任意兩行i和j上的皇后，需要滿足的約束條件有兩個：①不在同一列：xi≠xj;②不在同一對角線上：abs(xi-xj)≠abs(i-j)。

2 回溯法求解n皇后問題

2.1 算法思想

回溯法的基本思想是，按照順序依次確定每個皇后的位置，首先將第一個皇后放置在滿足約束條件的第1個位置，即x1=1,然后再為下一個皇后確定合適的位置，以此類推，直到確定了所有皇后的位置。在這一過程中，可能會出現這樣的情況：即無法為第n個皇后找到滿足約束條件的位置。這說明其前面已放置皇后的位置需要進行調整,因此可以先考慮將第n-1個皇后移至下一個滿足約束條件的位置，如果第n-1個皇后無法尋找到下一個滿足約束條件的位置，則可以進一步向前調整第n-2個皇后的位置，以此類推。之后再為第n個皇后尋找滿足約束條件的位置。以這樣的方式進行下去，最終可以保證所有皇后在互不攻擊的情況下放置在棋盤中。

2.2 算法求解

2.2.1 遞歸回溯算法

遞歸回溯算法的思想是基于深度優先搜索策略［5］。對于n皇后問題，遞歸的回溯算法采用遞歸的方式依次確定每個皇后的位置，若一個皇后的所有位置都不滿足約束條件，算法將回溯至前一個皇后。

算法1運用遞歸回溯法解決n皇后問題偽代碼描述

2.2.2 非遞歸回溯算法

求解n皇后問題的非遞歸回溯的算法同樣采用深度優先搜索策略，并在不符合約束條件時及時回溯［6-7］。相比于遞歸的回溯算法，非遞歸回溯算法不需要頻繁地調用系統堆棧，而是在一個數組中進行回溯的，從而節省了系統資源。

算法2運用非遞歸回溯法解決n皇后問題偽代碼描述

2.3 算法分析

回溯法基于深度優先搜索的策略在整個解空間中進行搜索，并在不滿足條件時及時進行剪枝操作。在解決n皇后問題的過程中，若不進行任何的剪枝操作，最壞情況下，其時間復雜度可達O(nn)，屬于指數級別。相比于一般的窮舉法，回溯算法雖然避免了一些不必要的搜索，并可將最壞情況下的時間復雜度優化至O(n!)，但其時間復雜度仍然較大，性能不好。

3 拉斯維加斯概率算法求解n皇后問題

3.1 算法思想

拉斯維加斯（Las Vegas）概率算法的基本思想是用生成的隨機序列代替有次序的窮舉，然后判斷基于該隨機序列所產生的結果是否為符合問題約束條件的正確解［8］。拉斯維加斯概率算法非常適合于在一個問題解空間中尋找一個可行解的場景。但是，該算法同時具有一定的缺點，即存在無法找到可行解的情形。事實上，出現這種情況的可能性不大，而且我們可以通過增加算法執行次數的方式進一步提高找到可行解的概率。

我們知道，當程序重復執行的次數越多，運行時間越長時，利用拉斯維加斯概率算法求得問題的一個可行解的概率也就越大［9-10］。因此，如果要使求解問題失敗的概率降至任意小，可以足夠多次地重復調用拉斯維加斯概率算法進行求解。

3.2 算法分類

為了表述方便，本文將拉斯維加斯概率算法分為拉斯維加斯循環算法和拉斯維加斯一般算法。

拉斯維加斯循環算法的成功率是100%，它將循環執行，直到找到一組可行解時退出程序。

拉斯維加斯一般算法的成功率不是100%，它將設定一個最大循環次數k，然后再進行有限次數的循環，直到找到一組可行解或當循環次數>k時，結束程序。

3.3 算法求解

對于n皇后問題，我們目前無法確定每個皇后放置的具體規律，因而無法快速地放置這些皇后，這使得我們可以采用隨機放置的方式。這種隨機放置的思想與拉斯維加斯概率算法相同。該算法依次隨機地放置每一個皇后，直到所有的皇后均已在滿足約束條件的情況下放置好。在放置當前皇后的過程中，需要保證：新放置的皇后與前面已放置好的所有皇后不沖突。

本文將選擇拉斯維加斯循環算法來解決n皇后問題，確保其正確率達到100%，方便后續進行各種算法運行時間的比較分析。

算法3運用拉斯維加斯概率算法解決n皇后問題偽代碼描述

Input:開始進行概率算法的行序號star（t0

3.4 算法分析

對于拉斯維加斯概率算法，假設一共要排列n個皇后，每一行的皇后平均要進行k次測試才能找到合適位置，LV函數的算法時間復雜度為O(n)，在Probability函數中，LV函數將被執行k次，因此，最終該算法的時間復雜度應為O(n×k)。

4 概率回溯復合算法求解n皇后問題

4.1 算法思路

分析上文中概率算法和回溯算法的特性可知，概率算法在問題規模較小時可以快速得到一個可行解；而回溯算法則可以利用其回溯的特性保證能夠求得問題的一個可行解［11-12］。因此，我們可以將二者的優勢相結合，提出一種概率回溯復合算法。該算法具體為：先將整個棋盤分為兩部分，然后在前一部分采用拉斯維加斯概率算法隨機地放置皇后，在后半部分使用回溯算法放置剩余的皇后，直到所有皇后都被放置完畢，如圖2所示。

圖2 概率回溯復合算法示意

4.2 算法求解

設皇后數量為n，d為分割系數，用于分割棋盤，floor為向下取整函數。在棋盤的前floor(n×d)行采用拉斯維加斯概率算法隨機放置皇后，后續的行采用非遞歸回溯的算法放置其余皇后。

為了確保該算法的成功率為100%，本文將在棋盤的前floor(n×d)行采用拉斯維加斯循環概率算法進行求解，并允許后續行在使用回溯法時能夠回溯到棋盤首行。

算法4運用概率回溯復合算法解決n皇后問題偽代碼描述

Input:皇后數量n，分割系數d，開始進行概率算法的行序號start（0

4.3 算法分析

當皇后數量為n時，則先在棋盤前floor(n×d)行使用拉斯維加斯概率算法，在后續行使用非遞歸回溯算法，采用概率算法的時間復雜度為O(d×n×k)，使用回溯法的 時 間 復 雜度為O((d×n)!)。

5 仿真實驗與分析

5.1 實驗環境

本文實驗環境：CPU，Intel Core i5-8265U；內存容量，8.00 GB；硬盤，1 TB；PF使用率，47%～50%；集成開發工具，Eclipse 4.12.0。

5.2 輸入數據

輸入數據為皇后的數量n，這也決定了棋盤是一個n×n大小的。本實驗將n分別取為8、11、14、17、20、23、25、26、27、28、30，概率回溯復合算法的分割系數d取為0.5，然后測試四種算法的運行結果及運行時間。在特定輸入規模n的情況下，每一種算法運行20次，運行時間取這20次實驗運行時間的平均值。

5.3 實驗結果分析

分別對n皇后問題遞歸回溯、非遞歸回溯、拉斯維加斯概率、概率回溯復合算法的算法規模和執行時間進行仿真。四種算法的成功率為100%，其求解時間如表1所示。

表1 四種算法求解時間（單位：ms）

當n>11時，拉斯維加斯概率算法的求解時間就已經超過了10000 ms，因此不再統計概率算法后期的求解時間。

從表1中可以直觀地看到四種算法的求解時間對比，當n從27變到28時，兩種回溯算法的求解時間的增長速度很快，當n從28變到30時，其求解時間更是呈指數形式增長。相比之下，概率回溯復合算法的求解時間一直都較短，并且隨輸入規模n增加而增長的速度也十分緩慢。

傳統的回溯算法在n=30的時候求解時間就已經很長了，考慮到計算機的算力瓶頸，后面只觀察隨著n值的繼續增大，概率回溯復合算法求解時間的增長情況。

圖3 概率回溯復合算法求解時間（n值：32～50）

圖3是當n值從32變化到50的過程中，概率回溯復合算法求解時間的變化情況。當n值達到41后，算法的求解時間就增長的比較快了，當n值從47到50的時候，算法的求解時間增長得最快，在n=50時，算法求解時間就已達到了42047 ms。這可能是由于前半部分的概率算法和后半部分的回溯算法需要花更多的時間去尋找每個皇后的合適位置。

6 概率回溯復合算法的進一步研究

6.1 回溯范圍對算法性能的影響

對于概率回溯復合算法，當在前若干行使用完拉斯維加斯概率算法之后，后續行會使用回溯法繼續放置剩余皇后。當回溯法需要進行回溯操作時，回溯范圍有兩種，一種是截止到開始使用回溯算法的那一行；另一種是截止到首行。可通過實驗驗證的方式對比這兩種范圍對算法性能的影響。皇后數量n將分別取為7、10、15、18、20、23、25、26、27、28，其概率算法部分采用成功率非100%的拉斯維加斯一般概率算法，最大循環次數k選為10000，這樣便于研究不同參數分別對概率算法部分和回溯算法部分的影響情況。

表2 回溯截止到首行的求解情況

表3 回溯截止到開始回溯的那一行的求解情況

表2和表3分別是回溯截止到首行的求解情況和回溯截止到開始回溯的那一行的求解情況。通過兩種回溯方式的對比實驗，可以知道，采用回溯到首行的方式，算法整體求解的正確率要更高一些。

6.2 分割系數對算法性能的影響

概率回溯復合算法中的分割系數d表示前floor(n×d)行使用拉斯維加斯概率算法，其中，floor()函數是下取整函數。因此，分割系數d的選取對該算法的性能有重要影響。本次實驗，規定采用回溯至首行的策略，概率算法部分采用成功率非100%的拉斯維加斯一般概率算法，設置分割系數分別為0、0.2、0.4、0.6、0.8、1，測試其在n=30的情況下算法連續運行50次能成功求解的概率，圖4是求解正確率隨分割系數d變化的折線圖，測試結果如圖4所示。

圖4 求解成功率隨分割系數d的變化情況

分析圖4可知，當分割系數d增大時，算法的求解成功率明顯下降。當d=1時，概率回溯復合算法退化為回溯算法，當d=0時，概率回溯復合算法變為拉斯維加斯概率算法。

分割系數除了對算法成功率有很大影響外，還影響算法的求解時間。圖5測試在n=30時，算法求解時間隨分割系數的變化情況。分割系數d分別取0.2、0.3、0.4、0.5、0.6、0.7、0.8，采用回溯到首行的方式，概率算法部分采用成功率為100%的拉斯維加斯循環概率算法，這樣能更合理地統計算法求解時間。

圖5 求解時間隨分割系數d的變化情況

從圖5可知，在分割系數從0.2增加到0.8的過程中，算法的求解時間是一個先減少后增加的過程，在d=0.4時，算法的求解時間最短。在分割系數為0.7和0.8時，程序的運行時間已超過規定的最大時限5 min，因此不再進行計算。

由此可見，選取合適的參數可以使概率回溯復合算法的性能得到很大提升。

7 結語

本文通過對比實驗,發現傳統的回溯算法在n=30的時候就需要兩萬多毫秒才能得到結果，而相比之下，分割系數為0.5的概率回溯復合算法在n值接近50的時候才會消耗相同的時間，這極大地拓展了規定時間內算法可計算和求解的范圍。此外，本文還深入研究和分析了回溯方式、分割系數等參數條件對概率回溯復合算法成功率及求解時間的影響，得出了在合理設置這些參數的條件下，概率回溯復合算法在求解n皇后問題一組解上的表現要優于其他算法的結論。這對今后研究與應用該算法以及分析和研究其他NP問題具有較好的指導意義和參考價值。