深入N皇后問題的兩個最高效算法的詳解

2020-02-24 14:28:00

字體：大中小

供稿：網(wǎng)友

皇后N問題的兩種算法是比特運(yùn)算法，前者是經(jīng)典算法，后者是目前公認(rèn)的最有效的算法，后者至少將前者的效率提高一個數(shù)量級，下面是武林技術(shù)頻道小編為大家深入N皇后問題的兩個最高效算法的詳解。
一、求解N皇后問題是算法中回溯法應(yīng)用的一個經(jīng)典案例
回溯算法也叫試探法，它是一種系統(tǒng)地搜索問題的解的方法。回溯算法的基本思想是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試。
在現(xiàn)實中，有很多問題往往需要我們把其所有可能窮舉出來，然后從中找出滿足某種要求的可能或最優(yōu)的情況，從而得到整個問題的解。回溯算法就是解決這種問題的“通用算法”，有“萬能算法”之稱。N皇后問題在N增大時就是這樣一個解空間很大的問題，所以比較適合用這種方法求解。這也是N皇后問題的傳統(tǒng)解法，很經(jīng)典。
下面是算法的高級偽碼描述，這里用一個N*N的矩陣來存儲棋盤：
1) 算法開始, 清空棋盤，當(dāng)前行設(shè)為第一行，當(dāng)前列設(shè)為第一列
2) 在當(dāng)前行，當(dāng)前列的位置上判斷是否滿足條件(即保證經(jīng)過這一點的行,列與斜線上都沒有兩個皇后)，若不滿足，跳到第4步
3) 在當(dāng)前位置上滿足條件的情形：
在當(dāng)前位置放一個皇后，若當(dāng)前行是最后一行，記錄一個解；
若當(dāng)前行不是最后一行，當(dāng)前行設(shè)為下一行, 當(dāng)前列設(shè)為當(dāng)前行的第一個待測位置；
若當(dāng)前行是最后一行，當(dāng)前列不是最后一列，當(dāng)前列設(shè)為下一列；
若當(dāng)前行是最后一行，當(dāng)前列是最后一列，回溯，即清空當(dāng)前行及以下各行的棋盤，然后，當(dāng)前行設(shè)為上一行，當(dāng)前列設(shè)為當(dāng)前行的下一個待測位置；
以上返回到第2步
4) 在當(dāng)前位置上不滿足條件的情形：
若當(dāng)前列不是最后一列，當(dāng)前列設(shè)為下一列，返回到第2步;
若當(dāng)前列是最后一列了，回溯，即，若當(dāng)前行已經(jīng)是第一行了，算法退出，否則，清空當(dāng)前行及以下各行的棋盤，然后，當(dāng)前行設(shè)為上一行，當(dāng)前列設(shè)為當(dāng)前行的下一個待測位置，返回到第2步;
算法的基本原理是上面這個樣子，但不同的是用的數(shù)據(jù)結(jié)構(gòu)不同，檢查某個位置是否滿足條件的方法也不同。為了提高效率，有各種優(yōu)化策略，如多線程，多分配內(nèi)存表示棋盤等。

