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

八皇后問題與回溯算法：C語言實現詳解

編輯：關於C

八皇后問題是經典的算法課題，要求在 8×8 的棋盤上放置 8 枚皇后，使任兩枚皇后不在同一行、同一列或同一對角線上。這是一個典型的約束滿足問題，最常用的解法是回溯算法。

問題描述

在 8×8 的國際象棋棋盤上放置 8 個皇后，使得任意兩個皇后都不能互相攻擊。也就是說：每行、每列、每條主對角線、每條副對角線上最多只能有一個皇后。下圖展示了一個可行解：

回溯算法思路

回溯算法的核心思想是「試探與撤銷」。我們從第一行開始，逐行嘗試在每一列放置皇后：

在當前行的每一列嘗試放置皇后
檢查該位置是否與已放置的皇后衝突（同列、同主對角線、同副對角線）
若無衝突，遞歸處理下一行
若所有列都試完仍無解，回溯到上一行，移動皇后位置繼續搜索
當成功放置第 8 行皇后時，找到一個可行解，輸出棋盤

關鍵函數解析

1. check 函數：位置合法性檢查

檢查在第 row 行、第 column 列放置皇后是否合法，需驗證三個方向：

縱向：檢查前 row-1 行的同一列是否有皇后
主對角線（左上→右下）：行列差固定，即 row - column 相等
副對角線（右上→左下）：行列和固定，即 row + column 相等

2. solve 函數：遞歸回溯主邏輯

void solve(int row) {
    for (int j = 0; j < 8; j++) {
        m[row-1][j] = 1;              // 嘗試放置
        if (check(row, j+1)) {        // 合法性檢查
            if (row == 8) output();   // 最後一行，找到解
            else solve(row + 1);      // 否則遞歸下一行
        }
        m[row-1][j] = 0;              // 回溯：移除皇后，試下一列
    }
}

3. output 函數：輸出解

將棋盤矩陣以 0/1 形式打印，1 表示有皇后。

完整 C 代碼

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

int m[8][8] = {0};
int num = 0;

bool check(int row, int column) {
    if (row == 1) return true;
    // 縱向檢查
    for (int i = 0; i <= row-2; i++)
        if (m[i][column-1] == 1) return false;
    // 主對角線檢查
    int i = row-2, j = i - (row - column);
    while (i >= 0 && j >= 0) {
        if (m[i][j] == 1) return false;
        i--; j--;
    }
    // 副對角線檢查
    i = row-2; j = row + column - i - 2;
    while (i >= 0 && j <= 7) {
        if (m[i][j] == 1) return false;
        i--; j++;
    }
    return true;
}

void output() {
    num++;
    printf("answer %d:\n", num);
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) printf("%d ", m[i][j]);
        printf("\n");
    }
}

void solve(int row) {
    for (int j = 0; j < 8; j++) {
        m[row-1][j] = 1;
        if (check(row, j+1)) {
            if (row == 8) output();
            else solve(row + 1);
        }
        m[row-1][j] = 0;
    }
}

int main() {
    solve(1);
    return 0;
}