N 皇後問題：遞歸回溯法 C++ 實現與優化思路

問題描述

在 N×N 棋盤上放置 N 個皇後，任意兩個不同行、不同列、不同對角線。求所有合法擺放方案數。

核心洞察：一維數組即可

queen[row] = col 表示第 row 行皇後在第 col 列。檢查衝突只需 O(1)：

bool check(int row) {
    for (int i = 0; i < row; ++i) {
        if (queen[i] == queen[row]) return false;           // 同列
        if (abs(queen[i] - queen[row]) == row - i) return false; // 同對角線
    }
    return true;
}

遞歸回溯框架

void solve(int row) {
    if (row == N) { count++; print(); return; }
    for (int col = 0; col < N; ++col) {
        queen[row] = col;
        if (check(row)) solve(row + 1);
    }
}

完整可運行代碼

#include <iostream>
#include <vector>
#include <cmath>

int N, total = 0;
std::vector<int> queen;

bool check(int row) {
    for (int i = 0; i < row; ++i)
        if (queen[i] == queen[row] || std::abs(queen[i] - queen[row]) == row - i)
            return false;
    return true;
}

void dfs(int row) {
    if (row == N) { total++; return; }
    for (int col = 0; col < N; ++col) {
        queen[row] = col;
        if (check(row)) dfs(row + 1);
    }
}

int main() {
    std::cin >> N;
    queen.resize(N);
    dfs(0);
    std::cout << total << '\n';
    return 0;
}

優化方向

1. 位運算加速：用三個整數 cols, diag1, diag2 位掩碼表示佔用，O(1) 判斷且極快
2. 對稱性剪枝：利用棋盤對稱性僅搜索一半
3. 迭代非遞歸：手動棧避免函數調用開銷

複雜度

時間 O(N!)，空間 O(N)。N=14 以內秒級解出，N=15 需優化。

參考

同類實現：活在二次元的偽觸博客