【LeetCode 热题 100】51. N 皇后——回溯
Problem: 51. N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N!)
- 空间复杂度：O(N)
整体思路
这段代码旨在解决经典的组合搜索问题：N皇后问题 (N-Queens)。问题要求在一个 N×N 的棋盘上放置 N 个皇后，使得它们互相之间不能攻击。这意味着任意两个皇后都不能处于同一行、同一列或同一条对角线上。代码需要找出所有可能的解决方案。
该算法采用的核心方法是 回溯法（Backtracking），通过 深度优先搜索（DFS） 来系统地探索所有可能的皇后布局。为了高效地判断位置是否安全，算法使用了几个布尔数组来记录列和对角线的占用情况。
算法的整体思路可以分解为以下步骤：
-
逐行放置皇后：
- 算法将放置 N 个皇后的过程，看作是依次在第
0行、第1行、…、第n-1行分别放置一个皇后。 - 它定义了一个
dfs(r, ...)函数，其核心任务是在第r行找到一个安全的位置来放置皇后。由于我们是逐行放置的，所以自然满足了“不同行”的约束。
- 算法将放置 N 个皇后的过程，看作是依次在第
-
高效的位置合法性判断：
- 为了快速判断在
(r, c)位置放皇后是否安全，算法需要检查该位置所在的列和两条对角线是否已被占用。它使用了三个布尔数组：boolean[] col: 大小为n。col[c] = true表示第c列已被占用。boolean[] diag1: 大小为2n-1。用于标记主对角线（从左上到右下）。同一条主对角线上的所有格子(r, c)，其r + c的值是恒定的。我们用r + c作为diag1的索引。boolean[] diag2: 大小为2n-1。用于标记副对角线（从右上到左下）。同一条副对角线上的所有格子(r, c)，其r - c的值是恒定的。为了避免负数索引，通常会加上一个偏移量n-1，所以用r - c + n - 1作为diag2的索引。
- 为了快速判断在
-
递归与回溯的核心逻辑：
dfs(r, ...)函数尝试在第r行的每一列c(从 0到 n-1) 放置皇后。- 检查合法性：对于每个
(r, c)，通过检查!col[c] && !diag1[r+c] && !diag2[r-c+n-1]来判断该位置是否安全。 - 选择 (Choose)：如果位置安全，就做出选择：
a. 将(r, c)的列和两条对角线标记为已占用。
b. 记录皇后位置：queens[r] = c，表示第r行的皇后放在了第c列。 - 探索 (Explore)：递归调用
dfs(r + 1, ...)，去解决下一行r+1的放置问题。 - 撤销选择 (Unchoose / Backtrack)：当
dfs(r + 1, ...)返回后，必须撤销刚才的选择。将(r, c)的列和两条对角线的标记恢复为false。这是回溯法的精髓，它使得在后续的循环中，可以尝试在第r行的其他列c放置皇后。
-
递归终止与方案构建：
- 当
r的值等于n时，意味着从第 0 行到第 n-1 行都成功地放置了一个皇后。 - 此时，一个完整的解决方案就找到了。
queens数组中存储了该方案的所有皇后位置。 - 代码会根据
queens数组来构建一个List<String>形式的棋盘表示，并将其加入到最终的结果列表ans中。
- 当
完整代码
class Solution {/*** 解决 N 皇后问题，返回所有不同的解决方案。* @param n 棋盘大小和皇后数量* @return 包含所有解决方案的列表，每个方案是一个棋盘的字符串表示*/public List<List<String>> solveNQueens(int n) {// ans: 最终结果列表，存储所有解决方案List<List<String>> ans = new ArrayList<>();// queens[r] = c 表示第 r 行的皇后放在了第 c 列int[] queens = new int[n];// col[c] = true 表示第 c 列被占用boolean[] col = new boolean[n];// diag1[r+c] = true 表示主对角线 r+c 被占用boolean[] diag1 = new boolean[2 * n - 1]; // 索引范围是 0 到 2n-2// diag2[r-c+n-1] = true 表示副对角线 r-c+n-1 被占用boolean[] diag2 = new boolean[2 * n - 1]; // 索引范围是 0 到 2n-2// 从第 0 行开始进行深度优先搜索dfs(0, queens, ans, col, diag1, diag2);return ans;}/*** 深度优先搜索（回溯）辅助函数。* @param r 当前准备放置皇后的行号* @param queens 记录每行皇后位置的数组* @param ans 结果列表* @param col 列占用标记数组* @param diag1 主对角线占用标记数组* @param diag2 副对角线占用标记数组*/private void dfs(int r, int[] queens, List<List<String>> ans, boolean[] col, boolean[] diag1, boolean[] diag2) {int n = col.length;// 递归终止条件：当 r == n 时，说明所有 n 行都已成功放置皇后if (r == n) {// 构建棋盘的字符串表示List<String> board = new ArrayList<>(n);for (int c : queens) {char[] row = new char[n];Arrays.fill(row, '.');row[c] = 'Q';board.add(new String(row));}// 将构建好的解决方案加入结果列表ans.add(board);return;}// 尝试在当前行 r 的每一列 c 放置皇后for (int c = 0; c < n; c++) {// 计算两条对角线的索引int d1_idx = r + c;int d2_idx = r - c + n - 1;// 检查当前位置 (r, c) 是否安全if (!col[c] && !diag1[d1_idx] && !diag2[d2_idx]) {// 选择 (Choose): 在 (r, c) 放置皇后col[c] = diag1[d1_idx] = diag2[d2_idx] = true;queens[r] = c;// 探索 (Explore): 递归地去处理下一行dfs(r + 1, queens, ans, col, diag1, diag2);// 撤销选择 (Unchoose / Backtrack): 恢复状态，将皇后从 (r, c) 移走col[c] = diag1[d1_idx] = diag2[d2_idx] = false;// queens[r] 的值会被下一轮循环覆盖，无需显式重置}}}
}
时空复杂度
时间复杂度：O(N!)
- 搜索空间：这是一个典型的全排列问题的变种。在第 0 行，我们有 N 个选择；在第 1 行，最多有 N-1 个选择（因为列不能重复），以此类推。这给出了一个
N * (N-1) * ... * 1 = N!的上界。 - 剪枝：由于对角线的约束，实际的搜索空间会比
N!小很多，但其增长趋势仍然是阶乘级别的。没有一个简单的封闭形式来精确描述N皇后问题的解的数量或搜索树的节点数，但O(N!)是一个被广泛接受的、描述其计算复杂度的上界。 - 方案构建：当找到一个解决方案时，需要花费 O(N^2) 的时间来构建棋盘的字符串表示。设
S(N)为解的数量，这部分的总时间是S(N) * O(N^2)。 - 综合分析：
- 搜索过程的时间复杂度远大于方案构建的总时间。
- 因此，整个算法的时间复杂度由搜索树的节点数决定，可以粗略地用 O(N!) 来表示。
空间复杂度：O(N)
- 主要存储开销：我们分析的是额外辅助空间，不包括存储最终结果的
ans列表。int[] queens: 大小为N。boolean[] col: 大小为N。boolean[] diag1: 大小为2N-1。boolean[] diag2: 大小为2N-1。- 递归调用栈：
dfs函数的最大递归深度为N。
- 综合分析：
- 所有辅助数组和递归栈的深度都与
N成线性关系。 - O(N) + O(N) + O(2N-1) + O(2N-1) + O(N) = O(N)。
- 因此，总的辅助空间复杂度为 O(N)。
- 所有辅助数组和递归栈的深度都与
参考灵神