企业官网建设流程全解析

N皇后是回溯算法里的常青树，LintCode 34题正好是它的计数版：N皇后问题 II。给定一个整数 n，返回 n 皇后不同解的数量。注意，不是返回棋盘布局，而是只返回一个数字。很多人刷完N皇后I之后，觉得II就是去掉打印棋盘的逻辑而已，实际动手写会发现没那么简单——计数题的剪枝深度、状态压缩技巧、常数优化空间，都比“把所有解铺出来”更适合研究。这篇博文就以 LintCode 34 为线索，从经典回溯讲到位运算加对称剪枝，把每一步为什么这样做讲清楚，代码可以直接抄，思路可以迁移到大量搜索类题目，适合刚学完回溯、准备面试算法题，或者被N皇后折磨过一轮的朋友。

1. 题目到底在问什么：从打印棋盘到只数个数

1.1 先看懂N皇后II和N皇后I的差异

N皇后I要求返回所有合法布局，通常返回一个字符串列表集合，每个解要画成一个棋盘。N皇后II只要一个整数，返回值是 int 或者 long，搜索过程完全一样，区别只在递归到第 n 层时：前者做一次快照存进结果集，后者count++完事。

这个差异看起来只是“少存点东西”，但对代码结构的影响其实非常大。N皇后I里你需要在递归过程中维护一个二维棋盘或一个皇后位置列表，每次放皇后要改状态，回溯时还要还原；N皇后II可以直接用三个 boolean 数组甚至三个整数掩码来维护冲突状态，连棋盘本身都不需要维护。换句话说，II 这个版本逼着你从“关心布局”切换到“关心约束状态的压缩表达”，这正是位运算切入的最佳场景。

我在帮别人 review 代码时见过很多次这种情况：有人把 N皇后I 的解法拿过来，去掉棋盘输出部分，跑一遍发现结果不对，然后开始怀疑是不是递归终止条件写错了。其实问题往往出在他仍然在维护棋盘，而计数版根本不需要这些额外状态。把不必要的状态去掉之后，递归结构会清爽很多，也更容易做进一步优化。

1.2 为什么计数版更考验剪枝功底

先看一组数据：4 皇后解数是 2，8 皇后是 92，12 皇后是 14200，14 皇后已经到了 365596。每增加一行，状态空间都呈指数膨胀，暴力枚举所有排列是完全不可行的。回溯本身已经比枚举所有排列高效得多，但同一套回溯思路，不同写法的常数差距可以到几十倍。

计数题因为不用存储结果，反而可以放心地把能砍的搜索分支全砍掉。比如后面要说的位运算，布尔数组版本每层要遍历 n 列去判断冲突，位运算版本一次位操作就能拿到全部可用列，然后只枚举真正能放的位置。再比如对称性剪枝，利用“左右翻转后的解仍然是合法解”这个性质，第一行只搜索一半列，搜索量直接接近减半。这些优化在 N皇后I 里也能做，但要同时维护棋盘列表，写起来会啰嗦得多；在 II 这种纯计数场景里，优化可以做得非常纯粹。

很多人在这道题上卡住，不是不知道皇后不能同行同列同斜线，而是不知道如何快速判断对角线冲突，或者不理解位运算掩码的移动方向。下面从最直观的 boolean 数组版本开始，把原理讲清楚，再一步步过渡到位运算和对称剪枝。

2. 回溯法的核心原理与常规实现

2.1 三个冲突条件是怎么变成代码的

N 皇后问题的约束可以拆成四条：不同行、不同列、两条对角线互不攻击。“不同行”在逐行放皇后的回溯中天然满足，因为我们的搜索顺序就是一行只放一个；“不同列”用一个长度为 n 的 boolean 数组 col 记录；“两条对角线”分别用一个 boolean 数组记录。

关键是对角线编号怎么设计。先看从左上到右下的主对角线，这条线上的所有点都满足一个性质：row - col是一个常数。例如棋盘上(0, 0)和(1, 1)在一条主对角线上，0 - 0 = 1 - 1 = 0。再看从右上到左下的副对角线，这条线上的点满足row + col是常数。例如(0, 3)和(1, 2)在一条副对角线上，0 + 3 = 1 + 2 = 3。

