八皇后問題：回溯法遞迴解法完整解析與 Java 實作

問題定義

在 8×8 國際象棋棋盤上放置 8 個皇后，使任兩皇后均不在同一列、同一行、同一斜線上。求所有合法擺放方案總數（已知為 92 種）。

回溯法核心思想

逐行嘗試放置皇后：

1. 第 1 行，嘗試第 1~8 列
2. 放置前檢查：該列、兩條斜線是否已有皇后
3. 合法 → 標記佔用，遞迴處理下一行
4. 第 9 行（i > 8） → 找到一組解，計數器 +1
5. 不合法或遞迴返回 → 撤銷標記（回溯），試同行下一列

關鍵資料結構設計

• column[9]：索引 1~8 對應 8 列，1=被佔用
• rsl[17]：右上→左下斜線（行+列），範圍 2~16
• lsl[17]：左上→右下斜線（行-列+8），範圍 1~15
• queen[9]：記錄每行皇后所在列（可選，用於輸出具體解）

完整 Java 實作

public class EightQueens {
    private int[] column = new int[9];
    private int[] rsl = new int[17];   // row + col
    private int[] lsl = new int[17];   // row - col + 8
    private static int solutionCount = 0;

    public void backtrack(int row) {
        if (row > 8) {
            solutionCount++;
            // 可在此印出 queen[1..8] 具體座標
            return;
        }
        for (int col = 1; col <= 8; col++) {
            if (column[col] == 0 && rsl[row + col] == 0 && lsl[row - col + 8] == 0) {
                // 放置皇后
                column[col] = rsl[row + col] = lsl[row - col + 8] = 1;
                // queen[row] = col; // 記錄解
                backtrack(row + 1);
                // 回溯：撤銷佔用
                column[col] = rsl[row + col] = lsl[row - col + 8] = 0;
            }
        }
    }

    public static void main(String[] args) {
        EightQueens eq = new EightQueens();
        eq.backtrack(1);
        System.out.println("總解數：" + solutionCount); // 輸出 92
    }
}

複雜度分析

• 時間複雜度：O(N!) 理論上限，但剪枝極大縮減搜尋空間（8 皇后僅檢查約 1.5 萬節點）
• 空間複雜度：O(N) 遞迴深度 + O(N) 狀態陣列

同構問題舉一反三

• N 皇后問題（通用化）
• 迷宮尋路（回溯 + 方向陣列）
• 數獨求解器
• 圖著色問題
• 全排列/組合生成

優化方向

1. 位元運算優化：用 int 位元掩碼取代陣列，單指令完成衝突檢測（LeetCode 51/52 標準解法）
2. 對稱性剪枝：利用棋盤對稱，僅搜尋前半列，解數 ×2（中央列特判）
3. 迭代深ening / 舞蹈鏈（Algorithm X）解決大規模 N

教學總結

八皇后是回溯法的經典入門題。關鍵在於：狀態表示簡潔、衝突檢測 O(1)、遞入遞出對稱修改狀態。掌握此模板，即可應對所有「在約束條件下尋找所有可行解」的組合優化問題。