n皇后问题的回溯算法JAVA

n皇后问题是经典的回溯法应用实例，目标是在一个n×n的棋盘上放置n个皇后，保证任何两个皇后都不会在同一行、同一列或对角线上。以下是使用Java实现n皇后问题的简单回溯算法：

public class NQueens {
    private static final int N = 8; // 可以换成任意大小

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

    // 用于记录每一行是否放了皇后
    private static boolean[][] board;

    // 回溯函数，寻找所有解决方案
    private static void solveNQueens(int row) {
        if (row == N) { // 找到一个解，打印并结束递归
            printBoard();
            return;
        }
        
        for (int col = 0; col < N; col++) { // 检查当前列是否可以放置皇后
            if (isValid(row, col)) {
                board[row][col] = true; // 放置皇后
                solveNQueens(row + 1); // 递归尝试下一行
                board[row][col] = false; // 撤销放置，回溯
            }
        }
    }

    // 检查当前位置是否合法，即检查同一行、同一列和两条对角线是否有其他皇后
    private static boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] || // 同一行
                    board[row][i] || // 同一列
                    board[i][i+col] || // 左上到右下的对角线
                    board[i][i-col]) { // 左下到右上的对角线
                return false;
            }
        }
        return true;
    }

    // 打印已经找到的皇后布局
    private static void printBoard() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(board[i][j] ? "Q " : ".");
            }
            System.out.println();
        }
    }
}