java回溯法解决八皇后问题

八皇后问题是一个经典的回溯法问题，它的目标是在8x8的棋盘上放置8个皇后，使得每个皇后都不会互相攻击（即不在同一行、同一列或同一对角线上）。下面是Java代码实现：

public class EightQueens {
    private static final int N = 8;
    private static int[] queen = new int[N];

    public static void main(String[] args) {
        placeQueen(0);
    }

    private static void placeQueen(int row) {
        if (row == N) {
            printQueen();
            return;
        }
        for (int i = 0; i < N; i++) {
            queen[row] = i;
            if (check(row)) {
                placeQueen(row + 1);
            }
        }
    }

    private static boolean check(int row) {
        for (int i = 0; i < row; i++) {
            if (queen[i] == queen[row] || Math.abs(queen[i] - queen[row]) == row - i) {
                return false;
            }
        }
        return true;
    }

    private static void printQueen() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (queen[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}

程序中的 `queen` 数组表示每一行放置的皇后所在的列数。`placeQueen` 方法用于递归地放置皇后，`check` 方法用于检查当前状态是否合法，`printQueen` 方法用于输出结果。程序的思路是从第0行开始递归地放置皇后，直到放置到第8行为止，然后输出结果。在递归过程中，如果当前状态合法，则继续递归放置下一行皇后，否则回溯到上一行重新尝试放置。