LeetCode 题解工作台
N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方…
2
题型
6
代码语言
3
相关题
当前训练重点
困难 · 回溯·pruning
答案摘要
我们定义三个数组 , 和 ，分别表示列、正对角线和反对角线上的是否有皇后，如果位置 $(i, j)$ 有皇后，那么 , $dg[i + j]$ 和 $udg[n - i + j]$ 都为 。另外，我们用一个数组 记录当前棋盘的状态，初始时 中的所有元素都是 `'.'`。 接下来，我们定义一个函数 ，表示从第 行开始放置皇后。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
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
解题思路
方法一：DFS(回溯)
我们定义三个数组 , 和 ，分别表示列、正对角线和反对角线上的是否有皇后，如果位置 有皇后，那么 , 和 都为 。另外，我们用一个数组 记录当前棋盘的状态，初始时 中的所有元素都是 '.'。
接下来，我们定义一个函数 ，表示从第 行开始放置皇后。
在 中，如果 ，说明我们已经完成了所有皇后的放置，我们将当前 放入答案数组中，递归结束。
否则，我们枚举当前行的每一列 ，如果位置 没有皇后，即 , 和 都为 ，那么我们可以放置皇后，即把 改为 'Q'，并将 , 和 都置为 ，然后继续搜索下一行，即调用 ，递归结束后，我们需要将 改回 '.' 并将 , 和 都置为 。
在主函数中，我们调用 开始递归，最后返回答案数组即可。
时间复杂度 ，空间复杂度 。其中 是题目给定的整数。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def dfs(i: int):
if i == n:
ans.append(["".join(row) for row in g])
return
for j in range(n):
if col[j] + dg[i + j] + udg[n - i + j] == 0:
g[i][j] = "Q"
col[j] = dg[i + j] = udg[n - i + j] = 1
dfs(i + 1)
col[j] = dg[i + j] = udg[n - i + j] = 0
g[i][j] = "."
ans = []
g = [["."] * n for _ in range(n)]
col = [0] * n
dg = [0] * (n << 1)
udg = [0] * (n << 1)
dfs(0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity grows exponentially with n due to backtracking, approximately O(n!), but pruning reduces unnecessary recursive calls. Space complexity is O(n) for tracking columns and diagonals plus O(n) per board for storing solutions. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate prunes branches early using column and diagonal tracking.
- question_mark
Look for clean recursion and backtracking structure without redundant iterations.
- question_mark
Confirm candidate can generate all distinct board arrangements correctly.
常见陷阱
外企场景- error
Not handling diagonal conflicts correctly, leading to invalid placements.
- error
Modifying the board in place without restoring state during backtracking.
- error
Failing to return results in the required board string format with 'Q' and '.'.
进阶变体
外企场景- arrow_right_alt
Return only the count of N-Queens solutions instead of full board configurations.
- arrow_right_alt
Solve for N-Queens II with restricted pre-placed queens in some rows.
- arrow_right_alt
Adapt the solution to k-Queens on an m x n board with k <= min(m,n).