N 皇後問題 Java 實現：回溯算法核心邏輯、棋盤狀態管理與解空間可視化完整教程

問題定義

在 N×N 棋盤上放置 N 個皇後，任意兩個皇後不同行、不同列、不同對角線。八皇後共有 92 種解。

核心數據結構

class Queen { int position; } // 該行皇后所在列
class Board {
    int size;
    int[][] layout; // 0=可放，>0=被攻擊次數
}

layout[i][j] 記錄第 i 行第 j 列被攻擊的次數，支持回溯時精確撤銷。

回溯算法遞歸流程

1. 逐行嘗試放置皇后（行號 = 遞歸深度）；
2. 遍歷該行所有列，layout[row][col] == 0 表示安全；
3. 放置後，更新下方行的同列、左下對角、右下對角攻擊計數 ++；
4. 遞歸處理下一行；
5. 回溯時，恢復攻擊計數 --，嘗試下一列。

完整 Java 實現

import java.util.*;

public class NQueens {
    private int solutions = 0;
    private final int n;
    private final Board board;
    private final List<Queen> queens;

    public NQueens(int n) {
        this.n = n;
        this.board = new Board(n);
        this.queens = new ArrayList<>(n);
        for (int i = 0; i < n; i++) queens.add(new Queen());
    }

    public void solve() {
        System.out.println("開始求解 " + n + " 皇後...");
        placeQueen(0);
        System.out.println("總共找到 " + solutions + " 個解");
    }

    private void placeQueen(int row) {
        for (int col = 0; col < n; col++) {
            if (board.layout[row][col] == 0) {
                queens.get(row).position = col;
                markAttack(row, col, +1); // 標記攻擊區域

                if (row == n - 1) {
                    printSolution(++solutions);
                } else {
                    placeQueen(row + 1);
                }
                markAttack(row, col, -1); // 回溯撤銷
            }
        }
    }

    private void markAttack(int row, int col, int delta) {
        for (int i = row + 1; i < n; i++) {
            board.layout[i][col] += delta;                    // 同列
            if (col - (i - row) >= 0) board.layout[i][col - (i - row)] += delta; // 左下
            if (col + (i - row) < n)  board.layout[i][col + (i - row)] += delta; // 右下
        }
    }

    private void printSolution(int idx) {
        System.out.println("第 " + idx + " 解：");
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                System.out.print(queens.get(r).position == c ? " ♛ " : " · ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        new NQueens(8).solve(); // 可改參數如 4、10
    }
}

class Queen { int position; }
class Board {
    final int size;
    final int[][] layout;
    Board(int n) { size = n; layout = new int[n][n]; }
}

關鍵優化點

• 攻擊計數器：替代布爾標記，支持多皇后攻擊同一格時正確回溯；
• 位運算優化（進階）：用 int 位掩碼表示列、主對角、副對角佔用，O(1) 判斷安全，極大提速；
• 剪枝：對稱性利用（僅枚舉前半列）、啟發式排序（優先嘗試中央列）。

複雜度分析

• 時間：O(N!) 最壞，實際遠小得益於剪枝；
• 空間：O(N²) 棋盤 + O(N) 遞歸棧；
• 八皇后 ~10ms 完成，13 皇后 ~1s，14 皇后 ~10s（普通回溯）。

擴展應用

• 約束滿足問題（CSP）通用框架：數獨、圖著色、課程表調度；
• 並行化：將首行列分配到多線程，無鎖獨立搜索；
• 可視化：Swing/JavaFX 實時繪製搜索過程，教學演示極佳。