在具體解決該問題時，可以將其拆分為幾個小問題。首先就是在棋盤上如何判斷兩個皇后是否能夠相互攻擊，在最初接觸這個問題時，首先想到的方法就是把棋盤存儲為一個二維數(shù)組，然后在需要在第i行第j列放置皇后時，根據(jù)問題的描述，首先判斷是在第i行是否有皇后，由于每行只有一個皇后，這個判斷也可以省略，然后判斷第j列是否有皇后，這個也很簡單，最后需要判斷在同一斜線上是否有皇后，按照該方法需要判斷兩次，正對角線方向和負(fù)對角線方向，總體來說也不難。但是寫完之后，總感覺很笨，因為在N皇后問題中這個函數(shù)的使用次數(shù)太多了，而這樣做效率較差，個人感覺很不爽。上網(wǎng)查看了別人的實現(xiàn)之后大吃一驚，大牛們都是使用一個一維數(shù)組來存儲棋盤，在某個位置上是否有皇后可以相互攻擊的判斷也很簡單。具體細(xì)節(jié)如下：
把棋盤存儲為一個N維數(shù)組a[N]，數(shù)組中第i個元素的值代表第i行的皇后位置，這樣便可以把問題的空間規(guī)模壓縮為一維O(N)，在判斷是否沖突時也很簡單，首先每行只有一個皇后，且在數(shù)組中只占據(jù)一個元素的位置，行沖突就不存在了，其次是列沖突，判斷一下是否有a[i]與當(dāng)前要放置皇后的列j相等即可。至于斜線沖突，通過觀察可以發(fā)現(xiàn)所有在斜線上沖突的皇后的位置都有規(guī)律即它們所在的行列互減的絕對值相等，即| row – i | = | col – a[i] | 。這樣某個位置是否可以放置皇后的問題已經(jīng)解決。
下面要解決的是使用何種方法來找到所有的N皇后的解。上面說過該問題是回溯法的經(jīng)典應(yīng)用，所以可以使用回溯法來解決該問題，具體實現(xiàn)也有兩個途徑，遞歸和非遞歸。遞歸方法較為簡單，大致思想如下：

