京公网安备11010502063487号上一题要求列出所有摆法，这一题只要求数出有多少种。既然不需要保存每种摆法，就可以把"哪些列、哪些对角线被占"压缩成三个整数位掩码：一位对应一列。每往下一行，两条对角线的影响各移动一位：\ 方向的掩码左移一位，/ 方向的右移一位。"当前行能放的位置"就是三个掩码的并集取反，用 avail & -avail 每次取出最低位的一个可放位置。本文验证这个位运算做法与上一题的集合做法个数完全一致，实测两者的耗时差距，给出五种语言的实现，并把掩码的变化做成分步演示。
完整题目见官方页面（链接在文末）。基准解枚举全部排列再检查对角线，只数个数。一共 9 组用例，n 从 1 到 9：
输入 [1] 输出 1 输入 [2] 输出 0 输入 [3] 输出 0 输入 [4] 输出 2 输入 [5] 输出 10 输入 [6] 输出 4
下面对 n 从 1 到 11，用位运算的 solve 与用集合的回溯（上一题的做法，只数个数）各数了一遍，每个取三次中最快的一次：
n | 解的个数（位运算 solve）| 用集合的回溯得到的个数 | 位运算耗时 | 用集合耗时（各取三次中最快） 1 | 1 | 1 | 0.00 ms | 0.00 ms 2 | 0 | 0 | 0.00 ms | 0.00 ms 3 | 0 | 0 | 0.00 ms | 0.00 ms 4 | 2 | 2 | 0.00 ms | 0.01 ms 5 | 10 | 10 | 0.01 ms | 0.02 ms 6 | 4 | 4 | 0.02 ms | 0.08 ms 7 | 40 | 40 | 0.07 ms | 0.33 ms 8 | 92 | 92 | 0.29 ms | 1.33 ms 9 | 352 | 352 | 1.41 ms | 5.89 ms 10 | 724 | 724 | 6.26 ms | 25.93 ms 11 | 2680 | 2680 | 30.01 ms | 129.96 ms
两种做法在所有 n 上的个数完全一致：1、0、0、2、10、4、40、92、352、724、2680，与文献里已知的 N 皇后解的个数一致。位运算比集合快约 4 倍（n = 10 时 6.26ms 对 25.93ms，n = 11 时 30.01ms 对 129.96ms），因为位运算一次性算出"当前行所有可放位置"，不用逐列检查集合，也没有集合的增删开销。这里的耗时只是 Python 里的实测。
三个位掩码：cols 是已经被占的列，diag1 是被 \ 方向对角线占用的列（相对当前行），diag2 是被 / 方向占用的列。每往下一行，diag1 左移一位，diag2 右移一位，并且用 & full 丢掉超出棋盘的位。当前行的可放位置 avail = full & ~(cols | diag1 | diag2)。cols == full（每一列都放了皇后）时就是一个解。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；JavaScript 的位运算只有 32 位，对 n ≤ 9 足够。
Python · 解法代码def solve(n): full = (1 << n) - 1 # n 个 1：所有列都被占满 def dfs(cols, diag1, diag2): # 三个位掩码：被占用的列、被"\"方向占用、被"/"方向占用（已对齐到当前行） if cols == full: return 1 count = 0 avail = full & ~(cols | diag1 | diag2) # 当前行可以放皇后的位置 while avail: bit = avail & -avail # 取最低位的 1：一个可放的位置 avail ^= bit count += dfs(cols | bit, ((diag1 | bit) << 1) & full, (diag2 | bit) >> 1) # 下一行：两条对角线的影响各移动一位 return count return dfs(0, 0, 0)
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [1] → 1 [2] → 0 [3] → 0 [4] → 2 [5] → 10 [6] → 4
Java · 解法代码class Solution { private int full; public int totalNQueens(int n) { full = (1 << n) - 1; // n 个 1：所有列都被占满 return dfs(0, 0, 0); } private int dfs(int cols, int diag1, int diag2) { // 三个位掩码：被占用的列、"\"方向、"/"方向（已对齐到当前行） if (cols == full) return 1; int count = 0; int avail = full & ~(cols | diag1 | diag2); // 当前行可以放皇后的位置 while (avail != 0) { int bit = avail & -avail; // 取最低位的 1：一个可放的位置 avail ^= bit; count += dfs(cols | bit, ((diag1 | bit) << 1) & full, (diag2 | bit) >> 1); // 下一行：两条对角线的影响各移动一位 } return count; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [1] → 1 [2] → 0 [3] → 0 [4] → 2 [5] → 10 [6] → 4
Go · 解法代码func totalNQueens(n int) int { full := (1 << n) - 1 // n 个 1：所有列都被占满 var dfs func(cols, diag1, diag2 int) int dfs = func(cols, diag1, diag2 int) int { // 三个位掩码：被占用的列、"\"方向、"/"方向（已对齐到当前行） if cols == full { return 1 } count := 0 avail := full &^ (cols | diag1 | diag2) // 当前行可以放皇后的位置 for avail != 0 { bit := avail & -avail // 取最低位的 1：一个可放的位置 avail ^= bit count += dfs(cols|bit, ((diag1|bit)<<1)&full, (diag2|bit)>>1) // 下一行：两条对角线的影响各移动一位 } return count } return dfs(0, 0, 0) }
$ go build -o bin . && ./bin < cases.jsonl [1] → 1 [2] → 0 [3] → 0 [4] → 2 [5] → 10 [6] → 4
JavaScript · 解法代码function totalNQueens(n) { const full = (1 << n) - 1; // n 个 1：所有列都被占满 const dfs = (cols, diag1, diag2) => { // 三个位掩码：被占用的列、"\"方向、"/"方向（已对齐到当前行） if (cols === full) return 1; let count = 0; let avail = full & ~(cols | diag1 | diag2); // 当前行可以放皇后的位置 while (avail) { const bit = avail & -avail; // 取最低位的 1：一个可放的位置 avail ^= bit; count += dfs(cols | bit, ((diag1 | bit) << 1) & full, (diag2 | bit) >> 1); // 下一行：两条对角线的影响各移动一位 } return count; }; return dfs(0, 0, 0); }
$ node run.js < cases.jsonl [1] → 1 [2] → 0 [3] → 0 [4] → 2 [5] → 10 [6] → 4
C++ · 解法代码using namespace std; class Solution { int full; int dfs(int cols, int diag1, int diag2) { // 三个位掩码：被占用的列、"\"方向、"/"方向（已对齐到当前行） if (cols == full) return 1; int count = 0; int avail = full & ~(cols | diag1 | diag2); // 当前行可以放皇后的位置 while (avail) { int bit = avail & -avail; // 取最低位的 1：一个可放的位置 avail ^= bit; count += dfs(cols | bit, ((diag1 | bit) << 1) & full, (diag2 | bit) >> 1); // 下一行：两条对角线的影响各移动一位 } return count; } public: int totalNQueens(int n) { full = (1 << n) - 1; // n 个 1：所有列都被占满 return dfs(0, 0, 0); } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [1] → 1 [2] → 0 [3] → 0 [4] → 2 [5] → 10 [6] → 4
共 9 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 9/9 Java 通过 9/9 Go 通过 9/9 JavaScript 通过 9/9 C++ 通过 9/9
n 分别为 6、8、10、11，每个规模取三次中最快的一次，基准是枚举全部 n! 个排列：
n | 暴力解 | 本文解法
6 | 0.228 ms | 0.021 ms
8 | 14.222 ms | 0.284 ms
10 | （未测，太慢） | 6.326 ms
11 | （未测，太慢） | 30.524 msn = 8 时，位运算回溯 0.28ms，枚举全部排列 14.22ms，约 50 倍。位运算回溯从 n = 10 到 n = 11 增长约 4.8 倍。基准在 n = 10 及以上没有再测。
Python 版本另外对 n 从 1 到 8 的随机取值和枚举排列做了对拍：
随机对拍 40 组（n 取 1 到 8 的随机值），solve 与 brute 的结果全部一致。
n 只有很少的几个值，固定用例已经覆盖了全部小规模输入。另外四种语言只在上面 9 组固定用例上验证过（n 从 1 到 9）。
下面的演示用 n = 4。掩码用 4 位二进制显示，最右边一位是第 0 列，1 表示这一列被占用（或可放）。第 0 行时三个掩码都是 0，可放位置是 1111；放在第 0 列之后，下一行的可放位置是 1100，也就是第 2 列和第 3 列（第 0 列被占，第 1 列在副对角线上）。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终统计出的个数与 solve 的返回值一致。