回溯算法解決八皇后問題（Java 實現）

回溯算法解決八皇后問題（Java 實現）

八皇后問題是回溯算法的經典案例：在 8×8 棋盤上擺放 8 個皇后，使任意兩個皇后不在同一行、同一列、同一斜線上。本文提供通用 N 皇后 Java 實現，邏輯清晰，易於擴展。

核心思路

1. 按行遞歸：第 n 個皇后放在第 n 行；
2. 遍歷該行所有列，嘗試放置；
3. 校驗當前列是否與前 n-1 個皇后衝突（同列、同斜線）；
4. 若合法，遞歸處理下一行；
5. 當 n == N 時找到一個解，記錄並回溯繼續搜尋。

完整代碼

public class NQueens {
    private final int N;
    private final int[] columns; // columns[i] = 第 i 行皇后所在列

    public NQueens(int n) {
        this.N = n;
        this.columns = new int[n];
    }

    public void solve() {
        backtrack(0);
    }

    private void backtrack(int row) {
        if (row == N) {
            printSolution();
            return;
        }
        for (int col = 0; col < N; col++) {
            columns[row] = col;
            if (isValid(row)) {
                backtrack(row + 1);
            }
        }
    }

    private boolean isValid(int row) {
        for (int i = 0; i < row; i++) {
            // 同列 或 同斜線（行差等於列差）
            if (columns[i] == columns[row] || Math.abs(row - i) == Math.abs(columns[row] - columns[i])) {
                return false;
            }
        }
        return true;
    }

    private void printSolution() {
        for (int col : columns) {
            System.out.print((col + 1) + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        new NQueens(8).solve(); // 8 皇后共有 92 個解
    }
}

關鍵點解析

• columns 一維數組隱含行信息，空間複雜度 O(N)；
• 斜線衝突判斷：|row1 - row2| == |col1 - col2|；
• 時間複雜度約 O(N!)，但剪枝極大減少搜索空間；
• 修改 N 即可解決任意 N 皇后問題。