Java 八皇后問題：隨機搜尋與八進制遍歷雙演算法完整實作

問題定義

8×8 棋盤放置 8 個皇后，任兩個不同行、不同列、不同對角線。用一維陣列 col[row] = column 表示。

有效性判斷核心邏輯

對任意 i < j：

• 不同列：col[i] != col[j]
• 不同對角線：|col[i] - col[j]| != j - i

演算法一：隨機打亂 + 驗證（求一解）

public void solveOne() {
    int[] col = new int[8];
    for (int i = 0; i < 8; i++) col[i] = i; // 初始各列唯一
    int attempts = 0;
    while (true) {
        attempts++;
        shuffle(col); // Fisher-Yates 洗牌
        if (isValid(col)) {
            System.out.println("嘗試 " + attempts + " 次找到解: " + Arrays.toString(col));
            break;
        }
    }
}

private void shuffle(int[] a) {
    Random r = new Random();
    for (int i = 0; i < a.length; i++) {
        int j = r.nextInt(a.length);
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

private boolean isValid(int[] col) {
    for (int i = 0; i < 8; i++)
        for (int j = i + 1; j < 8; j++)
            if (Math.abs(col[i] - col[j]) == j - i) return false;
    return true;
}

期望嘗試次數約 8! / 92 ≈ 4400，極快得到一解。

演算法二：八進制遍歷（求全解 92 組）

public void solveAll() {
    int start = 0_1234567; // 八進制字面值
    int end   = 0_7654321;
    int count = 0;
    for (int n = start; n <= end; n++) {
        String oct = Integer.toOctalString(n);
        if (oct.length() == 7) oct = "0" + oct; // 補齊前導 0
        if (isValidOct(oct)) {
            System.out.println(++count + ": " + oct);
        }
    }
    System.out.println("總解數: " + count); // 92
}

private boolean isValidOct(String oct) {
    for (int i = 0; i < 8; i++) {
        for (int j = i + 1; j < 8; j++) {
            if (oct.charAt(i) == oct.charAt(j)) return false; // 同列
            if (Math.abs(oct.charAt(i) - oct.charAt(j)) == j - i) return false; // 同對角線
        }
    }
    return true;
}

遍歷 8⁸ = 16,777,216 個八進制數，過濾重複列後驗證對角線，約 0.5 秒完成。

演算法對比

標準回溯法參考實作（推薦求全解）

List solutions = new ArrayList<>();
int[] col = new int[8];

void backtrack(int row) {
    if (row == 8) { solutions.add(col.clone()); return; }
    for (int c = 0; c < 8; c++) {
        col[row] = c;
        if (valid(row)) backtrack(row + 1);
    }
}
boolean valid(int row) {
    for (int i = 0; i < row; i++)
        if (col[i] == col[row] || Math.abs(col[i] - col[row]) == row - i) return false;
    return true;
}

延伸：N 皇后與位運算優化

• 用 int 位元表示列、主對角線、副對角線佔用，bits = cols | diag1 | diag2，極快
• N=14 以內毫秒級求全解