???? void queen(int row)
??? {
????????????? if (n == row)????? //如果已經(jīng)找到結(jié)果，則打印結(jié)果
??????????????????? print_result();
????????????? else {
????????????????????????? for (k=0 to N) { //試探第row行每一個列
????????????????????????????????? if (can_place(row, k) {
????????????????????????????????????????? place(row, k);?? //放置皇后
???????????????????????????????????????? queen(row + 1);? //繼續(xù)探測下一行
????????????????????????????????? }
???????????????????????? }
???????????? }
??? }

該方法由于在探測第i行后，如果找到一個可以放置皇后的位置j后，則會遞歸探測下一行，結(jié)束后則會繼續(xù)探測i行j+1列，故可以找到所有的N皇后的解。
但是一般來說遞歸的效率比較差，下面重點討論一下該問題的非遞歸實現(xiàn)。
非遞歸方法的一個重要問題時何時回溯及如何回溯的問題。程序首先對N行中的每一行進(jìn)行探測，尋找該行中可以放置皇后的位置，具體方法是對該行的每一列進(jìn)行探測，看是否可以放置皇后，如果可以，則在該列放置一個皇后，然后繼續(xù)探測下一行的皇后位置。如果已經(jīng)探測完所有的列都沒有找到可以放置皇后的列，此時就應(yīng)該回溯，把上一行皇后的位置往后移一列，如果上一行皇后移動后也找不到位置，則繼續(xù)回溯直至某一行找到皇后的位置或回溯到第一行，如果第一行皇后也無法找到可以放置皇后的位置，則說明已經(jīng)找到所有的解程序終止。如果該行已經(jīng)是最后一行，則探測完該行后，如果找到放置皇后的位置，則說明找到一個結(jié)果，打印出來。但是此時并不能再此處結(jié)束程序，因為我們要找的是所有N皇后問題所有的解，此時應(yīng)該清除該行的皇后，從當(dāng)前放置皇后列數(shù)的下一列繼續(xù)探測。
完整的代碼如下：

/**
* 回溯法解N皇后問題
* 使用一個一維數(shù)組表示皇后的位置
* 其中數(shù)組的下標(biāo)表示皇后所在的行
* 數(shù)組元素的值表示皇后所在的列
* 這樣設(shè)計的棋盤，所有皇后必定不在同一行，于是行沖突就不存在了
* date? : 2011-08-03
* author: liuzhiwei
**/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define QUEEN 8???? //皇后的數(shù)目
#define INITIAL -10000?? //棋盤的初始值
int a[QUEEN];??? //一維數(shù)組表示棋盤
void init()? //對棋盤進(jìn)行初始化
{
?int *p;
?for (p = a; p < a + QUEEN; ++p)
?{
??*p = INITIAL;
?}
}
int valid(int row, int col)??? //判斷第row行第col列是否可以放置皇后
{
?int i;
?for (i = 0; i < QUEEN; ++i)?? //對棋盤進(jìn)行掃描
?{
??if (a[i] == col || abs(i - row) == abs(a[i] - col))?? //判斷列沖突與斜線上的沖突
???return 0;
?}
?return 1;
}
void print()??? //打印輸出N皇后的一組解
{
?int i, j;
?for (i = 0; i < QUEEN; ++i)
?{
??for (j = 0; j < QUEEN; ++j)
??{
???if (a[i] != j)????? //a[i]為初始值
????printf("%c ", '.');
???else??????????????? //a[i]表示在第i行的第a[i]列可以放置皇后
????printf("%c ", '#');
??}
??printf("/n");
?}
?for (i = 0; i < QUEEN; ++i)
??printf("%d ", a[i]);
?printf("/n");
?printf("--------------------------------/n");
}
void queen()????? //N皇后程序
{
?int n = 0;
?int i = 0, j = 0;
?while (i < QUEEN)
?{
??while (j < QUEEN)??????? //對i行的每一列進(jìn)行探測，看是否可以放置皇后
??{
???if(valid(i, j))????? //該位置可以放置皇后
???{
????a[i] = j;??????? //第i行放置皇后
????j = 0;?????????? //第i行放置皇后以后，需要繼續(xù)探測下一行的皇后位置，所以此處將j清零，從下一行的第0列開始逐列探測
????break;
???}
???else
???{
????++j;???????????? //繼續(xù)探測下一列
???}
??}
??if(a[i] == INITIAL)???????? //第i行沒有找到可以放置皇后的位置
??{
???if (i == 0)???????????? //回溯到第一行，仍然無法找到可以放置皇后的位置，則說明已經(jīng)找到所有的解，程序終止
????break;
???else??????????????????? //沒有找到可以放置皇后的列，此時就應(yīng)該回溯
???{
????--i;
????j = a[i] + 1;??????? //把上一行皇后的位置往后移一列
????a[i] = INITIAL;????? //把上一行皇后的位置清除，重新探測
????continue;
???}
??}
??if (i == QUEEN - 1)????????? //最后一行找到了一個皇后位置，說明找到一個結(jié)果，打印出來
??{
???printf("answer %d : /n", ++n);
???print();
???//不能在此處結(jié)束程序，因為我們要找的是N皇后問題的所有解，此時應(yīng)該清除該行的皇后，從當(dāng)前放置皇后列數(shù)的下一列繼續(xù)探測。
???//_sleep(600);
???j = a[i] + 1;???????????? //從最后一行放置皇后列數(shù)的下一列繼續(xù)探測
???a[i] = INITIAL;?????????? //清除最后一行的皇后位置
???continue;
??}
??++i;????????????? //繼續(xù)探測下一行的皇后位置
?}
}
int main(void)
{
?init();
?queen();
?system("pause");
?return 0;
}

下面的代碼跟上面的代碼差不多，只是稍微做了一些變化。。上面函數(shù)判斷棋盤某個位置合法性的時候，valid函數(shù)里面的QUEEN可以修改為row的，只需要將前面row行與第row行進(jìn)行比較就可以了，不需要將所有行都與第row進(jìn)行比較的。。。下面的代碼中的check函數(shù)中循環(huán)次數(shù)是k而不是皇后的個數(shù)就是這個原因。。。

#include "iostream"
#include "cmath"
using namespace std;
#define Max 20????? //定義棋盤的最大值
int a[Max];
int show(int S)??? //定義輸出函數(shù)
{
?int i,p,q;
?int b[Max][Max]={0};???? //定義并初始化b[][]輸出數(shù)組
?for(i=1;i<=S;i++)??? //按橫列i順序輸出a[i]數(shù)組坐標(biāo)
?{
??b[i][a[i]]=1;
??printf("(%d,%d)/t",i,a[i]);
?}
?printf("/n");
?for(p=1;p<=S;p++)???? //按棋盤的橫列p順序標(biāo)明皇后的位置
?{
??for(q=1;q<=S;q++)
??{
???if(b[p][q]==1)???? //在第p行第q列放置一個皇后棋子
????printf("●");
???else
????printf("○");
??}
??printf("/n");
?}
?return 0;
}
int check(int k)??? //定義check函數(shù)
{
?int i;
?for(i=1;i<k;i++)??? //將第k行與前面的第1~~k-1行進(jìn)行判斷
?{
??if((a[i]==a[k]) || (a[i]-a[k]==k-i) || (a[i]-a[k]==i-k))??? //檢查是否有多個皇后在同一條直線上
??{
???return 0;
??}
?}
?return 1;
}
void check_m(int num)??? //定義函數(shù)
{
?int k=1,count=0;
?printf("The possible configuration of N queens are:/n");
?a[k]=1;
?while(k>0)
?{
??if(k<=num && a[k]<=num)??? //從第k行第一列的位置開始，為后續(xù)棋子選擇合適位子
??{
???if(check(k)==0)??? //第k行的a[k]列不能放置皇后
???{
????a[k]++;??????? //繼續(xù)探測當(dāng)前行的下一列：a[k]+1
???}
???else
???{
????k++;???????? //第K行的位置已經(jīng)確定了，繼續(xù)尋找第k+1行皇后的位置
????a[k]=1;????? //從第一列開始查找
???}
??}
??else
??{
???if(k>num)???? //若滿足輸出數(shù)組的要求則輸出該數(shù)組
???{
????count++;
????printf("[%d]:? ",count);
????show(num);??? //調(diào)用輸出函數(shù)show()
???}
???//如果k>num會執(zhí)行下面兩行代碼，因為雖然找到了N皇后問題的一個解，但是要找的是所有解，需要回溯，從當(dāng)前放置皇后的下一列繼續(xù)探測
???//如果a[k]>num也會執(zhí)行下面兩行代碼，就是說在當(dāng)前行沒有找到可以放置皇后的位置，于是回溯，從上一行皇后位置的下一列繼續(xù)探測
???k--;????? //棋子位置不符合要求，則退回前一步
???a[k]++;?? //繼續(xù)試探下一列位置
??}
?}
?printf("The count is: %d /n",count);
}
int main(void)
{
?int N,d;
?//system("color 2a");
?do
?{
??printf("********************N皇后問題系統(tǒng)*********************/n/n");
??printf("????????????????? 1. 四皇后問題??????????????????????? /n");
??printf("????????????????? 2. 八皇后問題??????????????????????? /n");
??printf("????????????????? 3. N 皇后問題(N<20)????????????????? /n");
??printf("????????????????? 4. 退出????????????????????????????? /n");
??printf("******************************************************/n");
??printf("/n??? 從數(shù)字1-4之間的數(shù)選擇需要的操作/n/n"); /*提示輸入選項*/
??printf("????? 請輸入你要選擇的功能選項:__/n");
??scanf("%d",&d);
??switch(d)
??{
??case 1:
???check_m(4);????? //4皇后問題
???break;
??case 2:
???check_m(8);???? //8皇后問題
???break;
??case 3:
???printf("請輸入N的值：_");
???fflush(stdin);????? //清除緩沖
???scanf("%d",&N);
???printf("/n");
???if(N>0&&N<20)
???{
????check_m(N);??? //N皇后問題
????break;
???}
???else
???{
????printf("輸入錯誤，請從新輸入：");
????printf("/n/n");
????break;
???}
??case 4:
???exit(0);???? //程序結(jié)束
??}
?}while(1);
?system("pause");
?return 0;
}

遞歸解法：

#include <stdio.h>
#include <stdlib.h>
const int N=20;?? //最多放皇后的個數(shù)
int q[N];???????? //各皇后所在的行號
int cont = 0;???? //統(tǒng)計解得個數(shù)
//輸出一個解
void print(int n)
{
?int i,j;
?cont++;
?printf("第%d個解：",cont);
?for(i=1;i<=n;i++)
??printf("(%d,%d) ",i,q[i]);
?printf("/n");
?for(i=1;i<=n;i++)??????? //行
?{???????????????
??for(j=1;j<=n;j++)??? //列
??{
???if(q[i]!=j)
????printf("x ");
???else
????printf("Q ");
??}
??printf("/n");
?}
}
//檢驗第i行的k列上是否可以擺放皇后
int find(int i,int k)?
{
?int j=1;
?while(j<i)? //j=1~i-1是已經(jīng)放置了皇后的行
?{
??//第j行的皇后是否在k列或(j,q[j])與(i,k)是否在斜線上
??if(q[j]==k || abs(j-i)==abs(q[j]-k))
???return 0;
??j++;
?}
?return 1;
}
//放置皇后到棋盤上
void place(int k,int n)?
{
?int j;
?if(k>n)
??print(n);
?else
?{
??for(j=1;j<=n;j++)?? //試探第k行的每一個列
??{
???if(find(k,j))
???{
????q[k] = j;
????place(k+1,n);? //遞歸總是在成功完成了上次的任務(wù)的時候才做下一個任務(wù)
???}
??}
?}
}
int main(void)
{
?int n;
?printf("請輸入皇后的個數(shù)(n<=20),n=:");
?scanf("%d",&n);
?if(n>20)
??printf("n值太大，不能求解!/n");
?else
?{
??printf("%d皇后問題求解如下(每列的皇后所在的行數(shù)):/n",n);
??place(1,n);??????? //問題從最初狀態(tài)解起
??printf("/n");
?}
?system("pause");
?return 0;
}

二、使用位運(yùn)算來求解N皇后的高效算法
?? 核心代碼如下：

void test(int row, int ld, int rd)
{
?int pos, p;
?if ( row != upperlim )
?{
??pos = upperlim & (~(row | ld | rd ));
??while ( pos )
??{
???p = pos & (~pos + 1);
???pos = pos - p;
???test(row | p, (ld | p) << 1, (rd | p) >> 1);
??}
?}
?else
??++Ans;
}

初始化：　upperlim =? (1 << n)-1; Ans = 0;
調(diào)用參數(shù)：test(0, 0, 0);
和普通算法一樣，這是一個遞歸函數(shù)，程序一行一行地尋找可以放皇后的地方。函數(shù)帶三個參數(shù)row、ld和rd，分別表示在縱列和兩個對角線方向的限制條件下這一行的哪些地方不能放。位于該行上的沖突位置就用row、ld和rd中的1來表示。把它們?nèi)齻€并起來，得到該行所有的禁位，取反后就得到所有可以放的位置（用pos來表示）。
p = pos & (~pos + 1)其結(jié)果是取出最右邊的那個1。這樣，p就表示該行的某個可以放子的位置，把它從pos中移除并遞歸調(diào)用test過程。
注意遞歸調(diào)用時三個參數(shù)的變化，每個參數(shù)都加上了一個禁位，但兩個對角線方向的禁位對下一行的影響需要平移一位。最后，如果遞歸到某個時候發(fā)現(xiàn)row=upperlim了，說明n個皇后全放進(jìn)去了，找到的解的個數(shù)加一。

