跳到正文
第 51 题困难

N 皇后

N-Queens

返回 N 皇后问题的所有解：每行一个皇后，任意两个皇后不能同列或同对角线。

在力扣中练习

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

 

提示：

  • 1 <= n <= 9

解题思路

主解法

逐行回溯 · 列与对角线剪枝

一行一行放，冲突就跳过，放满 n 行收集

N 皇后可以按行决策：第 row 行必须放一个皇后，枚举它的列 c。这样天然避免了“同一行”的冲突。

剩下的冲突只有三类：同一列、同一主对角线、同一副对角线。用三个布尔数组分别记录：

  • col[c]：第 c 列是否已被占用；
  • diag1[row - c + n]：主对角线，差相同；
  • diag2[row + c]：副对角线，和相同。
分步图解

第 0 行放在第 1 列；列与两条对角线都没有冲突。

row
0
N=4 · Q 是皇后，灰色是被攻击格
0
1
2
3
0
·
Q
·
·
1
·
·
·
·
2
·
·
·
·
3
·
·
·
·
逐行放皇后；同一列、同一条主/副对角线上不能再有皇后。
已找到的解
[ ]
1 / 4
逐行放置，先放 (0,1)，再放 (1,3)、(2,0)、(3,2)，每个位置都避开了列和对角线。

放之前检查三个数组，放之后同时置 true；递归下一行，返回时再全部撤销。放满 n 行就得到一个完整棋盘。

分步图解

第 0 行放在第 2 列；列与两条对角线都没有冲突。

row
0
N=4 · Q 是皇后，灰色是被攻击格
0
1
2
3
0
·
·
Q
·
1
·
·
·
·
2
·
·
·
·
3
·
·
·
·
逐行放皇后；同一列、同一条主/副对角线上不能再有皇后。
已找到的解
·Q··/···Q/Q···/··Q·
1 / 4
回溯后从第一行第 2 列重新开始，得到镜像的第二个解。

自拟 n=4 只有两个解，且互为镜像。画面上灰色格是被已放皇后攻击的位置，能直观看到剪枝依据。

时间 O(n!)，空间 O(n)（递归栈与三个数组）。

时间 O(n!)空间 O(n)

易错点

  • 只检查列：会漏掉对角线冲突。
  • diag1 下标写成 row - c：可能为负，数组越界。
  • 回溯时只清 board 不清标记：后续分支被错误禁止。
  • 逐格而不是逐行决策：需要额外处理同一行冲突，复杂度更高。

代码与演示

演示输入n = 4

从第 0 行开始逐行放置；每行只放一个，冲突时直接剪枝。

N=4 · Q 是皇后，灰色是被攻击格
0
1
2
3
0
·
·
·
·
1
·
·
·
·
2
·
·
·
·
3
·
·
·
·
逐行放皇后；同一列、同一条主/副对角线上不能再有皇后。
已找到的解
[ ]
1 / 12
查看 C++ 代码

延伸阅读

  • N 皇后是“排列 + 剪枝”的典型：每行一个皇后，列和两条对角线构成三个互斥条件。
  • 进一步优化可以用位运算表示列与两条对角线，把冲突检查压到 O(1) 的位操作。