八皇后問題 C 語言遞迴回溯完整實作與註解

問題描述

在 8×8 棋盤放置 8 個皇后，任兩個不同行、不同列、不同對角線。輸出所有解。

核心資料結構

int C[8]：C[row] = col 表示第 row 行皇后放在 col 列。一維陣列隱含「不同行」約束。

完整程式碼（含詳細註解）

#include 
#include 

void search(int *C, int n, int cur) {
    if (cur == n) {                     // 所有行已放置，輸出一解
        printf("解：\n");
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++)
                printf(C[r] == c ? "# " : "0 ");
            printf("\n");
        }
        return;
    }
    for (int col = 0; col < n; col++) { // 當前行嘗試每一列
        int ok = 1;
        C[cur] = col;
        for (int row = 0; row < cur; row++) {  // 檢查與前幾行是否衝突
            if (C[cur] == C[row] ||              // 同列
                C[cur] - C[row] == cur - row ||  // 主對角線
                C[cur] - C[row] == row - cur) {  // 副對角線
                ok = 0; break;
            }
        }
        if (ok) search(C, n, cur + 1);  // 無衝突，遞迴下一行
    }
}

void HuangHou(int n) {
    int *C = (int*)malloc(sizeof(int) * n);
    search(C, n, 0);
    free(C);
}

int main() {
    HuangHou(8);
    return 0;
}

衝突判斷幾何意義

• C[cur] == C[row]：同一直欄。
• C[cur] - C[row] == cur - row：行差等於列差 → 主對角線（左上右下）。
• C[cur] - C[row] == row - cur：行差等於負列差 → 副對角線（右上左下）。

複雜度

• 時間：O(N!) 級別，N=8 僅 92 解，瞬間完成。
• 空間：O(N) 遞迴深度 + 陣列。

優化方向

1. 位運算加速：用三個整數位掩碼分別記錄列、主對角、副對角佔用。
2. 對稱性剪枝：利用棋盤對稱性減少搜尋空間。