N 皇後問題遞歸回溯算法完整實現：從 8 皇後到 N 皇後通解

N 皇後問題遞歸回溯算法完整實現

問題描述

在 N×N 棋盤上放置 N 個皇後，使任意兩個皇後不同行、不同列、不同斜線。經典 8 皇後是 N=8 特例。解的數量隨 N 增長呈指數級增長（N=8 有 92 解，去重對稱後 12 解）。

算法思路：回溯 + 剪枝

1. 按行遞歸，每行嘗試每一列放置皇後
2. 放置前檢查：該列、主對角線、副對角線是否已被佔用
3. 合法則標記佔用，遞歸下一行
4. 回溯時恢復標記
5. 所有行放置完成（row == N）記錄一個解

優化關鍵：O(1) 合法性判斷

使用三個布爾數組（或位掩碼）記錄衝突：

• cols[c]：列 c 是否有皇後
• diag1[r+c]：主對角線（行+列固定）
• diag2[r-c+N-1]：副對角線（行-列固定，偏移避免負索引）

完整 Java 實現（含去重輸出）

import java.util.*;

public class NQueens {
    private int n;
    private int count = 0;
    private boolean[] cols, diag1, diag2;
    private int[] queens; // queens[row] = col
    private Set uniqueSolutions = new HashSet<>();

    public int solve(int n) {
        this.n = n;
        cols = new boolean[n];
        diag1 = new boolean[2 * n - 1];
        diag2 = new boolean[2 * n - 1];
        queens = new int[n];
        backtrack(0);
        return count;
    }

    private void backtrack(int row) {
        if (row == n) {
            // 找到一個解
            count++;
            printSolution();
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(row, col)) {
                placeQueen(row, col);
                backtrack(row + 1);
                removeQueen(row, col);
            }
        }
    }

    private boolean isValid(int row, int col) {
        return !cols[col] && !diag1[row + col] && !diag2[row - col + n - 1];
    }

    private void placeQueen(int row, int col) {
        queens[row] = col;
        cols[col] = true;
        diag1[row + col] = true;
        diag2[row - col + n - 1] = true;
    }

    private void removeQueen(int row, int col) {
        cols[col] = false;
        diag1[row + col] = false;
        diag2[row - col + n - 1] = false;
    }

    private void printSolution() {
        StringBuilder sb = new StringBuilder();
        for (int r = 0; r < n; r++) {
            sb.append('(').append(r).append(',').append(queens[r]).append(')');
        }
        String key = sb.toString();
        if (uniqueSolutions.add(key)) { // 去重
            System.out.println("解 " + count + ": " + key);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("請輸入 N (N≥4): ");
        int n = sc.nextInt();
        NQueens solver = new NQueens();
        long start = System.currentTimeMillis();
        int total = solver.solve(n);
        System.out.printf("N=%d 總解數: %d, 耗時: %d ms%n", n, total, System.currentTimeMillis() - start);
    }
}

運行示例 (N=4)

請輸入 N (N≥4): 4
解 1: (0,1)(1,3)(2,0)(3,2)
解 2: (0,2)(1,0)(2,3)(3,1)
N=4 總解數: 2, 耗時: 5 ms

複雜度分析

• 時間：O(N!) 理論上界，實際因剪枝遠小於此（N=14 約 36 萬解，毫秒級）
• 空間：O(N) 遞歸棧 + O(N) 狀態數組

進階優化方向

1. 位運算加速：用 int 位掩碼代替布爾數組，利用 CPU 指令級並行（N≤32 時極快）
2. 對稱性剪枝：利用棋盤旋轉/鏡像對稱，只搜索一半首行位置，結果乘 2（中間列單獨處理）
3. 迭代深ening / 並行化：多線程分割首行搜索空間

數學結論

• N=1: 1 解；N=2,3: 無解
• N≥4: 必有解
• 解數列：1, 0, 0, 2, 10, 4, 40, 92, 352, 724... (OEIS A000170)