牛客回溯专题刷到 BM59 的时候我明显感觉到一道坎。前面做全排列、组合你只需要在一维数组上反复交换元素N皇后一来问题直接搬上二维棋盘每放一个皇后要同时盯住列、主对角线、副对角线三类状态试错了往后退还得把上一颗皇后留下的所有痕迹都清干净。这个“标记—递归—还原”的循环就是回溯算法的骨架。说白了N皇后是回溯思想最完整的样板题。准备面试、蓝桥杯或者校招笔试它都是绕不开的一类题。这篇我会把 BM59 的完整解法、逐行注释、四皇后手工推演、剪枝优化和调试踩坑都过一遍目标是看完后你不光能 AC还能跟人把回溯讲明白。1. N皇后问题的本质为什么这道题是回溯的“教科书”1.1 问题拆解三个约束条件一个天然优势先回顾题目在一个 n×n 的棋盘上放 n 个皇后任意两个皇后不能在同一行、同一列、同一条主对角线、同一条副对角线。BM59 的典型返回值是一个二维字符串数组每个字符串代表一行Q表示皇后.表示空位。很多新手拿到这题第一反应是问题不复杂啊但真写起来棋盘从一维变二维状态检查就容易乱。我把约束拆开看行约束一行最多一个皇后。所以可以按行递归每次只给当前行选一列行冲突被这个循环顺序天然消除不需要额外标记。列约束需要一个数组记录哪些列已经被占O(1) 判断。对角线约束关键观察是主对角线上任意两格的row - col相同副对角线上任意两格的row col相同。因此用两个数组分别记录这两类差值是否出现过就能做到 O(1) 判断。这里有个很容易被忽略的点C 数组下标不能是负数而row - col的范围是[-(n-1), n-1]。所以 BM59 的代码里我习惯写成diag1[row - col n - 1]整体平移 n-1让下标落在[0, 2n-2]。这个n-1不是算法本身的障碍但漏了它轻则越界重则本地跑得好好的一提交就出诡异的崩溃。1.2 为什么是回溯而不是暴力枚举再想为什么这题要用回溯而不是暴力暴力当然也能解从 n² 个格子里选 n 个位置再逐个检查组合数 C(n², n) 的增长非常吓人。稍微聪明一点的做法是枚举列号的排列——每行放一个皇后行的顺序固定只要选一个列号排列但 n! 一样是指数级。回溯的收益在于每放一个皇后立刻用三个标记数组判断当前点是否可用不可用就跳过不用等到棋盘摆完再检查。这本质上是在搜索树上做剪枝把大量非法状态在更浅的层数就砍掉。框架也非常统一void backtrack(int row) { if (row n) { // 已经处理完最后一行保存答案 ans.emplace_back(board); return; } for (int c 0; c n; c) { if (col[c] || diag1[row - c n - 1] || diag2[row c]) continue; place(row, c); // 做选择放皇后 backtrack(row 1); // 递归处理下一行 remove(row, c); // 撤销选择拿掉皇后 } }这个框架值得背但不值得死记做选择是往棋盘和三个标记数组里写入递归是带着新状态走下一层撤销是递归返回后把所有写入清掉。三者缺一不可。我第一次学的时候总觉得撤销是多余的反正递归返回后那些变量会被覆盖。直到自己写了一遍才发现如果没有撤销同一层 for 循环枚举下一列时上一列留下的 Q 和标记还在后面的分支全被污染最终答案是错乱的。这个坑我在第 5 章会专门按排查链路讲一遍。2. 四皇后手工推演把解空间树走一遍2.1 四皇后的两个合法答案与其直接上大 n 的代码我建议先在纸上把四皇后走一遍。n4 的答案只有两个搜索树足够小能让你看清回溯到底在做什么。方案第0行第1行第2行第3行解一列1列3列0列2解二列2列0列3列1为什么这两组坐标合法列号分别是{1,3,0,2}和{2,0,3,1}互不重复主对角线值row-col分别对应{-1,-2,2,1}和{-2,1,-1,2}没有重复副对角线值rowcol分别对应{1,4,2,5}和{2,1,5,4}也没有重复。三条约束同时满足就是合法摆法。2.2 手动推演从(0,0)出发必然碰壁从 (0,0) 开局的整棵子树其实全部无解。这个过程可以一步步写出来第 1 行第 0 列被列占用第 1 列呢(0,0) 的主对角线值是row - col 0(1,1) 的主对角线值也是 0冲突不能放。剩下第 2 列和第 3 列可以临时试试。如果第 1 行放 (1,2)到第 2 行第 0 列被占第 2 列被占候选只剩第 1 列和第 3 列。但 (2,1) 在副对角线上和 (1,2) 冲突两格的row col都等于 3(2,3) 在主对角线上和 (1,2) 冲突两格的row - col都等于 -1。第二行整层没有空位立刻宣告失败。如果第 1 行放 (1,3)第 2 行还勉强能放 (2,1)但到第 3 行只能剩下列 3而 (3,3) 的主对角线值等于 0跟 (0,0) 撞在同一条主对角线上依然失败。所以 (0,0) 这一个起点就带走了三个不同分支。这就是剪枝的实际效果你不需要把整棵搜索树走完只要某一行发现一个可放的位置都没有这棵子树就可以整体放弃。2.3 从(0,1)出发如何走向解一(0,1) 是四皇后第一个解的起点。第 1 行候选列有第 0 列和第 3 列(1,0) 可以放但接着 (2,2) 放了以后第 3 行唯一能放的第 3 列又和 (2,2) 的主对角线冲突死路(1,3) 才是活路。确定 (0,1) 和 (1,3) 后第 2 行的合法位置只剩 (2,0)第 3 行的合法位置只剩 (3,2)于是拿到解一。从 (0,2) 出发完全对称的路径会走到解二(0,3) 与 (0,0) 镜像对称同样无解。所以整个四皇后就是这两个解。我建议你也拿 n5 在草稿纸上画一次你会发现搜索树在第一层就有很多分支提前死掉这就是回溯比暴力全枚举快的原因剪枝不是事后补救而是每条路径一旦露头就立刻掐掉。3. BM59标准解法的代码实现与关键细节3.1 先看 C 完整解法直接给一份可以提交的 C 实现class Solution { private: void dfs(int n, int row, vectorint col, vectorint diag1, vectorint diag2, vectorstring board, vectorvectorstring ans) { if (row n) { ans.push_back(board); return; } for (int c 0; c n; c) { if (col[c] || diag1[row - c n - 1] || diag2[row c]) continue; col[c] 1; diag1[row - c n - 1] 1; diag2[row c] 1; board[row][c] Q; dfs(n, row 1, col, diag1, diag2, board, ans); col[c] 0; diag1[row - c n - 1] 0; diag2[row c] 0; board[row][c] .; } } public: vectorvectorstring solveNQueens(int n) { vectorvectorstring ans; vectorstring board(n, string(n, .)); vectorint col(n, 0); vectorint diag1(2 * n - 1, 0); vectorint diag2(2 * n - 1, 0); dfs(n, 0, col, diag1, diag2, board, ans); return ans; } };代码不长但每一行都有讲究。board初始化为 n 行、每行 n 个.递归过程中往指定位置填Q最终走到第 n 行时棋盘本身就已经是标准输出格式直接ans.push_back(board)即可不需要额外转换。3.2 为什么是三个标记数组而不是四个这个问题我被问过很多次行约束去哪了答案在第 1 章说过按行递归天然保证每行只放一个行冲突不需要额外标记。有些人一开始会写出一个isSafe(row, col, board)函数每次现场扫描之前的行和两条对角线正确性没问题但这是 O(n) 的判断放在每层循环里会把整体复杂度推高。标记数组的写法把每次判断压成 O(1)代码也更直观。diag1的偏移量再强调一次主对角线row - col是常量范围从-(n-1)到n-1C 数组不支持负下标统一加n-1映射到0到2n-2。diag2用row col天然落在0到2n-2不需要偏移。很多资料把diag1写成diag1[row col]那是没搞清楚两条对角线方向的区别照抄代码就会出问题。3.3 Python 版本与 C 的差异如果面试或者日常刷题用 Python可以这样写def solve_n_queens(n): ans [] board [[.] * n for _ in range(n)] col, diag1, diag2 set(), set(), set() def dfs(row): if row n: ans.append([.join(r) for r in board]) return for c in range(n): d1 row - c d2 row c if c in col or d1 in diag1 or d2 in diag2: continue board[row][c] Q col.add(c) diag1.add(d1) diag2.add(d2) dfs(row 1) board[row][c] . col.remove(c) diag1.remove(d1) diag2.remove(d2) dfs(0) return ansPython 版我的选择是col、diag1、diag2三个set因为可读性最好n 在十几以内 set 的开销完全能接受。如果你追求极致性能可以把 set 换成 list 或 bytearray下标存 0/1原理和 C 一样。这里特别提醒Python 初始化棋盘千万别写[[.] * n] * n。这个写法把同一个内层列表复制了 n 份改board[0][2]会让所有行都跟着变。正确写法是列表推导式[[.] * n for _ in range(n)]。一旦遇到“只放一个 Q结果打印出一整列 Q”的灵异现象先检查这里。4. 剪枝优化从能过到跑得快4.1 对称性剪枝第一层只搜一半先说一个思路非常简单、但实现容易翻车的优化左右镜像。棋盘左右对折后皇后位置按列对称合法性完全不变。所以第一行只需要枚举前 ceil(n/2) 列把搜到的解做一次列镜像就能得到另一半解。n4 时第一行只需试第 0 列和第 1 列手动推演已经验证过(0,0) 无解(0,1) 给出解一镜像一下 (0,2) 就是解二(0,3) 镜像 (0,0) 也是无解。要注意的是当 n 是奇数第一行的皇后落在正中间那一列时镜像后的解和原解其实是同一个不能重复加入答案。处理办法是先检查镜像是否与当前解相同或者干脆对中间列的结果单独去重。这个额外的判断有时候比省下的时间还麻烦所以在竞赛和笔试里我一般推荐先写朴素版保底AC 了再考虑优化。对称剪枝更适合拿来在面试里聊思路展示你对解空间有理解。4.2 位运算把三个标记压进三个整数再说一个更有技术含量的优化位运算。思路是把三个标记数组压进三个整数用位掩码表示不可放的位置。假设 n ≤ 31int 的低 n 位就够用。void dfs(int row, int col, int ld, int rd, const int n, vectorvectorstring ans, vectorint queens) { if (row n) { vectorstring board(n, string(n, .)); for (int i 0; i n; i) board[i][queens[i]] Q; ans.push_back(board); return; } int avail ((1 n) - 1) ~(col | ld | rd); while (avail) { int p avail (-avail); // 取最低的 1即选一个可放列 avail avail - 1; // 把这个列位从候选里去掉 int c __builtin_ctz(p); // 该位对应的列号 queens[row] c; dfs(row 1, col | p, (ld | p) 1, (rd | p) 1, n, ans, queens); } }这里最容易迷糊的是(ld | p) 1和(rd | p) 1。主对角线row - col保持常数意味着当行号加 1 时列号也要加 1才能继续站在这条对角线上。所以主对角线的占用掩码在传入下一行时要整体左移一位对应列号更大的一侧。副对角线row col保持常数行号加 1 时列号要减 1掩码整体右移一位。这个平移动作就是用位运算模拟了数组下标row - c和row c在行号变化时的迁移。位运算版实测下来n12 时和数组版的差距已经能明显感觉到数组版要继续跑一会位运算版刷一下就结束到 n14、15 差距更大。OJ 上朴素版通常也能过位运算主要帮你建立底层直觉面试聊剪枝思路的时候也用得上。5. 踩坑实录从错误答案到 AC 的排查链路5.1 坑一撤销不完整导致棋盘“脏”了第一个坑是我自己真实掉进去的。把参数改成引用传参之后我在 C 代码里把撤销写漏了递归返回之后忘了把board[row][c]恢复成.。现象很诡异n4 时 ans 里居然有某些行同时出现两颗 Q 的棋盘而且解的数量也不对。排查时我在 dfs 开头打印row和当前棋盘发现同一行进入下一次 for 循环时上一列留下的 Q 还竖在那儿。再往下一列放的时候看起来就像“放了两颗皇后”。根因就是撤销不完整。修复的方法是递归调用后立刻恢复现场board[row][c] .同时清掉三个标记。提示如果递归函数里存在多个提前 return 的分支务必保证每个分支在 return 前都完成撤销。我自己的习惯是只在函数开头做递归出口一旦进入循环所有返回路径都集中在函数末尾的恢复处不容易漏。5.2 坑二对角线下标为负导致越界第一次写 N皇后时我图省事直接在diag1[row - col]上操作。本地 n4、n5 跑都正常n8 直接崩溃。用 AddressSanitizer 一跑定位到 vector 越界错误信息指向diag1的负下标。原因就是row - col为负时它并没有变成“自动取最后一个元素”而是未定义行为。修复就是row - col n - 1。这行代码看起来只是加了个常数实际上是整个数组方案成立的根基。如果你用diag1[row - col]但给 diag1 开了一个很大的数组负下标问题依然存在因为负数不会因为数组够大就变成合法访问。5.3 坑三参数按值传递导致超时还有一个典型的性能坑。递归函数签名写成dfs(int row, vectorint col, vectorint diag1, vectorint diag2, vectorstring board)所有状态全部按值传递。小 n 的时候没事n12 突然卡顿严重。原因是每一层递归都把三个长度约为 2n 的数组和整个棋盘完整复制一份递归树有大量节点复制开销乘上节点数就直接爆炸。修复方式是改成引用传参代价是必须在递归返回后手动撤销。这其实就是坑一的背景很多人被引用传参坑过之后索性用值传递结果又掉进超时的坑。正确姿势是引用 严格撤销。5.4 坑四Python 列表引用共享前面提到过[[.] * n] * n的坑这里再展开说。这个初始化方式在 Python 中非常阴险因为它不会直接报错而是让你在运行到一半时看到“一整行全是 Q”这种不可能出现的棋盘。定位方法很简单用id(board[0])和id(board[1])比较如果相同说明这几行是同一个对象。修复就是列表推导式。我把这些症状和修复整理成一张表刷题遇到类似问题可以直接对照症状根因修复输出棋盘同行多 Q、解错乱递归返回后未撤销 Q 和标记递归调用后恢复 board 和三个标记本地崩溃或提交后结果莫名错误diag1下标为负row - col n - 1做偏移n 稍大就超时参数按值传递导致大量拷贝改用引用传参配合严格撤销棋盘输出一整列 Q初始化用了同列表复制[[.] * n for _ in range(n)]这些坑单独看都不大但组合在一起就足以让人在 BM59 上磨一个晚上。我的建议是第一次写这题宁可写得笨一点也要保证撤销逻辑完整再考虑优化。6. 从 BM59 延伸回溯题的通用模板6.1 一套模板三类变体BM59 刷完之后回溯题完全可以靠一套思维模型通吃。看下面的伪代码def backtrack(路径, 选择列表): if 满足结束条件: 记录路径 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择每类题目的差异只在于三个地方全排列路径是当前前缀排列选择列表是还没用过的数字用used数组筛掉已用的路径长度等于数组长度时记录。组合总和路径是当前组合选择列表从start下标开始避免重复用 target 减去当前值做剪枝。解数独路径是棋盘选择列表是某个空格的候填数字约束是所在行、列、九宫格。N皇后和它们最大的不同是每一层递归固定推进一行路径隐含在row里只有列号是需要枚举的选择。抓住这个差异你就知道为什么 N皇后要额外维护三个标记数组而全排列只需要一个used。6.2 刷题顺序建议如果你想把回溯彻底吃透我建议按这个顺序走LeetCode 46/47 全排列吃透used数组和撤销逻辑。LeetCode 78/90 子集理解start下标如何控制组合方向避免重复。LeetCode 39/40 组合总和加一道求和剪枝学会在递归参数里携带累计状态。BM59 N皇后从一维路径跳到二维棋盘理解多维状态标记。LeetCode 37 解数独约束从两个对角线扩展到行、列、九宫格复杂度高但套路一致。这一串走完回溯基本没死角。而且你会发现N皇后在中间起到的“顿悟”作用非常明显它强迫你想清楚状态标记如何设计、状态如何还原这两个问题想明白了其他回溯题都是套壳。6.3 关于这道题我的一点体会最后说点个人的东西。BM59 我前后写过三个版本第一版朴素标记数组却因为值传递超时第二版改成引用传参加上严格撤销终于 AC第三版才折腾位运算。回头看N皇后教会我的其实不是怎么放皇后而是“进入递归之前要想清楚自己弄脏了什么返回之前必须收拾干净”。这个习惯在后来的深搜、状态压缩甚至写业务代码里的资源回滚时都让我少踩很多坑。如果你现在卡在 BM59 上别急着看题解先拿四皇后在草稿纸上把搜索树画出来很多疑问会在那个瞬间自己想通。 
长河君 · 2026/9/9 1:49:19 · 阅读 1.2k N皇后与回溯算法：从BM59题解到剪枝优化与状态还原
牛客回溯专题刷到 BM59 的时候我明显感觉到一道坎。前面做全排列、组合你只需要在一维数组上反复交换元素N皇后一来问题直接搬上二维棋盘每放一个皇后要同时盯住列、主对角线、副对角线三类状态试错了往后退还得把上一颗皇后留下的所有痕迹都清干净。这个“标记—递归—还原”的循环就是回溯算法的骨架。说白了N皇后是回溯思想最完整的样板题。准备面试、蓝桥杯或者校招笔试它都是绕不开的一类题。这篇我会把 BM59 的完整解法、逐行注释、四皇后手工推演、剪枝优化和调试踩坑都过一遍目标是看完后你不光能 AC还能跟人把回溯讲明白。1. N皇后问题的本质为什么这道题是回溯的“教科书”1.1 问题拆解三个约束条件一个天然优势先回顾题目在一个 n×n 的棋盘上放 n 个皇后任意两个皇后不能在同一行、同一列、同一条主对角线、同一条副对角线。BM59 的典型返回值是一个二维字符串数组每个字符串代表一行Q表示皇后.表示空位。很多新手拿到这题第一反应是问题不复杂啊但真写起来棋盘从一维变二维状态检查就容易乱。我把约束拆开看行约束一行最多一个皇后。所以可以按行递归每次只给当前行选一列行冲突被这个循环顺序天然消除不需要额外标记。列约束需要一个数组记录哪些列已经被占O(1) 判断。对角线约束关键观察是主对角线上任意两格的row - col相同副对角线上任意两格的row col相同。因此用两个数组分别记录这两类差值是否出现过就能做到 O(1) 判断。这里有个很容易被忽略的点C 数组下标不能是负数而row - col的范围是[-(n-1), n-1]。所以 BM59 的代码里我习惯写成diag1[row - col n - 1]整体平移 n-1让下标落在[0, 2n-2]。这个n-1不是算法本身的障碍但漏了它轻则越界重则本地跑得好好的一提交就出诡异的崩溃。1.2 为什么是回溯而不是暴力枚举再想为什么这题要用回溯而不是暴力暴力当然也能解从 n² 个格子里选 n 个位置再逐个检查组合数 C(n², n) 的增长非常吓人。稍微聪明一点的做法是枚举列号的排列——每行放一个皇后行的顺序固定只要选一个列号排列但 n! 一样是指数级。回溯的收益在于每放一个皇后立刻用三个标记数组判断当前点是否可用不可用就跳过不用等到棋盘摆完再检查。这本质上是在搜索树上做剪枝把大量非法状态在更浅的层数就砍掉。框架也非常统一void backtrack(int row) { if (row n) { // 已经处理完最后一行保存答案 ans.emplace_back(board); return; } for (int c 0; c n; c) { if (col[c] || diag1[row - c n - 1] || diag2[row c]) continue; place(row, c); // 做选择放皇后 backtrack(row 1); // 递归处理下一行 remove(row, c); // 撤销选择拿掉皇后 } }这个框架值得背但不值得死记做选择是往棋盘和三个标记数组里写入递归是带着新状态走下一层撤销是递归返回后把所有写入清掉。三者缺一不可。我第一次学的时候总觉得撤销是多余的反正递归返回后那些变量会被覆盖。直到自己写了一遍才发现如果没有撤销同一层 for 循环枚举下一列时上一列留下的 Q 和标记还在后面的分支全被污染最终答案是错乱的。这个坑我在第 5 章会专门按排查链路讲一遍。2. 四皇后手工推演把解空间树走一遍2.1 四皇后的两个合法答案与其直接上大 n 的代码我建议先在纸上把四皇后走一遍。n4 的答案只有两个搜索树足够小能让你看清回溯到底在做什么。方案第0行第1行第2行第3行解一列1列3列0列2解二列2列0列3列1为什么这两组坐标合法列号分别是{1,3,0,2}和{2,0,3,1}互不重复主对角线值row-col分别对应{-1,-2,2,1}和{-2,1,-1,2}没有重复副对角线值rowcol分别对应{1,4,2,5}和{2,1,5,4}也没有重复。三条约束同时满足就是合法摆法。2.2 手动推演从(0,0)出发必然碰壁从 (0,0) 开局的整棵子树其实全部无解。这个过程可以一步步写出来第 1 行第 0 列被列占用第 1 列呢(0,0) 的主对角线值是row - col 0(1,1) 的主对角线值也是 0冲突不能放。剩下第 2 列和第 3 列可以临时试试。如果第 1 行放 (1,2)到第 2 行第 0 列被占第 2 列被占候选只剩第 1 列和第 3 列。但 (2,1) 在副对角线上和 (1,2) 冲突两格的row col都等于 3(2,3) 在主对角线上和 (1,2) 冲突两格的row - col都等于 -1。第二行整层没有空位立刻宣告失败。如果第 1 行放 (1,3)第 2 行还勉强能放 (2,1)但到第 3 行只能剩下列 3而 (3,3) 的主对角线值等于 0跟 (0,0) 撞在同一条主对角线上依然失败。所以 (0,0) 这一个起点就带走了三个不同分支。这就是剪枝的实际效果你不需要把整棵搜索树走完只要某一行发现一个可放的位置都没有这棵子树就可以整体放弃。2.3 从(0,1)出发如何走向解一(0,1) 是四皇后第一个解的起点。第 1 行候选列有第 0 列和第 3 列(1,0) 可以放但接着 (2,2) 放了以后第 3 行唯一能放的第 3 列又和 (2,2) 的主对角线冲突死路(1,3) 才是活路。确定 (0,1) 和 (1,3) 后第 2 行的合法位置只剩 (2,0)第 3 行的合法位置只剩 (3,2)于是拿到解一。从 (0,2) 出发完全对称的路径会走到解二(0,3) 与 (0,0) 镜像对称同样无解。所以整个四皇后就是这两个解。我建议你也拿 n5 在草稿纸上画一次你会发现搜索树在第一层就有很多分支提前死掉这就是回溯比暴力全枚举快的原因剪枝不是事后补救而是每条路径一旦露头就立刻掐掉。3. BM59标准解法的代码实现与关键细节3.1 先看 C 完整解法直接给一份可以提交的 C 实现class Solution { private: void dfs(int n, int row, vectorint col, vectorint diag1, vectorint diag2, vectorstring board, vectorvectorstring ans) { if (row n) { ans.push_back(board); return; } for (int c 0; c n; c) { if (col[c] || diag1[row - c n - 1] || diag2[row c]) continue; col[c] 1; diag1[row - c n - 1] 1; diag2[row c] 1; board[row][c] Q; dfs(n, row 1, col, diag1, diag2, board, ans); col[c] 0; diag1[row - c n - 1] 0; diag2[row c] 0; board[row][c] .; } } public: vectorvectorstring solveNQueens(int n) { vectorvectorstring ans; vectorstring board(n, string(n, .)); vectorint col(n, 0); vectorint diag1(2 * n - 1, 0); vectorint diag2(2 * n - 1, 0); dfs(n, 0, col, diag1, diag2, board, ans); return ans; } };代码不长但每一行都有讲究。board初始化为 n 行、每行 n 个.递归过程中往指定位置填Q最终走到第 n 行时棋盘本身就已经是标准输出格式直接ans.push_back(board)即可不需要额外转换。3.2 为什么是三个标记数组而不是四个这个问题我被问过很多次行约束去哪了答案在第 1 章说过按行递归天然保证每行只放一个行冲突不需要额外标记。有些人一开始会写出一个isSafe(row, col, board)函数每次现场扫描之前的行和两条对角线正确性没问题但这是 O(n) 的判断放在每层循环里会把整体复杂度推高。标记数组的写法把每次判断压成 O(1)代码也更直观。diag1的偏移量再强调一次主对角线row - col是常量范围从-(n-1)到n-1C 数组不支持负下标统一加n-1映射到0到2n-2。diag2用row col天然落在0到2n-2不需要偏移。很多资料把diag1写成diag1[row col]那是没搞清楚两条对角线方向的区别照抄代码就会出问题。3.3 Python 版本与 C 的差异如果面试或者日常刷题用 Python可以这样写def solve_n_queens(n): ans [] board [[.] * n for _ in range(n)] col, diag1, diag2 set(), set(), set() def dfs(row): if row n: ans.append([.join(r) for r in board]) return for c in range(n): d1 row - c d2 row c if c in col or d1 in diag1 or d2 in diag2: continue board[row][c] Q col.add(c) diag1.add(d1) diag2.add(d2) dfs(row 1) board[row][c] . col.remove(c) diag1.remove(d1) diag2.remove(d2) dfs(0) return ansPython 版我的选择是col、diag1、diag2三个set因为可读性最好n 在十几以内 set 的开销完全能接受。如果你追求极致性能可以把 set 换成 list 或 bytearray下标存 0/1原理和 C 一样。这里特别提醒Python 初始化棋盘千万别写[[.] * n] * n。这个写法把同一个内层列表复制了 n 份改board[0][2]会让所有行都跟着变。正确写法是列表推导式[[.] * n for _ in range(n)]。一旦遇到“只放一个 Q结果打印出一整列 Q”的灵异现象先检查这里。4. 剪枝优化从能过到跑得快4.1 对称性剪枝第一层只搜一半先说一个思路非常简单、但实现容易翻车的优化左右镜像。棋盘左右对折后皇后位置按列对称合法性完全不变。所以第一行只需要枚举前 ceil(n/2) 列把搜到的解做一次列镜像就能得到另一半解。n4 时第一行只需试第 0 列和第 1 列手动推演已经验证过(0,0) 无解(0,1) 给出解一镜像一下 (0,2) 就是解二(0,3) 镜像 (0,0) 也是无解。要注意的是当 n 是奇数第一行的皇后落在正中间那一列时镜像后的解和原解其实是同一个不能重复加入答案。处理办法是先检查镜像是否与当前解相同或者干脆对中间列的结果单独去重。这个额外的判断有时候比省下的时间还麻烦所以在竞赛和笔试里我一般推荐先写朴素版保底AC 了再考虑优化。对称剪枝更适合拿来在面试里聊思路展示你对解空间有理解。4.2 位运算把三个标记压进三个整数再说一个更有技术含量的优化位运算。思路是把三个标记数组压进三个整数用位掩码表示不可放的位置。假设 n ≤ 31int 的低 n 位就够用。void dfs(int row, int col, int ld, int rd, const int n, vectorvectorstring ans, vectorint queens) { if (row n) { vectorstring board(n, string(n, .)); for (int i 0; i n; i) board[i][queens[i]] Q; ans.push_back(board); return; } int avail ((1 n) - 1) ~(col | ld | rd); while (avail) { int p avail (-avail); // 取最低的 1即选一个可放列 avail avail - 1; // 把这个列位从候选里去掉 int c __builtin_ctz(p); // 该位对应的列号 queens[row] c; dfs(row 1, col | p, (ld | p) 1, (rd | p) 1, n, ans, queens); } }这里最容易迷糊的是(ld | p) 1和(rd | p) 1。主对角线row - col保持常数意味着当行号加 1 时列号也要加 1才能继续站在这条对角线上。所以主对角线的占用掩码在传入下一行时要整体左移一位对应列号更大的一侧。副对角线row col保持常数行号加 1 时列号要减 1掩码整体右移一位。这个平移动作就是用位运算模拟了数组下标row - c和row c在行号变化时的迁移。位运算版实测下来n12 时和数组版的差距已经能明显感觉到数组版要继续跑一会位运算版刷一下就结束到 n14、15 差距更大。OJ 上朴素版通常也能过位运算主要帮你建立底层直觉面试聊剪枝思路的时候也用得上。5. 踩坑实录从错误答案到 AC 的排查链路5.1 坑一撤销不完整导致棋盘“脏”了第一个坑是我自己真实掉进去的。把参数改成引用传参之后我在 C 代码里把撤销写漏了递归返回之后忘了把board[row][c]恢复成.。现象很诡异n4 时 ans 里居然有某些行同时出现两颗 Q 的棋盘而且解的数量也不对。排查时我在 dfs 开头打印row和当前棋盘发现同一行进入下一次 for 循环时上一列留下的 Q 还竖在那儿。再往下一列放的时候看起来就像“放了两颗皇后”。根因就是撤销不完整。修复的方法是递归调用后立刻恢复现场board[row][c] .同时清掉三个标记。提示如果递归函数里存在多个提前 return 的分支务必保证每个分支在 return 前都完成撤销。我自己的习惯是只在函数开头做递归出口一旦进入循环所有返回路径都集中在函数末尾的恢复处不容易漏。5.2 坑二对角线下标为负导致越界第一次写 N皇后时我图省事直接在diag1[row - col]上操作。本地 n4、n5 跑都正常n8 直接崩溃。用 AddressSanitizer 一跑定位到 vector 越界错误信息指向diag1的负下标。原因就是row - col为负时它并没有变成“自动取最后一个元素”而是未定义行为。修复就是row - col n - 1。这行代码看起来只是加了个常数实际上是整个数组方案成立的根基。如果你用diag1[row - col]但给 diag1 开了一个很大的数组负下标问题依然存在因为负数不会因为数组够大就变成合法访问。5.3 坑三参数按值传递导致超时还有一个典型的性能坑。递归函数签名写成dfs(int row, vectorint col, vectorint diag1, vectorint diag2, vectorstring board)所有状态全部按值传递。小 n 的时候没事n12 突然卡顿严重。原因是每一层递归都把三个长度约为 2n 的数组和整个棋盘完整复制一份递归树有大量节点复制开销乘上节点数就直接爆炸。修复方式是改成引用传参代价是必须在递归返回后手动撤销。这其实就是坑一的背景很多人被引用传参坑过之后索性用值传递结果又掉进超时的坑。正确姿势是引用 严格撤销。5.4 坑四Python 列表引用共享前面提到过[[.] * n] * n的坑这里再展开说。这个初始化方式在 Python 中非常阴险因为它不会直接报错而是让你在运行到一半时看到“一整行全是 Q”这种不可能出现的棋盘。定位方法很简单用id(board[0])和id(board[1])比较如果相同说明这几行是同一个对象。修复就是列表推导式。我把这些症状和修复整理成一张表刷题遇到类似问题可以直接对照症状根因修复输出棋盘同行多 Q、解错乱递归返回后未撤销 Q 和标记递归调用后恢复 board 和三个标记本地崩溃或提交后结果莫名错误diag1下标为负row - col n - 1做偏移n 稍大就超时参数按值传递导致大量拷贝改用引用传参配合严格撤销棋盘输出一整列 Q初始化用了同列表复制[[.] * n for _ in range(n)]这些坑单独看都不大但组合在一起就足以让人在 BM59 上磨一个晚上。我的建议是第一次写这题宁可写得笨一点也要保证撤销逻辑完整再考虑优化。6. 从 BM59 延伸回溯题的通用模板6.1 一套模板三类变体BM59 刷完之后回溯题完全可以靠一套思维模型通吃。看下面的伪代码def backtrack(路径, 选择列表): if 满足结束条件: 记录路径 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择每类题目的差异只在于三个地方全排列路径是当前前缀排列选择列表是还没用过的数字用used数组筛掉已用的路径长度等于数组长度时记录。组合总和路径是当前组合选择列表从start下标开始避免重复用 target 减去当前值做剪枝。解数独路径是棋盘选择列表是某个空格的候填数字约束是所在行、列、九宫格。N皇后和它们最大的不同是每一层递归固定推进一行路径隐含在row里只有列号是需要枚举的选择。抓住这个差异你就知道为什么 N皇后要额外维护三个标记数组而全排列只需要一个used。6.2 刷题顺序建议如果你想把回溯彻底吃透我建议按这个顺序走LeetCode 46/47 全排列吃透used数组和撤销逻辑。LeetCode 78/90 子集理解start下标如何控制组合方向避免重复。LeetCode 39/40 组合总和加一道求和剪枝学会在递归参数里携带累计状态。BM59 N皇后从一维路径跳到二维棋盘理解多维状态标记。LeetCode 37 解数独约束从两个对角线扩展到行、列、九宫格复杂度高但套路一致。这一串走完回溯基本没死角。而且你会发现N皇后在中间起到的“顿悟”作用非常明显它强迫你想清楚状态标记如何设计、状态如何还原这两个问题想明白了其他回溯题都是套壳。6.3 关于这道题我的一点体会最后说点个人的东西。BM59 我前后写过三个版本第一版朴素标记数组却因为值传递超时第二版改成引用传参加上严格撤销终于 AC第三版才折腾位运算。回头看N皇后教会我的其实不是怎么放皇后而是“进入递归之前要想清楚自己弄脏了什么返回之前必须收拾干净”。这个习惯在后来的深搜、状态压缩甚至写业务代码里的资源回滚时都让我少踩很多坑。如果你现在卡在 BM59 上别急着看题解先拿四皇后在草稿纸上把搜索树画出来很多疑问会在那个瞬间自己想通。