N皇后问题 Java 代码：回溯法实现

public class NQueens {

private int[] queens; // 皇后位置
private boolean[] cols; // 列
private boolean[] diag1; // 主对角线
private boolean[] diag2; // 副对角线
private List<List<String>> res; // 存储结果

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

// 回溯求解
private void dfs(int row, int n) {
    if (row == n) {
        res.add(generateBoard(n));
        return;
    }
    for (int col = 0; col < n; col++) {
        if (cols[col] || diag1[row+col] || diag2[row-col+n-1]) {
            continue;
        }
        queens[row] = col;
        cols[col] = true;
        diag1[row+col] = true;
        diag2[row-col+n-1] = true;
        dfs(row+1, n);
        queens[row] = 0; // 回溯
        cols[col] = false;
        diag1[row+col] = false;
        diag2[row-col+n-1] = false;
    }
}

// 生成棋盘
private List<String> generateBoard(int n) {
    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;
}

}