HDOJ 2553 N皇后問題：經典回溯與位運算優化

問題描述

在 N×N 棋盤放 N 個皇后，任意兩個不同行、列、對角線。N ≤ 10，求解數。多測試用例，N=0 結束。

回溯核心邏輯

按行遞歸，每行枚舉列。需快速判斷衝突：

• 列衝突：col[j] 標記。
• 主對角線（行-列固定）：diag1[row-col+N]。
• 副對角線（行+列固定）：diag2[row+col]。

代碼實現

void dfs(int row, int cols, int d1, int d2) {
    if (row > n) { ++cnt; return; }
    int avail = (~(cols | d1 | d2)) & ((1<>1);
    }
}

位掩碼同時表示三條衝突線，無需數組，極大加速。

結果對照表（N=1..10）

1:1  2:0  3:0  4:2  5:10  6:4  7:40  8:92  9:352  10:724