C語言解決八皇后問題：回溯算法完整實現與輸出可視化

問題建模

在 8×8 棋盤放 8 個皇后，任意兩個不同行、不同列、不同對角線。
用一維數組 pos[8] 表示：pos[row] = col 第 row 行皇后放在 col 列。

回溯核心邏輯

bool is_safe(int row, int col, int *pos) {
    for (int r = 0; r < row; r++) {
        int c = pos[r];
        if (c == col) return false;                 // 同列
        if (r - c == row - col) return false;       // 主對角線 (row-col 恒定)
        if (r + c == row + col) return false;       // 副對角線 (row+col 恒定)
    }
    return true;
}

void solve(int row, int *pos, int *count) {
    if (row == 8) {                    // 找到一組解
        (*count)++;
        print_board(pos, *count);
        return;
    }
    for (int col = 0; col < 8; col++) {
        if (is_safe(row, col, pos)) {
            pos[row] = col;            // 放置
            solve(row + 1, pos, count); // 遞歸下一行
            // pos[row] = -1;           // 回溯（可選，下輪會覆蓋）
        }
    }
}

完整可視化程序

#include 
#include 

#define N 8

void print_board(int *pos, int sol_num) {
    printf("\n解 %2d:\n", sol_num);
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++)
            printf("%c ", (pos[r] == c) ? '♛' : '·');
        puts("");
    }
}

bool is_safe(int row, int col, int *pos) {
    for (int r = 0; r < row; r++) {
        int c = pos[r];
        if (c == col || r - c == row - col || r + c == row + col)
            return false;
    }
    return true;
}

void solve(int row, int *pos, int *count) {
    if (row == N) {
        print_board(pos, ++(*count));
        return;
    }
    for (int col = 0; col < N; col++) {
        if (is_safe(row, col, pos)) {
            pos[row] = col;
            solve(row + 1, pos, count);
        }
    }
}

int main() {
    int pos[N] = {0};
    int count = 0;
    solve(0, pos, &count);
    printf("\n總共 %d 個解\n", count); // 92
    return 0;
}

關鍵技術點

性能優化：位運算版（極快）

// 利用位掩碼表示列、主對角線、副對角線佔用
void solve_bit(int row, int cols, int diag1, int diag2, int *count) {
    if (row == N) { (*count)++; return; }
    // 可用位 = 所有列 & ~(佔用列 | 佔用主對角線 | 佔用副對角線)
    int available = ((1 << N) - 1) & ~(cols | diag1 | diag2);
    while (available) {
        int bit = available & -available; // 取最低位 1
        available -= bit;
        solve_bit(row + 1, cols | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1, count);
    }
}
// 主調用：solve_bit(0, 0, 0, 0, &count);

位運算版無分支預測失敗、無數組訪問、極適合 CPU 流水線，**比數組版快 10-50 倍**。

總結

• 八皇后是**回溯/遞歸/剪枝**教學經典。
• 一維數組 pos[row]=col + 對角線數學判斷 = 最清晰實現。
• 位運算版展示了**將集合運算映射到位掩碼**的系統級優化思維。
• 通用框架：DFS(狀態) { if(終止) 記錄; for(選擇) if(合法) { 標記; DFS(新狀態); 回溯; } }。