注：upperlime：=（1 << n）-1 就生成了n個1組成的二進(jìn)制數(shù)。
這個程序是從上向下搜索的。
pos & -pos 的意思就是取最右邊的 1 再組成二進(jìn)制數(shù)，相當(dāng)于 pos &（~pos +1），因為取反以后剛好所有數(shù)都是相反的（怎么聽著像廢話），再加 1 ，就是改變最低位，如果低位的幾個數(shù)都是1，加的這個 1 就會進(jìn)上去，一直進(jìn)到 0 ，在做與運(yùn)算就和原數(shù)對應(yīng)的 1 重合了。舉例可以說明：
原數(shù) 0 0 0 0 1 0 0 0??? 原數(shù) 0 1 0 1 0 0 1 1
取反 1 1 1 1 0 1 1 1??? 取反 1 0 1 0 1 1 0 0
加1??? 1 1 1 1 1 0 0 0??? 加1? 1 0 1 0 1 1 0 1
與運(yùn)算??? 0 0 0 0 1 0 0 0??? and? 0 0 0 0 0 0 0 1
其中呢，這個取反再加 1 就是補(bǔ)碼，and 運(yùn)算與負(fù)數(shù)，就是按位和補(bǔ)碼與運(yùn)算。
?????? (ld | p)<< 1 是因為由ld造成的占位在下一行要右移一下；
?????? (rd | p)>> 1 是因為由rd造成的占位在下一行要左移一下。
ld rd row 還要和upperlime 與運(yùn)算一下，這樣做的結(jié)果就是從最低位數(shù)起取n個數(shù)為有效位置，原因是在上一次的運(yùn)算中l(wèi)d發(fā)生了右移，如果不and的話，就會誤把n以外的位置當(dāng)做有效位。
pos 已經(jīng)完成任務(wù)了還要減去p 是因為？
while 循環(huán)是因為？
在進(jìn)行到某一層的搜索時，pos中存儲了所有的可放位置，為了求出所有解，必須遍歷所有可放的位置，而每走過一個點必須要刪掉它，否則就成死循環(huán)啦！
這個是目前公認(rèn)N皇后的最高效算法。
完整的代碼如下：

