基于對(duì)稱性計(jì)算N皇后問(wèn)題的非遞歸算法

孫國(guó)偉，買阿麗

(1.運(yùn)城學(xué)院應(yīng)用數(shù)學(xué)系，山西 運(yùn)城 044000;2.廣州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，廣東 廣州 510006)

0 引言

N皇后問(wèn)題[1-3]是一個(gè)古老而著名的問(wèn)題，該問(wèn)題是在N×N的國(guó)際象棋棋盤上，放置N個(gè)皇后，使任何兩個(gè)皇后都不能相互攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。N皇后問(wèn)題是由八皇后問(wèn)題演化而來(lái)的。八皇后問(wèn)題于1848年由國(guó)際象棋棋手 Max Bazzel提出[1]。

N皇后問(wèn)題是一個(gè)NP難問(wèn)題，近年來(lái)已經(jīng)成為計(jì)算機(jī)應(yīng)用領(lǐng)域內(nèi)的一個(gè)經(jīng)典問(wèn)題。學(xué)者們針對(duì)此問(wèn)題提出了許多解決方法。Jordan Bell等人總結(jié)比較了2007年以前提出的各種解法[1]。目前對(duì)N皇后問(wèn)題的計(jì)算主要有兩方面的研究，一方面是設(shè)計(jì)高效的算法去計(jì)算問(wèn)題的所有解，如回溯法[2-4]、并行算法[5]、位運(yùn)算方法[6-8];另一方面是快速尋找此問(wèn)題的一部分解[9-12]。

本文使用回溯法尋找N皇后問(wèn)題的全部解?；厮菟惴梢杂眠f歸方法來(lái)實(shí)現(xiàn)，也可以用非遞歸方法來(lái)實(shí)現(xiàn)。用遞歸的方法來(lái)解決回溯問(wèn)題時(shí)，思路很清晰，但速度較慢;非遞歸方法相對(duì)速度快，但是程序的邏輯結(jié)構(gòu)卻很復(fù)雜。不論用哪種方法實(shí)現(xiàn)，當(dāng)N較大時(shí)還沒(méi)有一種高效的算法。

為了提高算法的計(jì)算效率，需要研究N皇后問(wèn)題解的性質(zhì)，利用性質(zhì)縮小搜索空間。文獻(xiàn)[5]和文獻(xiàn)[12]均研究了解的旋轉(zhuǎn)性質(zhì)。文獻(xiàn)[5]利用旋轉(zhuǎn)性質(zhì)實(shí)現(xiàn)了N皇后解的快速計(jì)數(shù)。文獻(xiàn)[12]首先考慮計(jì)算出N皇后的全部解，之后再利用旋轉(zhuǎn)性質(zhì)計(jì)算基礎(chǔ)解。文獻(xiàn)[8]利用回溯法，基于位運(yùn)算計(jì)算N皇后問(wèn)題，但是程序復(fù)雜，且仍在整個(gè)解空間中搜索。本文提出N皇后問(wèn)題解的4個(gè)對(duì)稱性質(zhì)，并利用性質(zhì)縮小搜索空間，給出利用對(duì)稱性計(jì)算N皇后全部解的一個(gè)非遞歸算法。

1 N皇后問(wèn)題算法設(shè)計(jì)

N皇后問(wèn)題的解空間可以描述為:

其中，Q=(a1，a2，…，aN)表示在棋盤的第 i行第 ai列放置一個(gè)皇后，i=1，2，…，N。因此可用自然數(shù)集合{1，2，…，N}的排列樹(shù)來(lái)描述解空間，如圖1所示。

圖1 4皇后解空間的排列樹(shù)

圖1為4皇后解空間，其中每一個(gè)節(jié)點(diǎn)旁邊的編號(hào)表示棋盤的列號(hào)，第i層節(jié)點(diǎn)表示在棋盤第i行可以放置的與前i－1行皇后滿足行列不沖突的列，i=1，2，3，4。

根據(jù)對(duì)角線不沖突的約束知，若Q=(a1，a2，…，aN)∈S，則當(dāng)且僅當(dāng)對(duì)任意 i≠j，有:

則Q為N皇后一個(gè)解。

可以利用樹(shù)的深度優(yōu)先遍歷來(lái)實(shí)現(xiàn)回溯法，并在計(jì)算過(guò)程中利用式(1)進(jìn)行剪枝，計(jì)算N皇后問(wèn)題的解。

