题目描述
在 N×N 棋盘上放 N 个皇后，使任意两个都不在同一行、同一列、同一条对角线上。返回所有摆法。
n = 4
输出 = 2 种摆法
思路解析
N=8 时光摆法就上亿种，绝大多数一眼就违规，全枚举出来再筛根本扛不住。
既然每行必有且只有一个皇后，那就一行行来。在第 r 行放之前，先看这个列、这两条对角线有没有被占——没占才放。
逐行放，所以不用查行。只需查三样：同一列、主对角线（行−列 相同）、副对角线（行+列 相同）。
第 0 行：试 (0,0)：先在第 0 行第 0 列放一个皇后，试试这条路走不走得通。
第 1 行：只能 (1,2)：第 1 行里，列 0（同列）和 (1,1)（对角线）都被上面的皇后封了，最靠前能放的是 (1,2)。
第 2 行：无处可放：到第 2 行傻眼了：每个格子都被前两个皇后的列或斜线盯上，一个都放不了。这条路死了，回溯。
退回去换 (0,1)：一路退回第 0 行，把皇后挪到 (0,1) 重新试。换个开局，往往就柳暗花明。
顺下来了：一个完整解：从 (0,1) 出发，第 1 行放 (1,3)、第 2 行 (2,0)、第 3 行 (2,2)，四个皇后互不攻击，第一个解到手。再继续回溯能找到另一个对称解。
约束类回溯的范本：把限制（同列/对角线）变成 O(1) 的剪枝，逐行推进，死路立刻回退。
参考代码（Python）
Python
1def solveNQueens(n):
2 res = []; cols = set(); diag = set(); anti = set()
3 board = [[class="cl-str">"."] * n for _ in range(n)]
4 def bt(r):
5 if r == n: res.append([class="cl-str">"".join(row) for row in board]); return
6 for c in range(n):
7 if c in cols or r-c in diag or r+c in anti: continue # 冲突，跳过
8 cols.add(c); diag.add(r-c); anti.add(r+c); board[r][c]=class="cl-str">"Q"
9 bt(r + 1)
10 cols.discard(c); diag.discard(r-c); anti.discard(r+c); board[r][c]=class="cl-str">"." # 回溯
11 bt(0); return res复杂度分析
- 时间复杂度：O(N!) —— 每行选列，层层剪枝
- 空间复杂度：O(N) —— 三个集合 + 递归栈
套路模板
逐行递归、冲突就 continue、放下记占用、回溯清占用。对角线用 r−c 和 r+c 编号，是这题最妙的一笔。
Python
1def bt(r):
2 if r == n: 收集一个解; return
3 for c in range(n):
4 if 冲突(r, c): continue
5 放下(r, c) + 记录占用
6 bt(r + 1)
7 撤回(r, c) + 清除占用易错点
- ❌ 对角线只判一条 → ✅ 主对角线 r−c、副对角线 r+c 都要判（皇后两个斜向都能攻击，少判一条会放出互相攻击的皇后）
- ❌ 放下记了占用，回溯忘了清 → ✅ 放下/撤回成对出现（不清占用，后面的分支会以为那些列/对角线还被占，漏掉合法解）
- ❌ 收解时存 board 引用 → ✅ 存 board 每行的字符串快照（board 会被后续修改，存引用会让所有解变成最后一个棋盘）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。