解决思路：回溯 + 剪枝

N 皇后问题是经典的回溯算法应用场景，核心是在 n×n 的棋盘上放置 n 个皇后，使它们互不攻击（不在同一行、同一列、同一对角线）。下面用回溯 + 剪枝的思路来拆解这个问题。

一、问题分析

要让皇后互不攻击，需满足三个条件：

• 同一行：因为我们逐行放置皇后，所以每行只会有一个皇后，天然满足。
• 同一列：每列只能放一个皇后。
• 同一对角线：分为主对角线（行 - 列差值固定）和副对角线（行 + 列和固定），这两类对角线也只能各放一个皇后。

二、核心思路：回溯 + 剪枝

1. 回溯逻辑

• 逐行放置皇后（从第 0 行到第 n-1 行）。
• 对当前行的每一列，尝试放置皇后，若合法则递归处理下一行；若不合法则跳过（剪枝）。
• 递归完成后回溯：撤销当前列的选择，尝试下一列。

2. 剪枝策略（用三个布尔数组标记 “已占用”）

• invalidColumn[]：标记某一列是否已被皇后占用。
• invalidMainDiagonal[]：标记某条主对角是否已被占用。
• invalidAntiDiagonal[]：标记某条副对角线是否已被占用。

3. 结果构造

当递归到第 n 行（即curRow == n）时，说明找到了一种合法的放置方式。此时将列索引转换为棋盘字符串（Q表示皇后，.表示空位），存入结果集。

三、步骤总结

1. 初始化三个剪枝数组，分别标记列、主对角线、副对角线的占用状态。
2. 从第 0 行开始，逐行尝试在每一列放置皇后：
   • 若当前列或者对角线已被占用，跳过（剪枝）。
   • 若合法，标记占用状态，递归处理下一行。
   • 递归返回后，回溯（撤销占用标记，移除当前列选择）。
3. 当找到 n 个皇后的合法放置时，构造棋盘字符串并保存结果。

这种思路通过剪枝避免了大量无效尝试，确保算法效率，是解决 N 皇后问题的经典且高效的方法。

class Solution {
    public static List<List<String>> solveNQueens(int n) {
        // 若invalidColumn[x] == true, 下标为x的列不能放
        boolean[] invalidColumn = new boolean[n];
        // 若invalidMainDiagonal[x] == true, 则(横坐标-纵坐标+n == x)的位置不能放
        boolean[] invalidMainDiagonal = new boolean[2 * n + 1];
        // 若invalidAntiDiagonal[x] == true, 则(横坐标 + 纵坐标 == x)的位置不能放
        boolean[] invalidAntiDiagonal = new boolean[2 * n + 1];

        List<List<String>> result = new ArrayList<>();
        a(invalidColumn, invalidMainDiagonal, invalidAntiDiagonal, n, result, new ArrayList<>(), 0);

        return result;
    }

    // cur存的是从第0行到第n行的棋的纵坐标
    // curRow 是当前操作行数
    public static void a(boolean[] invalidColumn, boolean[] invalidMainDiagonal, boolean[] invalidAntiDiagonal, int n,List<List<String>> result, List<Integer> cur, int curRow) {
        if (curRow == n) {
            b(result, cur);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (invalidColumn[i] || invalidMainDiagonal[curRow - i + n] || invalidAntiDiagonal[curRow + i]) {
                continue;
            }
            cur.add(i);
            invalidColumn[i] = true;
            invalidMainDiagonal[curRow - i + n] = true;
            invalidAntiDiagonal[curRow + i] = true;
            a(invalidColumn, invalidMainDiagonal, invalidAntiDiagonal, n, result, cur, ++curRow);
            curRow--;
            cur.remove(cur.size() - 1);
            invalidColumn[i] = false;
            invalidMainDiagonal[curRow - i + n] = false;
            invalidAntiDiagonal[curRow + i] = false;
        }
    }

    //插入一次结果
    public static void b(List<List<String>> result, List<Integer> columnIndexs) {
        List<String> temp = new ArrayList<>();
        for (int index : columnIndexs) {
            StringBuilder s = new StringBuilder("");
            for (int i = 0; i < columnIndexs.size(); i++) {
                if (i == index) {
                    s.append("Q");
                    continue;
                }
                s.append(".");
            }
            temp.add(s.toString());
        }
        result.add(temp);
    }
}