LeetCode 51. N 皇后
题目描述
✅ 51. N 皇后
题意分析
在
n × n棋盘上放置恰好n个皇后，使任意两个皇后都不在同一行、同一列或同一条斜线上。返回全部不同的合法棋盘，用Q表示皇后、.表示空位；没有解时返回空列表。同一行最多放一个皇后，而皇后数恰好等于行数，所以每行必须放一个。这样可以把问题变成：为每一行选择一个不会与前面行冲突的列，而不必枚举任意格子组合。
解法：按行回溯 + 三组占用标记
核心思路
[!blue]
按行递归。进入
dfs(row)时，前row行各有一个互不攻击的皇后，当前行及之后尚未放置。当前行只尝试每一列，行冲突由递归层次天然排除，剩下只需检查列和两组对角线。同一列的列号相同。沿一条左上到右下的斜线，行列一起增加，
row - col不变；沿另一类斜线，行增列减，row + col不变。因此用三组布尔标记即可在常数时间判断冲突。行列差可能为负，加上n - 1后，两类对角线编号都落在[0, 2n - 2]。若列和两条对角线都空闲，就在棋盘放入皇后并设置三组标记，再递归下一行。返回时同时撤销棋盘字符和三组标记，恢复进入当前分支前的状态，然后继续尝试本行其他列。遇到冲突只跳过当前列，不能结束整行搜索。
row == n表示所有行都已放好，得到一组完整解。结果需要保存每一行的字符串快照，而不是继续被回溯修改的棋盘。每个合法棋盘唯一对应一组逐行列号，搜索逐层枚举这些选择，冲突才剪枝，所以不会遗漏合法解，也不会重复生成同一布局。
解题步骤
- 将棋盘初始化为
.，创建列标记和两组对角线标记，长度分别为n、2n - 1、2n - 1。- 从第零行开始递归。行号已到
n时，把棋盘各行复制为字符串，收集完整方案并返回。- 对当前行逐列尝试，计算列号、
row - col + n - 1和row + col，有任一占用则跳过。- 没有冲突时放入
Q、设置三个标记，递归下一行。- 返回后将该格恢复为
.，清除三个标记，继续本行后面的列。所有分支结束后返回全部方案。
代码实现
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
boolean[] cols = new boolean[n];
boolean[] diag1 = new boolean[2 * n - 1];
boolean[] diag2 = new boolean[2 * n - 1];
dfs(0, board, cols, diag1, diag2, ans);
return ans;
}
private void dfs(
int row,
char[][] board,
boolean[] cols,
boolean[] diag1,
boolean[] diag2,
List<List<String>> ans) {
int n = board.length;
if (row == n) {
List<String> solution = new ArrayList<>(n);
for (char[] line : board) {
solution.add(new String(line));
}
ans.add(solution);
return;
}
for (int col = 0; col < n; col++) {
// 行列差平移后与行列和分别标识两类对角线。
int d1 = row - col + n - 1;
int d2 = row + col;
if (cols[col] || diag1[d1] || diag2[d2]) {
continue;
}
board[row][col] = 'Q';
cols[col] = diag1[d1] = diag2[d2] = true;
dfs(row + 1, board, cols, diag1, diag2, ans);
// 递归结束后同时撤销棋盘与占用，恢复下一种选择的起点。
board[row][col] = '.';
cols[col] = diag1[d1] = diag2[d2] = false;
}
}
}
func solveNQueens(n int) [][]string {
board := make([][]byte, n)
for i := range board {
board[i] = make([]byte, n)
for j := range board[i] {
board[i][j] = '.'
}
}
cols := make([]bool, n)
diag1 := make([]bool, 2*n-1)
diag2 := make([]bool, 2*n-1)
ans := make([][]string, 0)
var dfs func(int)
dfs = func(row int) {
if row == n {
solution := make([]string, n)
for i := range board {
solution[i] = string(board[i])
}
ans = append(ans, solution)
return
}
for col := 0; col < n; col++ {
// 行列差平移后与行列和分别标识两类对角线。
d1, d2 := row-col+n-1, row+col
if cols[col] || diag1[d1] || diag2[d2] {
continue
}
board[row][col] = 'Q'
cols[col], diag1[d1], diag2[d2] = true, true, true
dfs(row + 1)
// 递归结束后同时撤销棋盘与占用，恢复下一种选择的起点。
board[row][col] = '.'
cols[col], diag1[d1], diag2[d2] = false, false, false
}
}
dfs(0)
return ans
}
复杂度分析
- 时间复杂度：保守上界为 $O(n\cdot n!+S\cdot n^2)$，其中
S为合法方案数。列去重后至多搜索列排列及其前缀，每个非叶搜索节点扫描n个位置；每个完整解还要复制 $n^2$ 个棋盘字符。对角线剪枝会减少实际搜索量。- 空间复杂度：不计输出为 $O(n^2)$，棋盘占 $O(n^2)$，三组标记和递归栈占 $O(n)$；全部返回棋盘另占 $O(S\cdot n^2)$。
关键点总结
[!green]
- 每行恰好一个皇后，将格子组合转为逐行选择列，缩小搜索范围。
- 同列、同行列差、同行列和分别对应三类需要维护的冲突。
- 放置和撤销成对更新棋盘与标记，保证兄弟分支互不影响。
- 本题要全部布局，找到一个解后还要继续搜索，并保存独立快照。
易错点总结
[!yellow]
- 行列差没有平移，负数不能作为数组下标；两类对角线数组都需要覆盖
2n - 1个编号。- 撤销时只改棋盘或漏掉某组标记，后续分支会继承上一分支的错误占用。
- 只检查列或其中一组斜线，会放过另一条斜线上的攻击关系。
- 遇到一列冲突就
return，会放弃当前行尚未尝试的其他位置；这里只能跳过该列。- 在
row == n - 1时收集，最后一行还没选择，得到的是不完整布局。- 保存可变棋盘引用，后续回溯会改变已收集的答案；应逐行创建字符串快照。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 52. N 皇后 II | 困难 | 搜索与约束相同，原题只计数，本题要保存每个棋盘布局。 |
| 37. 解数独 | 困难 | 同样回溯填棋盘并维护占用约束，本题按列和对角线剪枝。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！