// N Queens Problem
// 試探-回溯算法，遞歸實現

// sum用來記錄皇后放置成功的不同布局數；upperlim用來標記所有列都已經放置好了皇后。
long sum = 0, upperlim = 1;?????

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

?// 將pos最右邊為1的bit清零。
???????????????? // 也就是為獲取下一次的最右可用列使用做準備，
???????????????? // 程序將來會回溯到這個位置繼續試探。
?pos -= p;???????????????????????????

?// row + p，將當前列置1，表示記錄這次皇后放置的列。
?// (ld + p) << 1，標記當前皇后左邊相鄰的列不允許下一個皇后放置。
?// (ld + p) >> 1，標記當前皇后右邊相鄰的列不允許下一個皇后放置。
???????????????? // 此處的移位操作實際上是記錄對角線上的限制，只是因為問題都化歸
???????????????? // 到一行網格上來解決，所以表示為列的限制就可以了。顯然，隨著移位
???????????????? // 在每次選擇列之前進行，原來N×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);

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

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

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

上述代碼容易看懂，但我覺得核心的是在針對試探－回溯算法所用的數據結構的設計上。
程序采用了遞歸，也就是借用了編譯系統提供的自動回溯功能。

算法的核心：使用bit數組來代替以前由int或者bool數組來存儲當前格子被占用或者說可用信息，從這

可以看出N個皇后對應需要N位表示。
巧妙之處在于：以前我們需要在一個N*N正方形的網格中挪動皇后來進行試探回溯，每走一步都要觀察

和記錄一個格子前后左右對角線上格子的信息；采用bit位進行信息存儲的話，就可以只在一行格子也

就是（1行×N列）個格子中進行試探回溯即可，對角線上的限制被化歸為列上的限制。
程序中主要需要下面三個bit數組，每位對應網格的一列，在C中就是取一個整形數的某部分連續位即可

。
row用來記錄當前哪些列上的位置不可用，也就是哪些列被皇后占用，對應為1。
ld，rd同樣也是記錄當前哪些列位置不可用，但是不表示被皇后占用，而是表示會被已有皇后在對角線

上吃掉的位置。這三個位數組進行“或”操作后就是表示當前還有哪些位置可以放置新的皇后，對應0

的位置可放新的皇后。如下圖所示的8皇后問題求解得第一步：
row:??????? [ ][ ][ ][ ][ ][ ][ ][*]
ld:???????? [ ][ ][ ][ ][ ][ ][*][ ]
rd:???????? [ ][ ][ ][ ][ ][ ][ ][ ]
------------------------------------
row|ld|rd:? [ ][ ][ ][ ][ ][ ][*][*]
所有下一個位置的試探過程都是通過位操作來實現的，這是借用了C語言的好處，詳見代碼注釋。