代碼實現（集合版，通用易懂）

#include 
#include 
using namespace std;

class Solution {
    int count = 0;
    void backtrack(int row, int n, vector& cols, vector& diag1, vector& diag2) {
        if (row == n) { count++; return; }
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n - 1; // 主對角線索引 0~2n-2
            int d2 = row + col;         // 副對角線索引 0~2n-2
            if (!cols[col] && !diag1[d1] && !diag2[d2]) {
                cols[col] = diag1[d1] = diag2[d2] = true;
                backtrack(row + 1, n, cols, diag1, diag2);
                cols[col] = diag1[d1] = diag2[d2] = false;
            }
        }
    }
public:
    int totalNQueens(int n) {
        vector cols(n), diag1(2*n-1), diag2(2*n-1);
        backtrack(0, n, cols, diag1, diag2);
        return count;
    }
};

位掩碼優化版（高性能）

class Solution {
    int count = 0, n;
    void dfs(int row, int cols, int diag1, int diag2) {
        if (row == n) { count++; return; }
        int available = (~(cols | diag1 | diag2)) & ((1<>1);
        }
    }
public:
    int totalNQueens(int n) {
        this->n = n;
        dfs(0, 0, 0, 0);
        return count;
    }
};

複雜度

• 時間：O(N!) 理論上限，剪枝後實際極快（N=14 約 0.5s）
• 空間：O(N) 遞歸棧 + 狀態存儲

關鍵點

• 對角線索引映射：row-col 範圍 [-(n-1), n-1]，加 n-1 偏移為 [0, 2n-2]
• 位掩碼版利用位運算極大加速，LeetCode 硬核優化方案
• 只需計數不輸出佈局，節省大量字符串構建開銷