所以判断位置(row, c)是否安全，只需要检查三个条件：

• col[c]是否被占用；
• diag1[row + c]是否被占用，对应副对角线；
• diag2[row - c + n - 1]是否被占用，对应主对角线。

这里row - c可能是负数，所以加上n - 1偏移到数组合法下标。很多代码能背下来，但面试官一问“为什么一个是row + c，一个是row - c + n - 1”就容易露馅。我的建议是自己画一个 4×4 棋盘，把每条对角线标出来，很快就能看出规律。

2.2 经典回溯实现

用 Java 写最直白的版本，核心逻辑就是标准的 DFS 加回溯：

public class Solution { private int count = 0; private boolean[] col; private boolean[] diag1; private boolean[] diag2; private int n; public int totalNQueens(int n) { this.n = n; col = new boolean[n]; diag1 = new boolean[2 * n - 1]; diag2 = new boolean[2 * n - 1]; dfs(0); return count; } private void dfs(int row) { if (row == n) { count++; return; } for (int c = 0; c < n; c++) { if (col[c] || diag1[row + c] || diag2[row - c + n - 1]) { continue; } col[c] = true; diag1[row + c] = true; diag2[row - c + n - 1] = true; dfs(row + 1); col[c] = false; diag1[row + c] = false; diag2[row - c + n - 1] = false; } } }

Python 版本结构完全一致，只是把数组和递归写进 class 里，这里就不重复贴了。你要是第一次写，建议先把这个版本跑通，因为所有后续优化都是从它演变来的，逻辑最直白，也最容易对照验证。

2.3 一个容易被忽略的问题：恢复现场

回溯最常见的错误就是“恢复现场不干净”。递归进入前把占用位置标成 true，返回之后必须全部标成 false。三个数组的置位和复位要一一对应，不能只恢复 col 而忘了 diag1、diag2。

我见过一个很经典的翻车场景：有人优化了一下代码，把三个数组的置位合并成一行，像this.col[c] = this.diag1[...] = this.diag2[...] = true;，看着很聪明，但复位的时候少写了一个，结果 n=4 只算出 1 个解而不是 2 个。排查半天，最后发现是 diag2 没有恢复。

另一个细节是数组大小。diag1和diag2的长度应该是2 * n - 1，不是 n。row + c的最大值是(n - 1) + (n - 1) = 2n - 2，所以长度为2n - 1的数组下标范围 0 到2n - 2，刚刚好。如果你把数组长度写成 n，一跑就会越界。还有，row - c + n - 1的范围也要检查，最小值是0 - (n - 1) + n - 1 = 0，最大值是(n - 1) - 0 + n - 1 = 2n - 2，同样安全。

3. 位运算优化：把搜索常数压到极致

3.1 位掩码的设计思路

boolean 数组版本很直观，但每层递归都要循环 n 列，逐一判断冲突。位运算版本换一种思路：用一个整数的每个 bit 表示棋盘的一列，1 表示被占用或受攻击，0 表示空闲。

三个整数各司其职：

• cols：哪些列已经被皇后占用；
• diag1：哪些列位置被主对角线方向的皇后攻击；
• diag2：哪些列位置被副对角线方向的皇后攻击。

当前行所有可用位置怎么算？很好办，三者的按位或就是“所有不能放的位置”，取反之后和棋盘宽度做与，剩下的 1 就是能放的位置：

int available = limit & ~(cols | diag1 | diag2);

其中limit = (1 << n) - 1，只保留低 n 位有效。

这里必须解释一下为什么需要limit。~操作会把所有高位都变成 1，如果直接用，available 里就会混进一堆棋盘之外的伪位置，递归就会跑偏。用limit与一下，相当于只关心真实棋盘上的 n 列。

拿到 available 之后，要快速取出每一个可放位置。最经典的位运算技巧是 lowbit：

int pos = available & (-available); // 取出最低位的 1 available &= available - 1; // 清除最低位的 1

available & -available利用补码性质，结果只有最低位的 1 保留，其他位全为 0，这就是一个可放置位置对应的位掩码。然后每次把最低位清掉，循环处理剩下的位。

3.2 位运算版 DFS 完整实现

