Java 遞歸實現八皇后問題：常見錯誤與修正方案

問題背景

八皇后問題是經典的回溯算法練習，要求在 8×8 棋盤上放置 8 個皇后，使其互不攻擊（同行、同列、同對角線均不能有兩個皇后）。許多初學者嘗試用 Java 遞歸實現，但常因邏輯錯誤導致程序無法正常運行，甚至陷入死循環或棧溢出。

典型錯誤代碼分析

以下代碼展示了一種常見的錯誤寫法：

public class Test {
    public static void main(String[] args) {
        Empress a = new Empress();
        a.find(0, 0);
        System.out.println(a.map);
    }
}

class Empress {
    public int[][] arry = new int[8][8];
    public int map = 0;

    public boolean rule(int[][] arry, int k, int j) {
        // 判斷節點是否合適
        for (int i = 0; i < 8; i++) {
            // 行列衝突
            if (arry[k][i] == 1) return false;
            else if (arry[i][j] == 1) return false;
        }
        for (int i = k - 1, m = j - 1; i >= 0 && m >= 0; i--, m--) {
            // 左對角線
            if (arry[i][m] == 1) return false;
        }
        for (int i = k - 1, m = j + 1; i >= 0 && m <= 7; i--, m++) {
            // 右對角線
            if (arry[i][m] == 1) return false;
        }
        return true;
    }

    public void find(int i, int m) {
        // 尋找皇后節點
        if (i > 7) {
            // 皇后解
            map++;
        } else {
            for (int j = i + 1; j < 8; j++) {
                // 刷新當前節點下的數組
                for (int k = 0; k < 8; k++) {
                    arry[j][k] = 0;
                }
            }
            for (; i < 8; i++) {
                // 深度優先搜索
                for (; m < 8; m++) {
                    if (rule(arry, i, m)) {
                        arry[i][m] = 1;
                        find(i + 1, 0);
                    }
                }
            }
        }
    }
}

主要問題

1. 遞歸邏輯混亂：`find` 方法中混合了迴圈與遞歸，導致狀態重置不當，且缺少回溯步驟（撤銷放置的皇后）。
2. 數組刷新方式錯誤：嘗試在遞歸前清空後續行，但這破壞了回溯的狀態保持。
3. 參數傳遞不清晰：`i` 和 `m` 的語義重疊，導致搜索路徑錯誤。

正確實現思路

標準回溯算法應遵循「放置 → 遞歸 → 撤銷」模式：

• 按行遞歸，每行嘗試每一列。
• 通過 `rule` 檢查該位置是否合法。
• 合法則放置皇后（`arry[row][col] = 1`），遞歸處理下一行。
• 遞歸返回後，必須撤銷放置（`arry[row][col] = 0`），以便嘗試同行其他列。
• 當 `row == 8` 時，找到一組解，計數器加一。

參考修正版本

可參考經典實現：CSDN 八皇后問題正確代碼。只需將打印語句末尾改為 `"\n"` 即可正確換行輸出所有解。

總結

遞歸回溯的關鍵在於狀態的正確保存與恢復。初學者應先在紙上推演小規模棋盤（如 4×4），理解回溯流程，再編寫代碼，避免將迴圈與遞歸混淆。