解題說明
N-Queens II
題目描述：給定整數 n，回傳 n 皇后問題的不同解法數量。在 n×n 棋盤上放置 n 個皇后，使得任意兩個皇后不在同一行、同一列或同一對角線上。
解題思路：使用回溯法逐行放置皇后（每行恰好放一個）。為了快速判斷某一列是否被佔用，使用三個整數作為位元集合：
cols：記錄哪些列已被佔用。diag1：記錄哪些主對角線（/，行 + 列相同）已被佔用。diag2：記錄哪些副對角線（\，行 - 列相同）已被佔用。
在第 row 行嘗試每一列 col：若對應位元均為 0（未被攻擊），則放置皇后，設定三個位元集合的對應位，遞迴至下一行，完成後清除位元（回溯）。當 row == n 時代表成功放置 n 個皇后，計數器加一。此法利用位元運算使每次合法性檢查為 O(1)，整體效率遠優於逐格掃描。
C++ 解法
複雜度分析
時間複雜度：O(n!) — 第一行有 n 個選擇，第二行最多 n-1 個，依此類推，上界為 n!；實際因對角線剪枝而更少。
空間複雜度：O(n) — 遞迴深度為 n（每行一層），位元集合使用 O(1) 額外空間，無需儲存棋盤。
虛擬碼
1. Initialize count = 0.
2. Call backtrack(row=0, cols=0, diag1=0, diag2=0).
3. In backtrack(row, cols, diag1, diag2):
a. If row == n: increment count and return.
b. For col from 0 to n-1:
- Compute d1 = row + col, d2 = row - col + n - 1.
- If bit col in cols is set, skip.
- If bit d1 in diag1 is set, skip.
- If bit d2 in diag2 is set, skip.
- Set bits: cols |= (1<<col), diag1 |= (1<<d1), diag2 |= (1<<d2).
- Recurse: backtrack(row+1, cols, diag1, diag2).
- Unset bits (backtrack).
4. Return count.其他解法
方法一：位元操作最佳化回溯（Gosper's Hack）
直接計算每行所有可用列的位元遮罩（available = ~(cols | diag1 | diag2) & fullMask），再用 pos = available & (-available) 逐個取出最低位元，避免顯式 for 迴圈。時間複雜度同為 O(n!)，但常數因子更小，實際速度更快，常用於競程解法。
方法二：標準回溯 + 陣列標記
用三個 boolean 陣列 col_used[n]、diag1_used[2n]、diag2_used[2n] 代替位元集合，邏輯相同但較易理解。時間複雜度 O(n!)，空間複雜度 O(n)。適合初學者理解回溯框架後再進階到位元版本。
延伸思考
- N-Queens I（LeetCode 51）要求輸出所有解的棋盤佈局，若在本題基礎上修改，需要哪些額外空間和時間代價？
- 當 n 非常大（例如 n = 20 以上），有哪些方法可以進一步加速，例如利用對稱性將搜尋空間減半？
- 除了逐行放置皇后的策略外，是否可以改為逐列或逐對角線放置？這些策略對剪枝效率有何影響？