直接给一份完整的 Java 实现：

public class Solution { private int count = 0; private int limit; private int n; public int totalNQueens(int n) { this.n = n; this.limit = (1 << n) - 1; dfs(0, 0, 0, 0); return count; } private void dfs(int row, int cols, int diag1, int diag2) { if (row == n) { count++; return; } int available = limit & ~(cols | diag1 | diag2); while (available != 0) { int pos = available & (-available); available &= available - 1; dfs(row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1); } } }

很多第一次接触位运算版本的朋友，最容易懵的是(diag1 | pos) << 1和(diag2 | pos) >> 1为什么一个左移一个右移。

我的理解方式是这样的：掩码里的 bit 位置代表“列号”。进入下一行之后，主对角线方向上的攻击位置会整体向左下方移动一列，所以 bit 要左移；副对角线方向上的攻击位置会整体向右下方移动一列，所以 bit 要右移。你可以拿 n=4、第一行放第 0 列来手推：

初始cols=0001，diag1=0010，diag2=0000。下一行的 available 等于1100，也就是只能选第 2 列或第 3 列。这时第 1 列确实正被(0,0)的主对角线攻击，副对角线方向没有影响，和几何关系完全吻合。把 first few 步推一遍之后，左右移动的意义就再也忘不掉了。

Python 版本同样的逻辑，但要注意 Python 整数是无限位的，所以limit的截断作用更重要：

class Solution: def totalNQueens(self, n: int) -> int: self.count = 0 self.limit = (1 << n) - 1 self.dfs(0, 0, 0, 0) return self.count def dfs(self, row, cols, diag1, diag2): if row == n: self.count += 1 return available = self.limit & ~(cols | diag1 | diag2) while available: pos = available & -available available &= available - 1 self.dfs(row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1)

3.3 复杂度分析与实测效果

从复杂度上说，位运算版本的时间上界仍然是 O(n!)，因为 N 皇后本身就是在排列空间里做剪枝搜索。但它的常数小到可以忽略不计：每一层不再需要循环 n 列逐一判断，而是直接用三次位运算求出所有可用列，再只针对这些列递归。

空间方面更有意思，boolean 数组版本要开三个长度为 O(n) 的数组，位运算版本只需要三个 int 和三个参数，额外空间是 O(1)，递归栈不算在内的话，几乎不占内存。

我自己在本地测试过，n=12 和 n=13 时，位运算版本比 boolean 数组版本快好几倍，n=14 差距更大。在线评测如果时限比较紧，很多经典回溯版本会卡在 n=14 上，位运算版本通常能顺利跑完。当然，如果题目给的 n 很小，比如 8 以内，两种写法都无所谓，但位运算的思路本身值得掌握，因为很多搜索题都能套用“状态掩码 + lowbit 枚举”这套模板。

4. 对称性剪枝：搜索空间直接砍半

4.1 棋盘左右对称的原理

N 皇后解有一个非常漂亮的性质：一个合法解左右翻转之后，仍然是一个合法解。翻转后，第一行皇后位置从c变成n - 1 - c。如果c不等于n - 1 - c，那么这两个解就是两个不同的解；只有当 n 是奇数，且c正好落在中间列时，翻转前后才是同一个解。

这个性质可以直接用来剪枝：搜索第一行皇后落在左半部分的列，也就是列号0到n / 2 - 1。搜到的每一个解，都自动对应一个第一行皇后在右半部分的镜像解，计数时乘以 2 即可。对于奇数 n，中间列单独搜一次，不能乘 2。

很多题解在讲对称剪枝时只写“枚举一半列然后乘 2”，这句话在 n 为偶数时没问题，在 n 为奇数时会出错，关键就在于漏掉了中间列的特殊处理。

4.2 含对称优化的完整实现

正确做法是把“左半部分搜索结果”和“中间列搜索结果”分开统计，左半部分的结果乘 2，中间列的结果直接加进去。

