回溯法解n皇后问题(Java 实现)

n 皇后问题是指在 n×n 的棋盘上放置 n 个皇后，使得皇后不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。这个问题可以使用回溯法进行求解。

Java 实现如下：

public class NQueens {

    private int n;
    private int[] queens;
    private boolean[] cols;
    private boolean[] diag1;
    private boolean[] diag2;
    private List<List<String>> res;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.queens = new int[n];
        this.cols = new boolean[n];
        this.diag1 = new boolean[2 * n - 1];
        this.diag2 = new boolean[2 * n - 1];
        this.res = new ArrayList<>();
        backtrack(0);
        return res;
    }

    private void backtrack(int row) {
        if (row == n) {
            res.add(generateBoard());
            return;
        }
        for (int col = 0; col < n; col++) {
            int d1 = row + col;
            int d2 = row - col + n - 1;
            if (!cols[col] && !diag1[d1] && !diag2[d2]) {
                queens[row] = col;
                cols[col] = true;
                diag1[d1] = true;
                diag2[d2] = true;
                backtrack(row + 1);
                cols[col] = false;
                diag1[d1] = false;
                diag2[d2] = false;
            }
        }
    }

    private List<String> generateBoard() {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}

在该代码中，我们使用了一个一维数组 queens 来表示每一行中皇后的位置，queens[i] 表示第 i 行中皇后所在的列数。同时，我们使用了三个一维数组 cols、diag1 和 diag2 分别表示每一列、每一条正斜线和每一条反斜线上是否有皇后。

在回溯函数 backtrack 中，我们首先判断当前行是否已经放置了皇后。如果已经放置完毕，则将当前的解加入到结果集中。否则，我们遍历当前行的每一列，尝试将皇后放置在该列上。如果该列、该正斜线和该反斜线上都没有皇后，则将皇后放置在该位置上，并将该位置标记为有皇后。接着，我们递归遍历下一行。如果当前的放置方案不行，则撤销该方案，将该位置标记为无皇后，并继续遍历下一列。

最后，我们使用函数 generateBoard 将每个解转化为棋盘的形式，并将其加入到结果集中。