??? /*
??? ** 目前最快的N皇后遞歸解決方法
??? ** N Queens Problem
??? ** 試探-回溯算法，遞歸實現(xiàn)
??? */?
??? #include "iostream"?
??? using namespace std;?
??? #include "time.h"?

??? // sum用來記錄皇后放置成功的不同布局?jǐn)?shù)；upperlim用來標(biāo)記所有列都已經(jīng)放置好了皇后。?
??? long sum = 0, upperlim = 1;??????

??? // 試探算法從最右邊的列開始。?
??? void test(long row, long ld, long rd)?
??? {?
??????? if (row != upperlim)?
??????? {?
??????????? // row，ld，rd進(jìn)行“或”運(yùn)算，求得所有可以放置皇后的列,對應(yīng)位為0，?
??????????? // 然后再取反后“與”上全1的數(shù)，來求得當(dāng)前所有可以放置皇后的位置，對應(yīng)列改為1?
??????????? // 也就是求取當(dāng)前哪些列可以放置皇后?
??????????? long pos = upperlim & ~(row | ld | rd);??
??????????? while (pos)??? // 0 -- 皇后沒有地方可放，回溯?
??????????? {?
??????????????? // 拷貝pos最右邊為1的bit，其余bit置0?
??????????????? // 也就是取得可以放皇后的最右邊的列?
??????????????? long p = pos & -pos;???????????????????????????????????????????????

??????????????? // 將pos最右邊為1的bit清零?
??????????????? // 也就是為獲取下一次的最右可用列使用做準(zhǔn)備，?
??????????????? // 程序?qū)頃厮莸竭@個位置繼續(xù)試探?
??????????????? pos -= p;????????????????????????????

??????????????? // row + p，將當(dāng)前列置1，表示記錄這次皇后放置的列。?
??????????????? // (ld + p) << 1，標(biāo)記當(dāng)前皇后左邊相鄰的列不允許下一個皇后放置。?
??????????????? // (ld + p) >> 1，標(biāo)記當(dāng)前皇后右邊相鄰的列不允許下一個皇后放置。?
??????????????? // 此處的移位操作實際上是記錄對角線上的限制，只是因為問題都化歸?
??????????????? // 到一行網(wǎng)格上來解決，所以表示為列的限制就可以了。顯然，隨著移位?
??????????????? // 在每次選擇列之前進(jìn)行，原來N×N網(wǎng)格中某個已放置的皇后針對其對角線?
??????????????? // 上產(chǎn)生的限制都被記錄下來了?
??????????????? test(row + p, (ld + p) << 1, (rd + p) >> 1);???????????????????????????????
??????????? }?
??????? }?
??????? else????
??????? {?
??????????? // row的所有位都為1，即找到了一個成功的布局，回溯?
??????????? sum++;?
??????? }?
??? }?

