LeetCode 51. N 皇后
目录
题目描述
✅ 51. N 皇后
题意分析
在
n x n的棋盘上摆下n个皇后，任意两个皇后不能互相攻击，也就是不能同行、同列、同一条斜线；要求返回所有不同的摆法，每种摆法用字符串数组描述，Q表示皇后、.表示空格。注意题目要的是全部方案而非方案数，所以搜索到底后必须把整张棋盘的快照收集下来，这直接决定了收集答案时要做深拷贝。
约束信号是数量关系：棋盘
n行，皇后也恰好n个，而同一行装不下两个皇后，于是每行必须且只能放一个。这条推论把「在 $n^2$ 个格子里选 $n$ 个」的组合搜索，降维成「为每一行各选一个列号」的排列搜索，搜索空间从组合数级别压到 $n!$ 以内。另一个信号是规模：
n上限只有 9，说明出题人默认接受指数级搜索，重点考的是剪枝写得干不干净，而不是找多项式算法。边界要留意：
n = 1时有唯一解["Q"]；n = 2和n = 3无解，要能正常返回空列表而不是崩溃或返回半成品；斜线约束是两个方向都要管，只防一条是最典型的漏判。
解法：按行回溯 + 三组占用标记
核心思路
棋盘有
n行且必须放n个皇后，同一行又不能出现两个皇后，因此每行恰好放一个。递归时直接把row当作决策层，每层只枚举这一行的列，同行冲突便从搜索结构中消失。对一个候选位置
(row, col)，只需判断三类冲突：
- 列：同列皇后的
col相同；- 主对角线
\：同一条线上row - col相同，用row - col + n - 1映射到非负下标；- 副对角线
/：同一条线上row + col相同。因此用
cols、diag1、diag2三个布尔数组记录占用情况。进入dfs(row)时维持不变量：前row行各有一个互不攻击的皇后，三个数组与棋盘状态完全一致。候选位置未被占用才落子；递归返回后立即撤销棋盘和三个标记，使下一个分支从相同状态出发。当
row == n，当前棋盘必然是合法完整方案。反过来，任意合法方案在每一行都有唯一列号，DFS 会沿着这组列号走到叶子且不会被错误剪掉，所以方案不漏；每条根到叶路径的列序列不同，所以方案不重。收集答案时要复制每一行，因为棋盘随后还会继续回溯修改。
解题步骤
- 初始化
n × n棋盘为.，并创建长度为n、2n - 1、2n - 1的列和两组对角线标记。- 从第 0 行开始 DFS；当前行依次尝试每一列。
- 计算两个对角线下标。任一标记已占用，说明与前面某个皇后冲突，跳过该列。
- 否则放置
Q并设置三组标记，递归处理下一行。- 子问题返回后，恢复
.并清除三组标记，继续尝试当前行的下一列。- 行号到达
n时，把棋盘逐行转成字符串并加入答案。以
n = 4为例，列序列[1, 3, 0, 2]对应第一组解。放到(0,1)后，(1,0)因row + col = 1冲突，(1,2)因row - col = -1冲突，只有第 3 列可继续。完整搜索还会得到对称方案[2, 0, 3, 1]；从第 0 或第 3 列出发的分支都会在中途无处可放并回溯。
代码实现
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 · n!)：列去重后至多枚举列排列，每个搜索节点还要扫描当前行的n个位置；设解的数量为S，构造答案另需O(S · n²)。对角线剪枝会显著减少实际搜索量。- 空间复杂度：不计返回结果为
O(n²)，棋盘占O(n²)，三组标记和递归栈占O(n)；答案本身占O(S · n²)。
关键点总结
- 先利用“每行恰好一个”按行建搜索树，天然消除同行冲突。
- 用
row - col和row + col给两组对角线编号，把冲突检查降为O(1)。- 回溯状态只有棋盘和三组标记；落子与撤销必须严格对称。
- 正确性可以从“每个合法棋盘唯一对应一组列序列”说明：DFS 枚举所有合法列序列，既不漏也不重。
- 若题目只求方案数，可不保存棋盘；本题必须返回布局，所以叶子处需要生成快照。
易错点总结
- 对角线公式或偏移写错：
(0,1)与(1,2)的row - col都是-1，应判为同一主对角线；数组下标需加n - 1。- 把多个标记的撤销漏掉一项：例如只清棋盘不清
diag1，会把上一分支的占用带到下一分支，导致漏解。- 收集可变棋盘引用：回溯结束后内容会被清空；Java 要
new String(line)，Go 要把每行转成独立字符串。- 终止条件提前：
row == n - 1时最后一行还没完成决策，只有row == n才是完整方案。- 冲突后使用
return：它会放弃当前行后续所有列；这里只应continue。- 只检查一组对角线：例如
(0,3)与(1,2)的row + col都是 3，漏掉副对角线就会接受非法布局。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 52. N 皇后 II | 困难 | 只统计方案数，可去掉棋盘并改用位运算压缩状态 |
| 面试题 08.12. 八皇后 | 困难 | 与本题同构，可用来检验模板是否真的默写熟练 |
| 37. 解数独 | 困难 | 同为约束标记加回溯，但约束按行列宫三组划分且需就地填回原盘 |
| 46. 全排列 | 中等 | 本题去掉对角线约束后的原型，只剩「列不重复」这一条 |
| 79. 单词搜索 | 中等 | 决策维度是四个方向而非一行一列，撤销的是访问标记 |
| 39. 组合总和 | 中等 | 剪枝依据是累计和而非位置冲突，且需靠起始下标去重 |