八皇后问题

八皇后问题

八皇后问题是经典的回溯算法应用案例，由国际象棋棋手马克斯・贝瑟尔于 1848 年提出。问题要求在 8×8 的国际象棋棋盘上放置 8 个皇后，使得任意两个皇后不能处于同一行、同一列或同一斜线上，最终找出所有可能的摆放方案。

一、问题核心约束

放置皇后时需满足以下条件：

1. 不同行：每一行只能放置 1 个皇后（可通过按行放置天然满足）。
2. 不同列：任意两个皇后不能在同一列。
3. 不同斜线：任意两个皇后不能在同一对角线（包括主对角线和副对角线）。

若用坐标 (row, col) 表示皇后位置，则对于两个皇后 (r1, c1) 和 (r2, c2)，需满足：

• $ c1 \neq c2 $（不同列）
• $(|r1 - r2| \neq |c1 - c2|)$（不同斜线，即行差不等于列差）

二、解决方案：回溯算法

回溯算法是解决八皇后问题的最优方法，其核心思想是逐行尝试放置皇后，若当前位置不满足约束则回退到上一行，尝试下一列，直到找到所有合法方案。

算法步骤：

1. 初始化：创建一个数组 queens 记录每一行皇后的列位置（索引为行号，值为列号）。

2. 递归放置：从第 0 行开始，逐行尝试在每一列放置皇后：

   • 检查当前列是否与已放置的皇后冲突（列冲突或斜线冲突）。

• 若不冲突，放置皇后并递归处理下一行。

  • 若冲突，尝试下一列。

1. 终止条件：当所有 8 行都放置好皇后时，记录当前方案。

2. 回溯：若当前行所有列都尝试完毕仍无法放置，回退到上一行，调整上一行皇后的位置后继续尝试。

三、代码实现

import java.util.ArrayList;
import java.util.List;

public class EightQueens {
    // 存储所有合法方案
    private List<List<String>> solutions = new ArrayList<>();
    // 皇后数量（八皇后问题固定为8）
    private int n = 8;

    public List<List<String>> solveNQueens() {
        // queens[row] = col：记录第row行皇后的列位置
        int[] queens = new int[n];
        // 初始化所有位置为-1（未放置）
        for (int i = 0; i < n; i++) {
            queens[i] = -1;
        }
        // 从第0行开始递归
        backtrack(queens, 0);
        return solutions;
    }

    // 回溯函数：在row行放置皇后
    private void backtrack(int[] queens, int row) {
        // 所有行都放置完毕，记录方案
        if (row == n) {
            solutions.add(generateBoard(queens));
            return;
        }

        // 尝试当前行的每一列
        for (int col = 0; col < n; col++) {
            // 检查当前位置是否冲突
            if (isValid(queens, row, col)) {
                // 放置皇后
                queens[row] = col;
                // 递归处理下一行
                backtrack(queens, row + 1);
                // 回溯：移除当前行的皇后，尝试下一列
                queens[row] = -1;
            }
        }
    }

    // 检查(row, col)位置是否与已放置的皇后冲突
    private boolean isValid(int[] queens, int row, int col) {
        for (int r = 0; r < row; r++) {
            int c = queens[r];
            // 列冲突：同一列已有皇后
            if (c == col) {
                return false;
            }
            // 斜线冲突：行差等于列差（同一对角线）
            if (Math.abs(row - r) == Math.abs(col - c)) {
                return false;
            }
        }
        return true;
    }

    // 将皇后位置转换为可视化棋盘
    private List<String> generateBoard(int[] queens) {
        List<String> board = new ArrayList<>();
        for (int row = 0; row < n; row++) {
            char[] line = new char[n];
            // 初始化当前行为'.'（无皇后）
            for (int i = 0; i < n; i++) {
                line[i] = '.';
            }
            // 在皇后位置标记'Q'
            line[queens[row]] = 'Q';
            board.add(new String(line));
        }
        return board;
    }

    public static void main(String[] args) {
        EightQueens solver = new EightQueens();
        List<List<String>> solutions = solver.solveNQueens();
        // 输出所有方案（八皇后问题共有92种解法）
        System.out.println("八皇后问题共有 " + solutions.size() + " 种解法：");
        for (int i = 0; i < solutions.size(); i++) {
            System.out.println("解法 " + (i + 1) + "：");
            for (String row : solutions.get(i)) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}

四、算法分析

• 时间复杂度：(O(n!))，其中 (n=8)。每一行最多有 n 种选择，第二行最多 (n-1) 种（排除当前列和斜线），以此类推，总方案数为 (n!) 级别。
• 空间复杂度：(O(n))，主要用于存储皇后位置的数组 queens 和递归调用栈（深度为 n）。
• 解法数量：八皇后问题共有 92 种 不同的合法摆放方案（不考虑旋转和镜像对称）。

五、扩展与变种

1. N 皇后问题：将 8×8 棋盘扩展为 (N×N) 棋盘，放置 N 个皇后，解法思路相同，只需将代码中的 (n=8) 改为自定义参数 N。
2. 优化技巧：
   • 使用哈希集记录已占用的列、主对角线（(row - col)）和副对角线（(row + col)），加速冲突检查。
   • 位运算优化：利用二进制位表示列和对角线占用状态，减少空间占用。
3. 应用场景：回溯算法是组合优化问题的经典解法，除八皇后外，还可用于数独求解、全排列生成、子集选择等问题。