题目描述
在 N×N 棋盘上放 N 个皇后，使任意两个都不在同一行、同一列、同一条对角线上。返回所有摆法。
思路解析
N=8 时光「16 选 8」就上亿种摆法，绝大多数一眼就违规，全枚举出来再筛根本扛不住。
转折：既然每行必有且只有一个皇后，那就一行行来，把「选 N 个格子」变成「每行选一列」。在第 r 行放之前，先看这列、这两条对角线有没有被占——没占才放，撞了就跳过，整行都放不下就回退上一行。
逐行放，所以不用查行。只需查三样：同一列、主对角线（行−列 相同）、副对角线（行+列 相同）。三个集合 O(1) 判定。
第 0 行 · 试 (0,0)：先在第 0 行第 0 列放一个皇后(试探态)，记下 列0、主对角线 0−0、副对角线 0+0 被占，试试这条路走不走得通。
第 1 行 · 前两列被攻击：进到第 1 行从左往右试：(1,0) 和上面的皇后同列、(1,1) 在主对角线上(行差1=列差1)，都被攻击(红格)，跳过。
第 1 行 · 落子 (1,2)：继续到 (1,2)：列 2 没占、两条对角线也没占 → 安全，放下。记列2、对角线 1−2、1+2 被占，再下探第 2 行。
第 2 行 · 无处可放：负例分支：第 2 行每个格子都被前两个皇后的列或斜线盯上——(2,0)同列、(2,1)在(1,2)的副对角线、(2,2)同列、(2,3)在(1,2)的主对角线。整行没安全列，这条路死了，回溯。
回退第 1 行 · (1,2) 后无路：退回第 1 行，撤掉 (1,2) 并清除它占的列和对角线。再往后试 (1,3)：它在 (0,0) 的主对角线(行差3=列差3)上，也被攻击。第 1 行可放的列试光了，继续往上回退到第 0 行。
退回第 0 行 · 换 (0,1)：一路退回第 0 行，撤掉 (0,0)，把皇后挪到 (0,1) 重新试。换个开局，往往就柳暗花明。
第 1 行 · 推进到 (1,3)：新开局后第 1 行试列：列1同列、(1,0)和(1,2)分别在 (0,1) 的两条对角线上，只有 (1,3) 安全 → 放下，继续下探。
顺下来了 · 一个完整解：接着第 2 行只剩 (2,0)、第 3 行只剩 (3,2)，r 推到 4(== n) → 四个皇后互不攻击，第一个解到手。继续回溯还能找到它的镜像，凑齐 2 个解。
约束类回溯的范本：把限制（同列/对角线）变成 O(1) 的剪枝，逐行推进，死路立刻回退。
参考代码（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!) —— 第 r 行最多剩 N−r 个安全列，层层相乘逼近 N!，但剪枝砍掉大量死分支
- 空间复杂度：O(N) —— 三个集合各至多 N 项 + 递归栈深 N + 棋盘 N×N(可压成一维)
套路模板
逐行递归、冲突就 continue、放下记占用、回溯清占用。对角线用 r−c 和 r+c 编号，是这题最妙的一笔。
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 都要判（皇后两个斜向都能攻击。比如只判 r−c，(0,0) 和 (1,2)…还看不出，但 (0,0) 与 (3,3)、(0,3) 与 (3,0) 这种反斜会被漏放成互相攻击）
- 错误写法：放下记了占用，回溯忘了清 → 正确写法：放下/撤回成对出现（不清占用，回退后那些列/对角线仍被误认为占着，后面分支会漏掉 (0,1) 这条合法解）
- 错误写法：收解时存 board 引用 → 正确写法：存 board 每行的字符串快照（board 会被后续回溯改回 "."，存引用会让所有解都变成最后那个空棋盘）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。