用位操作實現的n皇後問題

C語言是我大一時期專業課所學習的第一門語言，離現在差不多也有將近5年的時間。最近想重拾起來，買了一本Plauger大牛的<<The standard C library>>，簡單翻了一下，覺得自己如井底之蛙一樣。。。以前對C的理解只是皮毛，孰不知這門極其優秀的跨平台可移植的編譯語言還有如此精彩的實現。
      前幾天整理文檔，發現了這段用C bit實現的N皇後算法，花了半天時間才把它搞明白。。大家都知道，n皇後的一般解法是回溯，要用一個二維數組表示棋盤，按逐行（列）進行解搜索，對於每個當前解都要進行判斷，如成功則繼續；失敗則回溯。
      這段用bit實現的代碼極其簡明。只不過它只是用了一個一維的數組，按行搜索，將列上的、對象線上的限制歸一。
      感興趣的朋友可以看下：html">http://jsomers.com/nqueen_demo/nqueens.html 作者的方法跟下面的方法大同小異。
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4
 5 long int sum = 0, upperlim = 1;
 6
 7 void test(long  row, long  ld, long  rd)
 8 {
 9     //printf("%ld %ld %ld ",row,ld,rd);
10     //printf("%ld ",row);
11     //printf(" %ld ",upperlim);
12     if(row != upperlim)
13     {
14         long pos = upperlim & ~(row|ld|rd);
15         //printf("%ld ",pos);
16         while(pos!= 0)
17         {
18           //    printf("%ld ",pos);
19               long p = pos & -pos;
20               pos = pos - p; //取得可以放皇後的最右邊的列
21               test(row + p,(ld + p)<<1, (rd + p)>>1);
22           }  
23       return;
24      }
25       else
26     {
27         sum++;
28         return;
29     }
30 }
31
32 int main(int  argc, char  *argv[])
33 {
34       time_t tm;
35       int n = 16;
36       if(argc  !=   1) n = atoi(argv[1]);
37       tm = time(0);
38       if((n < 1)||(n > 32))
39       {
40         printf("只能計算1-32之間的皇後問題 ");
41         exit(-1);
42       }
43       printf( "%d皇後 ",n);
44        printf("%ld ",upperlim);
45       upperlim = (upperlim << n) - 1;      //所有位都是1
46          printf("%ld ",upperlim);
47       test(0,0,0);
48       printf( "共有%ld種排列,計算時間%d秒 ",sum,(int)(time(0)-tm));
49       system("pause");
50       return 0;
51 }