目录
题目
题目链接
思路
复杂度
代码
题目
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
题目链接
51. N 皇后 – 力扣（LeetCode）
https://leetcode.cn/problems/n-queens/description/?envType=study-plan-v2&envId=top-100-liked
思路
-
逐行放置：每一行有且只能有一个皇后，因此我们按行顺序尝试放置，这样天然解决了行冲突。
-
冲突检查：
-
列冲突：用一个布尔数组 cor[] 标记每一列是否已被占用。
-
主对角线冲突：主对角线上所有位置的行列差 (r – i) 为常数，但为了数组下标非负，常用 (r + i) 作为标记。因为同一主对角线上 r + i 相同。
-
副对角线冲突：副对角线上所有位置的行列和 (r + i) 为常数，但为了区分方向，我们用 (n – i + r) 或 (r – i + n) 来保证下标非负。这里使用 n – i + r 是因为当 i 从0到n-1时，n – i 从n到1，加上 r 后范围在 [r, n+r]，保证不越界且同一副对角线上该值相同。
-
-
回溯：当在某一行尝试所有列都无法放置时，回溯到上一行改变皇后的位置，继续搜索。
复杂度
-
时间复杂度：O(n!) 在最坏情况下，但实际由于剪枝，会远小于 n!。例如，第一行有 n 种选择，第二行最多 n-1 种，但受对角线限制，实际分支更少。上界为 O(n!)，但实际运行时间对于 n≤15 是可接受的。
-
空间复杂度：O(n) 主要包括递归栈的深度（最大 n）以及三个标记数组（大小约 2n），均为 O(n)。
代码
class Solution {
public:
// 存储所有有效的棋盘布局
vector<vector<string>> ans;
// 当前正在构建的棋盘（每一行是一个字符串）
vector<string> q;
// 标记数组：
// cor[i] 表示第 i 列是否已被占用
// dg[r+i] 表示主对角线（从左上到右下）是否被占用
// udg[n – i + r] 表示副对角线（从右上到左下）是否被占用
int cor[100], dg[100], udg[100];
// 深度优先搜索，r 表示当前正在放置第 r 行（从0开始）
void dfs(int r, int n) {
// 如果已经放置完所有行，说明找到一个有效解
if (r == n) {
ans.push_back(q); // 将当前棋盘加入结果集
return;
}
// 尝试在当前行的每一列放置皇后
for (int i = 0; i < n; i++) {
// 检查当前位置是否合法：列、主对角线、副对角线均未被占用
if (!cor[i] && !dg[r + i] && !udg[n – i + r]) {
// 放置皇后
q[r][i] = 'Q';
// 标记该列和两条对角线为占用
cor[i] = dg[r + i] = udg[n – i + r] = 1;
// 递归处理下一行
dfs(r + 1, n);
// 回溯：撤销当前行的放置，恢复状态
cor[i] = dg[r + i] = udg[n – i + r] = 0;
q[r][i] = '.';
}
}
}
// 主函数：生成所有N皇后解
vector<vector<string>> solveNQueens(int n) {
// 初始化棋盘，全部填充为 '.'
q.assign(n, string(n, '.'));
// 从第0行开始搜索
dfs(0, n);
// 返回所有解
return ans;
}
};
