分支限界算法求解八皇后问题java

八皇后问题是指在 8x8 的棋盘上放置 8 个皇后，使得每个皇后都无法攻击到其他皇后（即不在同一行、同一列、同一对角线上）。分支限界算法是一种常用于解决搜索问题的算法，可以用来解决八皇后问题。

以下是使用 Java 实现八皇后问题的分支限界算法的代码：

public class EightQueens {
    private static int[] solution = new int[8]; // 存储每行皇后的位置

    public static void main(String[] args) {
        solve(0); // 从第一行开始搜索
    }

    private static void solve(int row) {
        if (row == 8) { // 找到一组解
            printSolution();
            return;
        }

        for (int col = 0; col < 8; col++) {
            if (isValid(row, col)) { // 判断当前位置是否合法
                solution[row] = col;
                solve(row + 1); // 递归搜索下一行
            }
        }
    }

    private static boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            int diff = Math.abs(solution[i] - col);
            if (diff == 0 || diff == row - i) { // 判断是否在同一列或同一对角线上
                return false;
            }
        }
        return true;
    }

    private static void printSolution() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (solution[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}

在 `solve` 方法中，每次搜索一行时循环遍历该行的所有列，判断当前位置是否合法。如果合法，将该位置存储到 `solution` 数组中，并递归搜索下一行。如果搜索到最后一行，说明找到了一组解，调用 `printSolution` 方法打印出解。

在 `isValid` 方法中，判断当前位置是否在同一列或同一对角线上。如果在同一列，返回 false；如果在同一对角线上，差的绝对值等于行数之差，则返回 false。

在 `printSolution` 方法中，打印出每个皇后的位置，用 "Q" 表示皇后，"." 表示空格。

运行该程序，可以得到八皇后问题的所有解。