N 皇後問題：位運算極致優化解法

傳統回溯 vs 位運算

位運算核心思想

• 用整數的二進制位表示列佔用：第 i 位 = 1 表示第 i 列有皇后。
• 三個掩碼：
  • row：列衝突
  • ld (left diagonal)：左下對角線衝突（下一行左移 1 位）
  • rd (right diagonal)：右下對角線衝突（下一行右移 1 位）
• 可用位置：pos = upperlim & ~(row | ld | rd)（upperlim 低 N 位全 1）。
• 取最低可用位：p = pos & -pos（隔離 lowest set bit）。
• 遞歸：test(row|p, (ld|p)<<1, (rd|p)>>1)。

完整代碼

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long sum = 0, upperlim = 1;

void test(long row, long ld, long rd) {
    if (row != upperlim) {
        long pos = upperlim & ~(row | ld | rd);
        while (pos) {
            long p = pos & -pos;        // 最右可用位
            pos -= p;                   // 移除該位
            test(row + p, (ld + p) << 1, (rd + p) >> 1);
        }
    } else {
        ++sum;                          // 找到一解
    }
}

int main(int argc, char* argv[]) {
    time_t tm = time(0);
    int n = (argc > 1) ? atoi(argv[1]) : 16;
    if (n < 1 || n > 32) { puts("1-32"); return -1; }

    upperlim = (upperlim << n) - 1;     // 低 n 位置 1
    printf("%d皇后 上限=%ld\n", n, upperlim);
    test(0, 0, 0);
    printf("共%ld種排列，耗時%d秒\n", sum, (int)(time(0)-tm));
    return 0;
}

關鍵技巧解析

1. upperlim = (1<：生成掩碼 0b111...1 (n 個 1)。
2. pos = upperlim & ~(row|ld|rd)：同時排除列、兩條對角線衝突。
3. p = pos & -pos：lowbit 技巧，取最低 1 位（對應最右可用列）。
4. (ld+p)<<1 / (rd+p)>>1：下一行對角線衝突相對當前行左移/右移 1 列。

N=13:  73712 解  <0.1s
N=14: 365596 解  ~0.3s
N=15: 2279184 解 ~2s
N=16: 14772512 解 ~14s