您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

八皇后問題：回溯法演算法詳解與 C 語言完整實作

編輯：關於C語言

問題描述

在 8×8 棋盤上放置 8 枚皇后，使任意兩枚皇后不在同一行、同一列、同一對角線（主/副對角線）上。求所有可行解。

回溯法核心思想

按行遞歸：第 row 行嘗試在各列放置皇后。
合法性檢查：新位置不與前 row-1 行的皇后衝突（同列、同主對角線、同副對角線）。
若某行無合法列 → 回溯至上一行換列繼續。
遞歸至第 9 行（row == 9） → 找到一解，輸出棋盤。

衝突檢查數學條件

假設前一皇后位於 (r, c)，新位置 (row, col)（1-based）：

同列：c == col
主對角線（左上→右下）：r - c == row - col ⇔ r - row == c - col
副對角線（右上→左下）：r + c == row + col ⇔ r - row == col - c

代碼中用陣列 m[8][8] 記錄棋盤，check(row, col) 逐行掃描前 row-1 行驗證上述條件。

完整 C 代碼（註釋版）

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int board[8][8] = {0};
int solutions = 0;

/* 檢查 (row, col) 是否可放置皇后（1-based 行列） */
bool check(int row, int col) {
    if (row == 1) return true;  // 第一行無約束
    int r, c;
    /* 同列 */
    for (r = 0; r < row-1; ++r)
        if (board[r][col-1]) return false;
    /* 主對角線：左上方向 */
    for (r = row-2, c = col-2; r >= 0 && c >= 0; --r, --c)
        if (board[r][c]) return false;
    /* 副對角線：右上方向 */
    for (r = row-2, c = col; r >= 0 && c < 8; --r, ++c)
        if (board[r][c]) return false;
    return true;
}

/* 輸出當前解 */
void output() {
    printf("Solution %d:\n", ++solutions);
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) printf("%d ", board[i][j]);
        putchar('\n');
    }
    putchar('\n');
}

/* 遞歸回溯：處理第 row 行（1-based） */
void solve(int row) {
    for (int col = 0; col < 8; ++col) {
        board[row-1][col] = 1;           // 嘗試放置
        if (check(row, col+1)) {
            if (row == 8) output();      // 最後一行 → 找到解
            else solve(row + 1);         // 否則遞歸下一行
        }
        board[row-1][col] = 0;           // 回溯：移除嘗試
    }
}

int main() {
    solve(1);
    printf("Total solutions: %d\n", solutions);  // 應為 92
    return 0;
}

優化方向（延伸閱讀）

位元遮罩：用三個整數 cols, diag1, diag2 以位元表示被佔用的列/對角線，O(1) 判斷合法性，極大加速（可在微秒級解出 92 解）。
對稱性剪枝：利用棋盤對稱性，僅搜尋前半列，解數乘 2（扣除中心對稱解）。
迭代深ening / 改良式回溯：將遞歸改寫為迭代，避免棧溢出（N 較大時）。