n皇后问题的回溯算法java

n皇后问题是经典的计算机科学问题，涉及在一个n×n的棋盘上放置n个皇后，使得任意两个皇后都不在同一行、同一列，以及同一对角线上。回溯算法是一种常见的解决此问题的策略，它通过递归尝试所有可能的位置，当发现无法放置新的皇后时，就“回溯”到之前的决策点，改变之前的选择。

在Java中，可以按照以下步骤编写n皇后问题的回溯算法：

1. 定义一个二维数组`board`表示棋盘，其中`board[i][j] = 0`表示位置(i,j)为空，`board[i][j] = 1`表示有皇后。
2. 创建一个递归函数`solveNQueens(int n, int row)`，从第一行开始遍历，对于每一行，尝试将皇后放在当前行的所有列中。
3. 检查当前位置是否导致冲突（即同一行、同一列或对角线上有其他皇后）。如果冲突，则回溯到前一列继续尝试下一个位置。
4. 如果没有冲突，将皇后放置在该位置，并递归地检查下一行。如果能成功放置n个皇后，说明找到一个解，记录并返回。
5. 当row等于n时，说明已经处理完所有行，结束递归。

以下是简化版的Java代码示例：

public class NQueens {
    private static final int BOARD_SIZE = 8; // 可以根据需要调整大小

    public static void main(String[] args) {
        boolean[][] board = new boolean[BOARD_SIZE][BOARD_SIZE];
        solveNQueens(board, 0);
        printBoard(board);
    }

    public static void solveNQueens(boolean[][] board, int row) {
        if (row == BOARD_SIZE) { // 到达最后一行，找到一个解
            for (int[] col : board) {
                System.out.print(col.join(" "));
            }
            System.out.println();
            return;
        }

        for (int col = 0; col < BOARD_SIZE; col++) {
            if (isValid(board, row, col)) { // 检查当前位置是否合法
                board[row][col] = true;
                solveNQueens(board, row + 1); // 递归前进到下一行
                board[row][col] = false; // 回溯：移除已放置的皇后
            }
        }
    }

    private static boolean isValid(boolean[][] board, 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(boolean[][] board) {
        for (int[] row : board) {
            for (boolean cell : row) {
                if (cell) System.out.print('Q');
                else       System.out.print('.');
            }
            System.out.println();
        }
    }
}