八皇後問題：回溯算法經典範式與剪枝優化實戰

編輯：關於C語言

前言

八皇後問題是回溯算法 (Backtracking) 的教科書級案例：在 8×8 棋盤上放置 8 個皇後，使任意兩個皇後不同行、不同列、不同對角線。本文將從暴力枚舉的不可行性切入，推導逐行回溯 + 剪枝的標準解法，提供完整 C 代碼實現，並總結回溯算法的通用設計模式。

一、為什麼暴力枚舉失敗？

若在 64 格中選 8 格放置皇後，組合數 C(64,8) ≈ 4.4×10⁹；若考慮每行必有一皇後，則為 8⁸ = 16,777,216 種。雖在現代 CPU 可跑通，但指數級增長讓 N 皇後 (N>15) 迅速不可計算。核心浪費在：後續行的嘗試建立在前序行非法放置之上。

二、回溯核心邏輯：逐行決策 + 合法性剪枝

狀態表示

用一維數組 pos[row] = col 表示第 row 行皇后所在列。因逐行放置，行沖突天然消除，只需檢查：

列沖突：pos[i] == col
主對角線沖突 (左上-右下)：row - col == i - pos[i] (行差 = 列差)
副對角線沖突 (右上-左下)：row + col == i + pos[i] (行和 = 列和)

遞歸框架

void solve(int row) {
    if (row == N) { print_solution(); return; } // 找到一解
    for (int col = 0; col < N; col++) {
        if (is_valid(row, col)) {
            pos[row] = col;      // 做選擇
            solve(row + 1);      // 遞歸下一行
            pos[row] = -1;       // 撤銷選擇 (回溯)
        }
    }
}

三、完整 C 語言實現

#include 
#include 

#define N 8
int pos[N] = {0};      // pos[row] = col
int solution_count = 0;

// 合法性檢查：O(row) 時間
int is_valid(int row, int col) {
    for (int i = 0; i < row; i++) {
        if (pos[i] == col) return 0;                    // 同列
        if (i + pos[i] == row + col) return 0;          // 副對角線
        if (i - pos[i] == row - col) return 0;          // 主對角線
    }
    return 1;
}

// 打印棋盤
void print_board() {
    printf("Solution #%d:\n", ++solution_count);
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            printf("%c ", (pos[r] == c) ? 'Q' : '.');
        }
        printf("\n");
    }
    printf("\n");
}

// 回溯主函數
void backtrack(int row) {
    if (row == N) {
        print_board();
        return;
    }
    for (int col = 0; col < N; col++) {
        if (is_valid(row, col)) {
            pos[row] = col;
            backtrack(row + 1);
            pos[row] = -1; // 回溯清理 (可選，下輪會覆蓋)
        }
    }
}

int main() {
    backtrack(0);
    printf("Total solutions: %d\n", solution_count); // 92
    return 0;
}

四、進階優化：位運算加速合法性檢查 (O(1))

用三個整數位掩碼分別記錄被佔用的列、主對角線、副對角線：

cols：第 c 位為 1 表示第 c 列被佔用
diag1 (主對角線)：row - col + N - 1 映射到 0~2N-2
diag2 (副對角線)：row + col 映射到 0~2N-2

// 位運算版核心邏輯 (N <= 32 適用 32bit int)
void backtrack_bit(int row, int cols, int diag1, int diag2) {
    if (row == N) { count++; return; }
    // 可用位 = 所有位(低N位) & ~(被佔用位)
    int available = ((1 << N) - 1) & ~(cols | diag1 | diag2);
    while (available) {
        int col_bit = available & -available; // 取最低可用位
        available ^= col_bit;                 // 清除該位
        backtrack_bit(row + 1, 
                      cols | col_bit, 
                      (diag1 | col_bit) << 1, // 下一行主對角線左移
                      (diag2 | col_bit) >> 1); // 下一行副對角線右移
    }
}

效果：N=14 從秒級降至毫秒級，是競程/面試必備技巧。

五、回溯算法通用設計模式總結

步驟	關鍵動作	八皇后對應
1. 定義狀態	最小化表示問題局面	pos[row]=col 一維數組
2. 確定選擇列表	當前狀態下的所有可行動作	當前行所有列 (0~7)
3. 實現合法性剪枝	盡早過濾無效選擇	is_valid() / 位掩碼
4. 遞歸/迭代搜索	做選擇 → 遞歸 → 撤銷選擇	backtrack(row+1)
5. 識別終止條件	找到解 / 無解 / 搜索空間耗盡	row == N
6. 結果收集/輸出	記錄路徑或計數	print_board() / count++