51. N皇后#

class Solution {
    // 主函数：返回 n 皇后的所有棋盘解法
    public List<List<String>> solveNQueens(int n) {
        // result：保存最终所有可行棋盘
        List<List<String>> result = new ArrayList<>();

        // queens[row] = col：记录第 row 行皇后放在第 col 列
        int[] queens = new int[n];

        // cols[col]：第 col 列是否已有皇后
        boolean[] cols = new boolean[n];
        // diag1[d1]：主对角线（row + col）是否已有皇后
        boolean[] diag1 = new boolean[2*n-1];
        // diag2[d2]：副对角线（row - col + n - 1）是否已有皇后
        boolean[] diag2 = new boolean[2*n-1];

        // 从第 0 行开始回溯放置皇后
        backtrack(n, 0, queens, cols, diag1, diag2, result);
        // 返回所有解
        return result;
    }

    // 回溯函数：尝试在 row 行放置皇后
    private void backtrack(int n, int row, int[] queens, boolean[] cols, 
                          boolean[] diag1, boolean[] diag2, List<List<String>> result) {
        // 终止条件：row == n，说明前 n 行都已成功放置皇后
        if (row == n) {
            // 根据 queens 生成棋盘字符串并加入结果
            result.add(generateBoard(queens, n));
            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]) {
                // 做选择：在 (row, col) 放置皇后
                queens[row] = col;
                cols[col] = true;
                diag1[d1] = true;
                diag2[d2] = true;

                // 递归处理下一行
                backtrack(n, row + 1, queens, cols, diag1, diag2, result);

                // 撤销选择（回溯）：恢复占用状态，尝试当前行下一列
                cols[col] = false;
                diag1[d1] = false;
                diag2[d2] = false;
            }
        }
    }

    // 根据 queens 数组生成当前解对应的棋盘字符串列表
    private List<String> generateBoard(int[] queens, int n) {
        // board：保存每一行的字符串表示
        List<String> board = new ArrayList<>();
        // 逐行构造棋盘
        for (int i = 0; i < n; i++) {
            // 先把该行全部初始化为 '.'（空位）
            char[] row = new char[n];
            Arrays.fill(row, '.');

            // 在该行皇后所在列标记为 'Q'
            row[queens[i]] = 'Q';

            // 将字符数组转为字符串加入棋盘
            board.add(new String(row));
        }
        // 返回构造好的棋盘
        return board;
    }
}