??? int main(int argc, char *argv[])?
??? {?
??????? time_t tm;?
??????? int n = 16;?

??????? if (argc != 1)?
??????????? n = atoi(argv[1]);?
??????? tm = time(0);?

??????? // 因為整型數(shù)的限制，最大只能32位，?
??????? // 如果想處理N大于32的皇后問題，需要?
??????? // 用bitset數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲?
??????? if ((n < 1) || (n > 32))??????????????????
??????? {?
??????????? printf(" 只能計算1-32之間/n");?
??????????? exit(-1);?
??????? }?
??????? printf("%d 皇后/n", n);?

??????? // N個皇后只需N位存儲，N列中某列有皇后則對應(yīng)bit置1。?
??????? upperlim = (upperlim << n) - 1;??????????

??????? test(0, 0, 0);?
??????? printf("共有%ld種排列, 計算時間%d秒 /n", sum, (int) (time(0) - tm));?
??????? system("pause");?
??????? return 0;?
??? }?

上述代碼還是比較容易看懂的，但我覺得核心的是在針對試探－回溯算法所用的數(shù)據(jù)結(jié)構(gòu)的設(shè)計上。
程序采用了遞歸，也就是借用了編譯系統(tǒng)提供的自動回溯功能。
算法的核心：使用bit數(shù)組來代替以前由int或者bool數(shù)組來存儲當(dāng)前格子被占用或者說可用信息，從這可以看出N個皇后對應(yīng)需要N位表示。
巧妙之處在于：以前我們需要在一個N*N正方形的網(wǎng)格中挪動皇后來進(jìn)行試探回溯，每走一步都要觀察和記錄一個格子前后左右對角線上格子的信息；采用bit位進(jìn)行信息存儲的話，就可以只在一行格子也就是（1行×N列）個格子中進(jìn)行試探回溯即可，對角線上的限制被化歸為列上的限制。
程序中主要需要下面三個bit數(shù)組，每位對應(yīng)網(wǎng)格的一列，在C中就是取一個整形數(shù)的某部分連續(xù)位即可。 row用來記錄當(dāng)前哪些列上的位置不可用，也就是哪些列被皇后占用，對應(yīng)為1。ld，rd同樣也是記錄當(dāng)前哪些列位置不可用，但是不表示被皇后占用，而是表示會被已有皇后在對角線上吃掉的位置。這三個位數(shù)組進(jìn)行“或”操作后就是表示當(dāng)前還有哪些位置可以放置新的皇后，對應(yīng)0的位置可放新的皇后。如下圖所示的8皇后問題求解得第一步：
????????????? row:????????? [ ][ ][ ][ ][ ][ ][ ][*]
????????????? ld:???????????? [ ][ ][ ][ ][ ][ ][*][ ]
????????????? rd:???????????? [ ][ ][ ][ ][ ][ ][ ][ ]
????????????? --------------------------------------
??????????? row|ld|rd:??? [ ][ ][ ][ ][ ][ ][*][*]
所有下一個位置的試探過程都是通過位操作來實現(xiàn)的，這是借用了C語言的好處，詳見代碼注釋。
關(guān)于此算法，如果考慮N×N棋盤的對稱性，對于大N來說仍能較大地提升效率！
位操作－－對優(yōu)化算法有了個新的認(rèn)識
這個是在csdn找到的一個N皇后問題最快的算法，看了好一會才明白，這算法巧妙之處我認(rèn)為有２個：
１、以前都是用數(shù)組來描述狀態(tài)，而這算法采用是的位來描述，運(yùn)算速度可以大大提升，以后寫程序?qū)τ诿枋鰻顟B(tài)的變量大家可以借鑒這個例子，會讓你的程序跑得更快　　　　　　　　　　　　　　　　　　　　　　　　
２、描述每行可放置的位置都是只用row,ld,rd這３個變量來描述，這樣使得程序看起來挺簡潔的。