假設(shè)在棋盤的第i行第ai列放置一個(gè)皇后之后，則可以利用式(1)計(jì)算出當(dāng)這個(gè)皇后放置以后第i+1行可以放置皇后的列，從而在每次回溯時(shí)，只在每一行可以放置皇后的列中繼續(xù)進(jìn)行搜索，避免對(duì)角線不沖突約束的重復(fù)判斷，提高計(jì)算效率[8]。

算法1 N皇后非遞歸算法。

P1如果N==1，輸出“1皇后有一個(gè)解”，算法結(jié)束，否則執(zhí)行P2至P4。

P2初始化棧S1。棧長(zhǎng)為N+1。即將整數(shù)1，2，…，N形成含有N個(gè)元素的隊(duì)列，每個(gè)隊(duì)列元素包含兩項(xiàng)，數(shù)字域和標(biāo)志域。初始化時(shí)所有元素的標(biāo)志域均置為0，并依據(jù)整數(shù)遞增順序進(jìn)入隊(duì)列。再將此隊(duì)列壓入棧S1。

P3初始化棧S2為空，棧長(zhǎng)為N。

P4當(dāng)棧S2不空或棧S1棧底隊(duì)列中還有元素的標(biāo)志位為0時(shí)，循環(huán)執(zhí)行4.1至4.3。

4.1 當(dāng)棧S2中元素個(gè)數(shù)小于N，且棧S1棧頂隊(duì)列中存在標(biāo)志位為0的元素時(shí)，循環(huán)執(zhí)行4.1.1至4.1.4。

4.1.1 彈出S1的棧頂元素，記此隊(duì)列為L(zhǎng)1;

4.1.2 記隊(duì)列L1的隊(duì)頭元素之后第一個(gè)標(biāo)志域?yàn)?的元素為h，并將h所對(duì)應(yīng)的數(shù)字域的值a壓入棧S2;再將L1中除a之外的數(shù)字，形成一個(gè)隊(duì)列L2，并將L2中滿足式(1)條件的元素標(biāo)志位置為1，其余標(biāo)志位置為0，并依據(jù)整數(shù)遞增順序進(jìn)入隊(duì)列;

4.1.3 將隊(duì)列L1中h的標(biāo)志位改為1，并將隊(duì)頭移至h，再將L1壓入棧S1;

4.1.4 將 L2壓入棧 S1。

4.2 如果棧S2中元素個(gè)數(shù)等于 N，執(zhí)行4.2.1至 4.2.2。

4.2.1 從S2的棧底開(kāi)始，從下往上依次輸出棧中元素產(chǎn)生一個(gè)新解。解的個(gè)數(shù)加1。

4.2.2 棧S2棧頂出棧。

4.3 當(dāng)S2不空且S1棧頂隊(duì)列中元素標(biāo)志位全為1 時(shí)，循環(huán)執(zhí)行4.3.1 至 4.3.2。

4.3.1 彈出S1棧頂元素;

4.3.2 彈出S2棧頂元素。

2 N皇后算法分析

圖2為4皇后問(wèn)題排列樹(shù)的剪枝示例圖。圖2中粗線表示4 皇后問(wèn)題的兩個(gè)解:2，4，1，3 和3，1，4，2;虛線表示被剪去的樹(shù)枝;有標(biāo)號(hào)的節(jié)點(diǎn)表示進(jìn)入過(guò)棧S1的節(jié)點(diǎn)，實(shí)線上有標(biāo)號(hào)的點(diǎn)表示進(jìn)入過(guò)棧S2的節(jié)點(diǎn)。

圖2 4皇后問(wèn)題的解及排列樹(shù)剪枝示例

使用棧和隊(duì)列實(shí)現(xiàn)非遞歸組合生成算法，棧和隊(duì)列均采用順序存儲(chǔ)方式[13-14]。棧S1需要2·(n+1)個(gè)空間，棧S2需要n個(gè)空間，因此空間復(fù)雜度為O(3n)。時(shí)間復(fù)雜度是一個(gè)需要繼續(xù)研究的問(wèn)題。

3 N皇后解的性質(zhì)

N皇后問(wèn)題的部分解可以由其他解經(jīng)對(duì)稱和旋轉(zhuǎn)變換得到。當(dāng)以{1，2，…，N}的全排列樹(shù)表示N皇后問(wèn)題的解空間時(shí)，每個(gè)解對(duì)應(yīng)于一個(gè)全排列Q=(a1，a2，…，aN)，此時(shí)有如下4 個(gè)對(duì)稱性質(zhì)。

