八皇后問題：經典回溯算法的 C 語言實現與解析

編輯：關於C語言

八皇后問題：經典回溯算法的 C 語言實現與解析

八皇后問題是計算機科學中極具代表性的回溯算法經典案例。問題源於國際象棋：如何在 8×8 的棋盤上放置八個皇后，使任意兩個皇后都不在同一行、同一列或同一斜線上？這意味著每個皇后佔據獨立的行、列與對角線。

問題建模與核心思路

棋盤可抽象為二維數組 chess[8][8]，值為 0 表示空位，1 表示被攻擊區域，2 表示已放置皇后。核心邏輯包含三部分：

標記攻擊範圍：setLimitsArea() 在放置皇后後，將其所在行、列、主對角線、副對角線標記為 1。
窮舉搜索：eightQueensProblem() 使用八層巢狀迴圈，對應八行皇后的列位置（0~7），逐行嘗試放置。
剪枝判斷：每放置一個皇后，檢查下一行目標位置是否為 0（未被攻擊），若否則跳過後續迴圈，大幅減少無效搜索。

關鍵代碼解析

void setLimitsArea(int row, int col) {
    // 標記同行、同列
    for (int j = 0; j < 8; j++) if (col != j) chess[row][j] = 1;
    for (int i = 0; i < 8; i++) if (row != i) chess[i][col] = 1;
    // 標記主對角線 (左上、右下)
    for (int i = 1; row - i >= 0 && col - i >= 0; i++) chess[row - i][col - i] = 1;
    for (int i = row + 1, j = col + 1; i < 8 && j < 8; i++, j++) chess[i][j] = 1;
    // 標記副對角線 (右上、左下)
    for (int i = 1; row - i >= 0 && col + i < 8; i++) chess[row - i][col + i] = 1;
    for (int i = row + 1, j = col - 1; i < 8 && j >= 0; i++, j--) chess[i][j] = 1;
}

主函數 eightQueensProblem() 雖使用八層迴圈而非遞歸回溯，但邏輯清晰：每行固定一個皇后，逐列嘗試，通過 setLimitsArea 動態維護約束，最終輸出所有 92 個合法解。顯示函數 display() 將 2 輸出為笑臉符號（ASCII 1），1 輸出為線條（ASCII 45），直觀呈現棋盤佈局。

算法優缺點與改進方向

此迭代寫法易於理解，但擴展性差（N 皇后需修改迴圈層數）。理想做法是遞歸回溯：

void dfs(int row) {
    if (row == 8) { output_solution(); return; }
    for (int col = 0; col < 8; col++) {
        if (is_safe(row, col)) {
            place_queen(row, col);
            dfs(row + 1);
            remove_queen(row, col); // 回溯恢復狀態
        }
    }
}

遞歸版本代碼簡潔、通用性強，時間複雜度同為 O(N!)，但常數因子更小，且易於結合位運算優化（用整數位掩碼表示列、主對角線、副對角線佔用狀態），可進一步提升效率。