回溯法n皇后问题Java

回溯法是一种用于解决约束搜索问题的算法，特别适用于像八皇后问题这样的组合优化问题。八皇后问题是一个经典的数学谜题，目标是在一个8x8的棋盘上放置8个皇后，使得任意两个皇后都不在同一行、同一列，以及对角线上。

在Java中，我们可以使用递归的方式实现回溯法来解决这个问题。以下是基本步骤：

1. 初始化数组：创建一个二维布尔数组表示棋盘，`boolean chessboard[8][8]`，初始值全部设为`false`，代表所有位置都是空的。

2. 选择当前位置：从第一行开始循环，尝试将皇后放在每一格。

3. 验证可行性：检查当前位置及其上下左右四个方向是否已经有皇后。

4. 如果可以放，则继续处理下一行；否则，回溯到上一行并尝试下一个位置。

5. 当所有皇后都放置完毕，如果找到了一个解决方案，就打印出来；如果没有找到，返回上一步。

6. 递归结束条件：当处理完所有行时，回溯至起始位置。

下面是一个简单的Java代码示例：

public class NQueens {
    private static final int N = 8;
    boolean chessboard[N][N];

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

    public static void solve(int row) {
        if (row == N) { // 所有皇后放置完成
            printSolution();
            return;
        }
        for (int col = 0; col < N; col++) {
            if (isValid(row, col)) {
                chessboard[row][col] = true;
                solve(row + 1); // 递归处理下一行
                chessboard[row][col] = false; // 回溯，移除当前皇后
            }
        }
    }

    private static boolean isValid(int row, int col) {
        // 检查列、同行、左对角线和右对角线是否有皇后
        return chessboard[row][col] == false &&
               allEmptyBelow(row, col) && allEmptyDiagonals(row, col);
    }

    private static boolean allEmptyBelow(int row, int col) {
        // 检查下方是否有皇后
        for (int i = row + 1; i < N; i++)
            if (chessboard[i][col])
                return false;
        return true;
    }

    private static boolean allEmptyDiagonals(int row, int col) {
        // 左对角线和右对角线
        int leftDiagonal = row - col;
        int rightDiagonal = row + col;

        while (leftDiagonal >= 0 && rightDiagonal < N)
            if (chessboard[leftDiagonal][rightDiagonal])
                return false;
            leftDiagonal--;
            rightDiagonal++;

        return true;
    }

    private static void printSolution() {
        // 打印解决方案
        for (int[] row : chessboard) {
            for (boolean cell : row) {
                System.out.print(cell ? "Q" : ".");
            }
            System.out.println();
        }
    }
}