性質(zhì)1 如果Q=(a1，a2，…，aN)為N皇后問(wèn)題的一個(gè)解，則它關(guān)于棋盤左右對(duì)稱的解為Q1=(b1，b2，…，bN)，其中 bi=N+1 － ai。例如解 1，3，5，2，4關(guān)于棋盤左右對(duì)稱的解為 5，3，1，4，2。

性質(zhì)2 如果Q=(a1，a2，…，aN)為N皇后問(wèn)題的一個(gè)解，則它關(guān)于棋盤次對(duì)角線對(duì)稱的解為Q2=(c1，c2，…，cN)，其中 Q2的第 N+1 － ai個(gè)值為 N+1－i，即 cN+1－ai=N+1 －i。例如解 1，3，5，2，4 關(guān)于棋盤次對(duì)角線對(duì)稱的解為 3，1，4，2，5。

性質(zhì)3 如果Q=(a1，a2，…，aN)為N皇后問(wèn)題的一個(gè)解，則它關(guān)于棋盤上下對(duì)稱的解為Q3=(d1，d2，…，dN)，其中 Q3的第 i個(gè)值為 aN+1－i，即 di=aN+1－i;例如解1，3，5，2，4 關(guān)于棋盤上下對(duì)稱的解為4，2，5，3，1。

性質(zhì)4 如果Q=(a1，a2，…，aN)為N皇后問(wèn)題的一個(gè)解，則它關(guān)于棋盤主對(duì)角線對(duì)稱的解為Q4=(e1，e2，…，eN)，其中 Q4的第 ai個(gè)值為 i，即 eai=i。例如解1，3，5，2，4關(guān)于棋盤主對(duì)角線對(duì)稱的解為1，4，2，5，3。

容易驗(yàn)證性質(zhì)1至4與文獻(xiàn)[12]中的4個(gè)三維旋轉(zhuǎn)性質(zhì)等價(jià)，但敘述更簡(jiǎn)單更易于算法實(shí)現(xiàn)。表1為算法1計(jì)算出的5皇后問(wèn)題的解。其第一行從左到右，緊接著在第二行從右到左為解的產(chǎn)生順序。同一列的解具有左右對(duì)稱性。

表1 5皇后問(wèn)題的解

圖3 為5 皇后解 1，3，5，2，4 和2，5，3，1，4 對(duì)稱示例。圖3中每5×5的方格表示一個(gè)棋盤，方格中的數(shù)字表示在對(duì)應(yīng)行中的相應(yīng)列放置皇后。有線相連的方格表示兩個(gè)解相互對(duì)稱，兩個(gè)方格之間連線上的文字表示對(duì)稱的類型。粗虛線左側(cè)為解1，3，5，2，4的左右、上下、主對(duì)角線和次對(duì)角線的對(duì)稱解。粗虛線右側(cè)表示解 2，5，3，1，4 的左右、上下、主對(duì)角線和次對(duì)角線的對(duì)稱解均為解 4，1，3，5，2。

圖3 5皇后解1，3，5，2，4 和2，5，3，1，4 對(duì)稱示例

圖4為5皇后全部10個(gè)解對(duì)稱情況。圖4中每個(gè)頂點(diǎn)表示一個(gè)解，有邊相連的頂點(diǎn)表示兩個(gè)解相互對(duì)稱，邊上的文字表示對(duì)稱的類型。

圖4 5皇后全部10個(gè)解對(duì)稱情況

4 N皇后優(yōu)化算法

可以結(jié)合算法1和性質(zhì)1描述的左右對(duì)稱性，得到一個(gè)優(yōu)化算法。從圖2可以看出粗虛線左側(cè)的解正好和右側(cè)的解左右對(duì)稱。因此只需在排列樹(shù)的左側(cè)搜索滿足條件的解，再利用對(duì)稱性計(jì)算右側(cè)的解。在棧S1和S2采用順序存儲(chǔ)，且元素以遞增順序入隊(duì)時(shí)，優(yōu)化的N皇后非遞歸算法，只需在算法1的基礎(chǔ)上做如下修改。

(1)在算法1 的第4.1.2 和4.1.3 之間增加一個(gè)判定條件，“如果n為偶數(shù)且S2[1]大于n/2，或者n為奇數(shù)且 S2[1]大于1+n/2 且 S2[2]大于 n/2，算法結(jié)束?！逼渲?，S2[1]表示為棧S2棧底元素。

(2)修改4.2.1為“從 S2的棧底開(kāi)始，從下往上依次輸出棧中元素產(chǎn)生一個(gè)新解;同時(shí)依據(jù)左右對(duì)稱性產(chǎn)生另一個(gè)解。解的個(gè)數(shù)加2?！?/p>

