深入N皇后問(wèn)題的兩個(gè)最高效算法的詳解

更新時(shí)間：2013年05月24日 16:01:55 作者：

本篇文章是對(duì)N皇后問(wèn)題的兩個(gè)最高效的算法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

N皇后問(wèn)題是一個(gè)經(jīng)典的問(wèn)題，在一個(gè)N*N的棋盤(pán)上放置N個(gè)皇后，每行一個(gè)并使其不能互相攻擊（同一行、同一列、同一斜線上的皇后都會(huì)自動(dòng)攻擊）。
一、求解N皇后問(wèn)題是算法中回溯法應(yīng)用的一個(gè)經(jīng)典案例
回溯算法也叫試探法，它是一種系統(tǒng)地搜索問(wèn)題的解的方法?；厮菟惴ǖ幕舅枷胧牵簭囊粭l路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來(lái)，換一條路再試。
在現(xiàn)實(shí)中，有很多問(wèn)題往往需要我們把其所有可能窮舉出來(lái)，然后從中找出滿足某種要求的可能或最優(yōu)的情況，從而得到整個(gè)問(wèn)題的解?；厮菟惴ň褪墙鉀Q這種問(wèn)題的“通用算法”，有“萬(wàn)能算法”之稱。N皇后問(wèn)題在N增大時(shí)就是這樣一個(gè)解空間很大的問(wèn)題，所以比較適合用這種方法求解。這也是N皇后問(wèn)題的傳統(tǒng)解法，很經(jīng)典。
下面是算法的高級(jí)偽碼描述，這里用一個(gè)N*N的矩陣來(lái)存儲(chǔ)棋盤(pán)：
1) 算法開(kāi)始, 清空棋盤(pán)，當(dāng)前行設(shè)為第一行，當(dāng)前列設(shè)為第一列
2) 在當(dāng)前行，當(dāng)前列的位置上判斷是否滿足條件(即保證經(jīng)過(guò)這一點(diǎn)的行,列與斜線上都沒(méi)有兩個(gè)皇后)，若不滿足，跳到第4步
3) 在當(dāng)前位置上滿足條件的情形：
在當(dāng)前位置放一個(gè)皇后，若當(dāng)前行是最后一行，記錄一個(gè)解；
若當(dāng)前行不是最后一行，當(dāng)前行設(shè)為下一行, 當(dāng)前列設(shè)為當(dāng)前行的第一個(gè)待測(cè)位置；
若當(dāng)前行是最后一行，當(dāng)前列不是最后一列，當(dāng)前列設(shè)為下一列；
若當(dāng)前行是最后一行，當(dāng)前列是最后一列，回溯，即清空當(dāng)前行及以下各行的棋盤(pán)，然后，當(dāng)前行設(shè)為上一行，當(dāng)前列設(shè)為當(dāng)前行的下一個(gè)待測(cè)位置；
以上返回到第2步
4) 在當(dāng)前位置上不滿足條件的情形：
若當(dāng)前列不是最后一列，當(dāng)前列設(shè)為下一列，返回到第2步;
若當(dāng)前列是最后一列了，回溯，即，若當(dāng)前行已經(jīng)是第一行了，算法退出，否則，清空當(dāng)前行及以下各行的棋盤(pán)，然后，當(dāng)前行設(shè)為上一行，當(dāng)前列設(shè)為當(dāng)前行的下一個(gè)待測(cè)位置，返回到第2步;
算法的基本原理是上面這個(gè)樣子，但不同的是用的數(shù)據(jù)結(jié)構(gòu)不同，檢查某個(gè)位置是否滿足條件的方法也不同。為了提高效率，有各種優(yōu)化策略，如多線程，多分配內(nèi)存表示棋盤(pán)等。

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

復(fù)制代碼代碼如下:

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

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

復(fù)制代碼代碼如下:

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

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

復(fù)制代碼代碼如下:

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

遞歸解法：

復(fù)制代碼代碼如下:

#include <stdio.h>
#include <stdlib.h>
const int N=20;   //最多放皇后的個(gè)數(shù)
int q[N];         //各皇后所在的行號(hào)
int cont = 0;     //統(tǒng)計(jì)解得個(gè)數(shù)
//輸出一個(gè)解
void print(int n)
{
 int i,j;
 cont++;
 printf("第%d個(gè)解：",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");
 }
}
//檢驗(yà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;
}
//放置皇后到棋盤(pán)上
void place(int k,int n)  
{
 int j;
 if(k>n)
  print(n);
 else
 {
  for(j=1;j<=n;j++)   //試探第k行的每一個(gè)列
  {
   if(find(k,j))
   {
    q[k] = j;
    place(k+1,n);  //遞歸總是在成功完成了上次的任務(wù)的時(shí)候才做下一個(gè)任務(wù)
   }
  }
 }
}
int main(void)
{
 int n;
 printf("請(qǐng)輸入皇后的個(gè)數(shù)(n<=20),n=:");
 scanf("%d",&n);
 if(n>20)
  printf("n值太大，不能求解!\n");
 else
 {
  printf("%d皇后問(wèn)題求解如下(每列的皇后所在的行數(shù)):\n",n);
  place(1,n);        //問(wèn)題從最初狀態(tài)解起
  printf("\n");
 }
 system("pause");
 return 0;
}

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

復(fù)制代碼代碼如下:

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

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

復(fù)制代碼代碼如下:

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

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

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

                // 將pos最右邊為1的bit清零  
                // 也就是為獲取下一次的最右可用列使用做準(zhǔn)備，  
                // 程序?qū)?lái)會(huì)回溯到這個(gè)位置繼續(xù)試探  
                pos -= p;                             

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

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

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

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

        // N個(gè)皇后只需N位存儲(chǔ)，N列中某列有皇后則對(duì)應(yīng)bit置1。  
        upperlim = (upperlim << n) - 1;           

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

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

您可能感興趣的文章: