圖論與 DFS 算法深度解析：C++ 實現八皇後問題完整指南

問題背景

八皇後問題是經典的回溯算法案例：在 8×8 棋盤上放置 8 個皇後，使其兩兩不在同一行、同一列、同一對角線。本文結合圖結構與深度優先搜索（DFS），提供完整的 C++ 實現與思路解析，適合數據結構初學者進階。

核心思路：狀態空間樹 + 剪枝

將問題轉化為在狀態空間樹中尋找合法葉子節點：

• 每一層代表一行，每個節點代表該行皇後所在的列
• DFS 遍歷樹，遇到衝突立即回溯（剪枝）
• 利用一維數組 `col[row] = column` 存儲狀態，空間複雜度 O(N)

關鍵衝突判定邏輯

bool isValid(int row, int col) {
    for (int i = 0; i < row; ++i) {
        // 同列衝突
        if (cols[i] == col) return false;
        // 主對角線衝突：row - col == i - cols[i]
        // 副對角線衝突：row + col == i + cols[i]
        if (abs(row - i) == abs(col - cols[i])) return false;
    }
    return true;
}

完整 C++ 實現代碼

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int N = 8;
vector cols(N);
int solutions = 0;

void dfs(int row) {
    if (row == N) {
        // 找到一個解，輸出棋盤
        ++solutions;
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c)
                cout << (cols[r] == c ? "Q " : ". ");
            cout << '\n';
        }
        cout << "\n---\n";
        return;
    }
    for (int c = 0; c < N; ++c) {
        if (isValid(row, c)) {
            cols[row] = c;
            dfs(row + 1);
        }
    }
}

int main() {
    dfs(0);
    cout << "Total solutions: " << solutions << endl; // 92
    return 0;
}

圖論視角的額外收穫

若將每個合法位置視為圖中的節點，衝突關係視為邊，問題等價於尋找圖中的最大獨立集。雖然八皇後規模較小，回溯法已足夠高效，但這一建模思想可擴展至 N 皇後、圖著色等 NP 完全問題的近似求解。

複雜度分析與優化方向

• 時間複雜度：O(N!) 最壞情況，實際剪枝後極快
• 空間複雜度：O(N) 遞歸棧 + 狀態數組
• 優化：位運算加速衝突檢測、對稱性剪枝（僅搜索前一半列）、迭代深ening

總結

八皇後問題是理解回溯、DFS、剪枝策略的絕佳切入點。掌握「狀態表示 → 合法性判定 → 遞歸搜索 → 回溯恢復」這套模板後，可輕鬆遷移至解數獨、全排列、子集生成等經典問題。建議動手調試代碼，觀察遞歸調用棧變化，加深對遞歸本質的理解。