表2 算法1、優(yōu)化后的算法及文獻(xiàn)[8]的運(yùn)行時(shí)間和解的個(gè)數(shù)

從圖1知4皇后解空間的排列樹(shù)共有64個(gè)節(jié)點(diǎn)，從圖2知在計(jì)算4皇后解時(shí)只訪問(wèn)了左半樹(shù)中的16個(gè)節(jié)點(diǎn)。搜索節(jié)點(diǎn)為解空間的25%，性能的提升還是比較明顯的。為了與同樣采用回溯法，但利用位運(yùn)算操作，基于Erlang語(yǔ)言平臺(tái)計(jì)算N皇后問(wèn)題解的文獻(xiàn)[8]進(jìn)行比較，同樣在 Core 2、2.94 GHz、2 GB內(nèi)存的電腦上進(jìn)行試驗(yàn)。使用C++程序設(shè)計(jì)語(yǔ)言，實(shí)現(xiàn)了算法1和優(yōu)化的N皇后非遞歸算法，計(jì)算了11～18皇后問(wèn)題的解。算法1、利用對(duì)稱性優(yōu)化后的算法及文獻(xiàn)[8]的運(yùn)行時(shí)間和解的個(gè)數(shù)如表2所示。

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

針對(duì)非遞歸方法相對(duì)速度快，但是程序的邏輯結(jié)構(gòu)卻很復(fù)雜的問(wèn)題，筆者采用棧和隊(duì)列實(shí)現(xiàn)了利用回溯法計(jì)算N皇后問(wèn)題的一種新的非遞歸算法，該算法邏輯清晰，并在搜索過(guò)程中進(jìn)行剪枝，使得每次回溯后只需搜索每一行可以放置皇后的位置，從而提高了算法的效率。同時(shí)如理論分析及表2所示，利用性質(zhì)1能極大地提高N皇后問(wèn)題的計(jì)算效率，相比文獻(xiàn)[8]計(jì)算效率也有一定的提高。但是，從圖3和圖4可以看出，N皇后問(wèn)題的解相互之間具有較復(fù)雜的對(duì)稱性。如何結(jié)合其余3個(gè)性質(zhì)進(jìn)一步縮小搜索空間提高計(jì)算效率是一個(gè)需要繼續(xù)研究的問(wèn)題。

[1]Jordan Bell，Brett Stevens.A survey of known results and research areas for N-Queens[J].Discrete Mathematics，2009，309(1):1-31.

[2]Anany Levitin.算法設(shè)計(jì)與分析基礎(chǔ)(第2版)[M].潘彥譯.北京:清華大學(xué)出版社，2007:315-316.

[3]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京:電子工業(yè)出版社，2001:132-135.

[4]Solomon W Golomb，Leonard D Baumert.Backtrack programming[J].Journal of the ACM，1965，12(4):516-524.

[5]韓宇南，呂英華，黃小紅.并行改進(jìn)回溯算法實(shí)現(xiàn)N皇后問(wèn)題的快速計(jì)數(shù)[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(36):1-3.

[6]Martin Richards.Backtracking Algorithms in MCPL Using Bit Patterns and Recursion[R].UCAM-CL-TR-433.United Kingdom:University of Cambridge，Computer Laboratory，1997.

[7]潘大志，杜勇，譚代倫，等.位運(yùn)算在N皇后問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(32):61-62.

[8]向宏，孫黎明，桑軍.改進(jìn)的基于Erlang的N皇后問(wèn)題算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48(10):64-67.

[9]Jacek Mandziuk，Bohdan Macukow.A neural network designed to solve the N-queens problem[J].Biological Cybernetics，1992，66(4):375-379.

[10]Wei Zhang，Zheng Tang.A new algorithm using hopfield neural network with CHN for N-queens problem[J].International Journal of Computer Science and Network Security，2009，9(4):36-41.

[11]Sosic Rok，Gu Jun.A polynomial time algorithm for the NQueens problem[J].SIGART Bulletin，1990，1(3):7-11.

[12]黃達(dá)峰.N皇后問(wèn)題解的構(gòu)造及等價(jià)性分析[D].廣州:中山大學(xué)，2008.

[13]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京:清華大學(xué)出版社，2006:44-65.

[14]Larry Nyhoff.數(shù)據(jù)結(jié)構(gòu)與算法分析—C++語(yǔ)言描述(第2版)[M].黃達(dá)明譯.北京:清華大學(xué)出版社，2006:280-309，345-361.