回溯法求n皇后问题java

下面是一个基于回溯法的 Java 代码实现，用于解决 n 皇后问题：

public class NQueens {
    private int[] queens;  // 存放皇后所在列的位置
    private int n;  // 皇后个数
    private int count;  // 解法数

    public int solveNQueens(int n) {
        this.n = n;
        queens = new int[n];
        count = 0;
        backtrack(0);
        return count;
    }

    private void backtrack(int row) {
        if (row == n) {  // 找到一组解
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(row, col)) {  // 判断该位置是否可以放置皇后
                queens[row] = col;
                backtrack(row + 1);
            }
        }
    }

    private boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (queens[i] == col || Math.abs(row - i) == Math.abs(col - queens[i])) {
                return false;  // 同一列或同一对角线已有皇后
            }
        }
        return true;
    }
}

在这个实现中，`queens` 数组存放每行皇后所在的列位置，`n` 表示皇后个数，`count` 初始为 0，用于统计解法数。`solveNQueens` 方法返回解法数，内部调用 `backtrack` 方法进行回溯搜索。`isValid` 方法用于判断该位置是否可以放置皇后，即该位置所在列、左上对角线、右上对角线是否已经有皇后。

回溯法是一种常用的解决搜索问题的算法，其思路是通过枚举所有可能的解，找到符合条件的解。在 n 皇后问题中，我们从第一行开始，枚举该行的所有位置，判断该位置是否可行，如果可行则继续递归搜索下一行，如果不可行则回溯到上一行。这样，当找到一组解时，我们就可以记录下来并开始寻找下一组解。