N 皇后問題：經典回溯算法完整解析與 C 語言實現

N 皇后問題簡介

N 皇後問題是計算機科學中著名的回溯算法經典案例。問題描述為：在一個 N×N 的棋盤上放置 N 個皇後，使任意兩個皇後都不在同一行、同一列或同一斜線上。根據國際象棋規則，皇後可攻擊同行、同列及同斜線上的棋子，因此需找出所有合法的擺放方案總數。

問題輸入輸出規範

輸入：單一整數 n (n ≤ 13)，代表棋盤大小。
輸出：整數，表示合法擺放方法的總數。例如輸入 8，輸出 92（八皇後問題有 92 種解）。

核心算法思路：回溯搜索

採用深度優先搜索（DFS）配合剪枝策略。逐行嘗試放置皇後，利用三個布爾陣列標記列、主對角線、副對角線是否被佔用：

• col[i]：第 i 列是否有皇後
• diag1[row+col]：主對角線（行+列固定）
• diag2[row-col+n-1]：副對角線（行-列固定，加偏移量避免負數）

遞歸函數 search(row) 嘗試在當前行放置皇後，若成功則遞歸處理下一行；若到達第 n+1 行，計數器加一。回溯時需恢復標記陣列。

C 語言完整代碼實現

#include <stdio.h>

int col[20] = {0}, diag1[40] = {0}, diag2[40] = {0};
int n, count = 0;

void search(int row) {
    if (row > n) {
        count++;
        return;
    }
    for (int c = 1; c <= n; c++) {
        int d1 = row + c;
        int d2 = row - c + n;
        if (!col[c] && !diag1[d1] && !diag2[d2]) {
            col[c] = diag1[d1] = diag2[d2] = 1;
            search(row + 1);
            col[c] = diag1[d1] = diag2[d2] = 0; // 回溯恢復
        }
    }
}

int main() {
    scanf("%d", &n);
    search(1);
    printf("%d", count);
    return 0;
}

關鍵點總結

此解法時間複雜度約 O(N!)，但受對角線剪枝影響實際運行極快。n ≤ 13 時瞬間出結果。陣列大小預留 20/40 足夠應對最大情況。遞歸深度僅 n 層，棧溢出風險極低。