public class Solution { private int limit; private int n; public int totalNQueens(int n) { this.n = n; this.limit = (1 << n) - 1; int ans = 0; // 第一行只搜左半部分列 for (int c = 0; c < n / 2; c++) { ans += dfs(1, 1 << c, (1 << c) << 1, (1 << c) >> 1); } ans *= 2; // 奇数 n 时，中间列的解左右翻转后仍是自身，只能算一次 if (n % 2 == 1) { int mid = 1 << (n / 2); ans += dfs(1, mid, mid << 1, mid >> 1); } return ans; } private int dfs(int row, int cols, int diag1, int diag2) { if (row == n) { return 1; } int res = 0; int available = limit & ~(cols | diag1 | diag2); while (available != 0) { int pos = available & (-available); available &= available - 1; res += dfs(row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1); } return res; } }

注意这里 dfs 的起点是row = 1，因为第一行已经在外面放好了，初始的三个掩码分别是列掩码、主对角线掩码和副对角线掩码。初始化和普通版本从第 0 行开始完全对应，只要在纸上验算一次就能理解。

有人可能会问：能不能同时做上下对称、旋转对称剪枝？理论上可以，但实现复杂度立刻上涨，而且去重逻辑非常容易出错，做完之后代码也很难向面试官讲清楚。在刷题和面试这个场景，左右对称已经能把搜索量减少接近一半，性价比很高。

4.3 奇数 n 的中间列陷阱

我用 n=5 来验证一下。5 皇后的正确解数是 10，中间列是c=2。第一行皇后放在中间列的解，左右翻转后还是中间列，所以这个解和它的镜像实际上是同一个解。如果统一乘以 2，相当于把中间列的解重复算了一遍，结果就会偏大。

正确的统计方式就是上面代码里的写法：

• 第一行在c=0和c=1时搜出来的解，每个都代表两个实际解，所以全部加起来之后乘以 2；
• 第一行在c=2时搜出来的解，它本身已经代表自己，直接加上去就行了。

这个陷阱非常经典，如果你在网上搜题解，会看到很多版本虽然思路类似，但要么没考虑奇数 n，要么处理方式放在递归内部导致代码绕来绕去。分开统计是最好理解也最不容易出错的做法。

5. 常见问题与排查技巧实录

5.1 高频错误速查表

我整理了这几年帮人排查 N皇后II 时遇到最多的错误，每一条都真实踩过，值得收藏。

如果你跑出来的结果比预期小，优先怀疑恢复现场和终止条件；如果结果大，优先怀疑位运算的截断和对称剪枝的翻倍逻辑。

5.2 边界用例与答案校验

本地调试的时候，先把小规模 n 跑一遍，和已知答案对照：

这些数字是经典序列，如果对不上，基本可以断定是剪枝逻辑或恢复现场的问题，而不是“慢”的问题。

还有一个排查小技巧：在递归到row == n的时候临时输出第一行皇后所在的列，统计一下分布。比如 n=6 时，左右的分布应该是对称的；如果分布极端不均衡，说明你的剪枝把某些合法分支误杀了。

5.3 面试官追问怎么答

面试里这道题的追问通常集中在三个方向：为什么位运算快、对角线掩码为什么左移右移、还能不能更快。

回答“为什么位运算快”时，不要只背“常数小”，要说清楚快在哪：经典回溯每层用 for 循环遍历 n 列，每次都要查三个数组；位运算版本用一次位操作拿到所有可用位置，然后只递归可用位置，循环次数从 n 压缩到实际可行解个数，这才是核心收益。

回答“对角线为什么左移右移”时，用坐标变换解释：掩码 bit 代表列号，进入下一行后主对角线攻击位置相对左移一列，副对角线相对右移一列。配合一个 n=4 的例子画在纸上，一下就说清。

回答“还能不能更快”时，可以提继续做上下对称、旋转对称去重，或者对固定 n 打表，但强调后者在面试里没有价值。比较稳妥的说法是：左右对称剪枝已经能够应付评测数据，再往上属于竞赛优化范畴，工程里很少用到。

最后再分享一个我自己的调试习惯：遇到计数类搜索题，先在小 n 上把朴素版本跑对，再逐步加优化，不要一上来就写位运算加对称剪枝的最终形态。先保证流程正确，再谈性能，不然出了错都不知道是哪一步引入的。N皇后II是少有的能同时练到回溯、状态压缩、剪枝推导的题，把这一题吃透，后面再遇到排列组合类搜索题会顺手很多。