八皇后問題深度解析：回溯算法經典實現與C語言代碼詳解

八皇后問題是計算機科學與數學領域中最著名的經典問題之一，作為回溯算法的教科書級案例，它不僅展示了遞歸思想的優雅，更蘊含著豐富的算法優化智慧。本文將從問題起源、數學建模、算法設計到代碼實現，為您全方位剖析這個迷人的棋盤謎題。

問題背景與歷史演進

1850年，數學巨匠高斯首次提出：在標準8×8國際象棋棋盤上放置八個皇后，使任意兩個皇后都不在同一行、同一列或同一對角線上。高斯初步估計有76種解法，但1854年柏林象棋雜誌刊登了40種不同解答，後經圖論方法證實共有92種本質不同解法（若考慮旋轉鏡像對稱，則有12種基本解）。

隨著計算機誕生，該問題成為驗證編程語言性能、教學遞歸回溯算法的標準測試案例。維基百科將其推廣為N皇后問題：當且僅當 n=1 或 n≥4 時存在解。

核心約束條件建模

在二維坐標系中，皇后位置 (i, j) 需滿足三大約束：

• 行約束：同一行僅能有一個皇后 → 通過按行遞歸天然滿足
• 列約束：同一列不能重複 → 檢查 queen[0..i-1][j]
• 對角線約束：主對角線 (i-j 固定)、副對角線 (i+j 固定) 不能重複

回溯算法設計思路

採用「逐行放置 + 衝突檢測 + 回溯撤銷」策略：

1. 從第0行開始，嘗試在每列放置皇后
2. 調用 check() 驗證列、左上、右上三個方向是否衝突
3. 若安全則遞歸處理下一行 put(i+1)
4. 若到達第8行（i≥8），輸出一個完整解
5. 回溯時將 queen[i][j] 重置為0，繼續嘗試下一列

C語言完整實現代碼

#include <stdio.h>

int queen[8][8];  // 棋盤狀態：1=有皇后，0=空
int m = 1;        // 解法計數器

// 衝突檢測：返回0表示安全，>0表示衝突數
int check(int i, int j) {
    int k = 0, a, b;
    
    // 檢查同列
    for (a = 0; a < i; a++)
        if (queen[a][j] == 1) k++;
    
    // 檢查左上對角線 (i-1,j-1) (i-2,j-2)...
    for (a = i-1, b = j-1; a >= 0 && b >= 0; a--, b--)
        if (queen[a][b] == 1) k++;
    
    // 檢查右上對角線 (i-1,j+1) (i-2,j+2)...
    for (a = i-1, b = j+1; a >= 0 && b < 8; a--, b++)
        if (queen[a][b] == 1) k++;
    
    return k;
}

// 遞歸放置皇后
void put(int i) {
    int j;
    if (i >= 8) {  // 找到一組完整解
        printf("第%d種解法:\n", m++);
        for (i = 0; i < 8; i++) {
            for (j = 0; j < 8; j++)
                printf(queen[i][j] == 1 ? "%d " : "- ", j);
            printf("\n");
        }
        printf("\n");
    } else {  // 逐列嘗試放置
        for (j = 0; j < 8; j++) {
            queen[i][j] = 1;           // 嘗試放置
            if (check(i, j) == 0)      // 安全則遞歸
                put(i + 1);
            queen[i][j] = 0;           // 回溯撤銷
        }
    }
}

int main() {
    put(0);  // 從第0行開始
    return 0;
}

代碼關鍵點解析

1. 二維數組 vs 一維優化

本代碼使用 int queen[8][8] 直觀存儲棋盤，雖空間佔用較大（64字節），但邏輯清晰。進階優化可用一維數組 col[8] 記錄每行皇后列號，空間壓縮至32字節，檢測邏輯改為：

// 一維數組衝突檢測
for (int k = 0; k < row; k++) {
    if (col[k] == col[row] || 
        abs(col[k] - col[row]) == row - k)  // 對角線判斷
        return 0;  // 衝突
}