LeetCode 51. N皇后——回溯+位运算优化：三个位掩码控制冲突
LeetCode 51. N皇后——回溯+位运算优化：三个位掩码控制冲突
适读人群：Java中高级工程师、算法竞赛选手 | 阅读时长：约25分钟 | 难度：困难
开篇故事
N皇后是回溯算法的经典教材题，几乎每本算法书都会讲。但大多数教程讲完朴素回溯就结束了，很少有人深入到位运算优化这一层。
我第一次见到 N 皇后的位运算解法是在《编程之美》里，当时就被那三行魔法代码震惊了：用三个整型变量（col、diag1、diag2），通过按位或和移位操作，O(1) 判断当前列是否合法。整个回溯搜索不需要任何数组，只有纯粹的位运算。
理解这三个掩码的含义，需要先理解对角线的数学规律：左对角线（/方向）的所有格子行+列值相同，右对角线（\方向）的所有格子行-列值相同。这个规律转化为位掩码，就是这个题最精妙的地方。今天我们把朴素版和位运算版都讲清楚。
一、题目解析
题目： 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n，返回所有不同的 n 皇后问题的解决方案。
约束分析：
- 每一行恰好放一个皇后（因为每行只能有一个，行遍历隐含了这一点）。
- 每一列只能有一个皇后：用 colUsed 集合记录已占用列。
- 每条
/对角线只能有一个皇后：同一/对角线上的格子行+列 = 常数，用 diag1Used 集合记录。 - 每条
\对角线只能有一个皇后：同一\对角线上的格子行-列 = 常数（或行-列+n-1保证非负），用 diag2Used 集合记录。
二、解法一：朴素回溯（数组记录）
代码
import java.util.*;
public class Solution_Basic {
private List<List<String>> result = new ArrayList<>();
private int[] queens; // queens[row] = col，表示第row行皇后在第col列
public List<List<String>> solveNQueens(int n) {
queens = new int[n];
Arrays.fill(queens, -1);
backtrack(n, 0, new HashSet<>(), new HashSet<>(), new HashSet<>());
return result;
}
private void backtrack(int n, int row,
Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) {
if (row == n) {
result.add(generateBoard(n));
return;
}
for (int col = 0; col < n; col++) {
if (cols.contains(col)) continue;
if (diag1.contains(row + col)) continue; // /对角线：行+列
if (diag2.contains(row - col)) continue; // \对角线：行-列
queens[row] = col;
cols.add(col);
diag1.add(row + col);
diag2.add(row - col);
backtrack(n, row + 1, cols, diag1, diag2);
queens[row] = -1;
cols.remove(col);
diag1.remove(row + col);
diag2.remove(row - col);
}
}
private List<String> generateBoard(int n) {
List<String> board = new ArrayList<>();
for (int row = 0; row < n; row++) {
char[] line = new char[n];
Arrays.fill(line, '.');
line[queens[row]] = 'Q';
board.add(new String(line));
}
return board;
}
}复杂度分析
- 时间复杂度： O(n!)，每行有越来越少的合法列（第 row 行最多 n-row 个合法位置），总搜索节点数 <= n!。
- 空间复杂度： O(n)，三个 HashSet 最多各存 n 个元素，queens 数组 O(n)，递归栈 O(n)。
三、解法二：位运算三掩码优化
三个掩码的含义
用三个整型变量代替三个 HashSet：
col：第 j 位为1 表示第 j 列已被占用。diag1：由/方向对角线占用情况压缩的掩码。处理方式：当皇后在第 row 行第 c 列时，row + c = 常数，下一行/对角线的影响列会右移1（col + 1）。用diag1 >> 1传递到下一行（因为行数+1，列数也+1，在"新行"的视角，之前的对角线限制在掩码中右移）。等等，这里需要仔细解释：
对角线掩码的数学推导：
设当前处理第 row 行。若第 row-1 行在列 c 放了一个皇后，它在 / 方向对角线上影响的下一行（row）是列 c-1（因为 / 对角线从左下到右上，向右上走，换成"向下看"是向左走）。
不对，让我重新理解：
\对角线（从左上到右下）：第 row-1 行的皇后在列 c，它威胁第 row 行的列 c+1（右移）。/对角线（从右上到左下）：第 row-1 行的皇后在列 c，它威胁第 row 行的列 c-1（左移）。
所以：
diag1（\方向）：传递到下一行时整体左移1位（diag1 << 1）。diag2（/方向）：传递到下一行时整体右移1位（diag2 >> 1）。
col 不需要移位，因为列冲突在每一行都是同一列。
当前行可用列 = ~(col | diag1 | diag2) 的后 n 位
代码
import java.util.*;
public class Solution {
private List<List<String>> result = new ArrayList<>();
private int[] queens;
private int n;
public List<List<String>> solveNQueens(int n) {
this.n = n;
this.queens = new int[n];
// limit：后n位全为1的掩码，用于限制有效列范围
int limit = (1 << n) - 1;
backtrack(0, 0, 0, 0, limit);
return result;
}
/**
* @param row 当前处理的行
* @param col 已占用的列掩码
* @param diag1 \方向对角线掩码（已经针对当前行移位过）
* @param diag2 /方向对角线掩码（已经针对当前行移位过）
* @param limit 后n位全为1的限制掩码
*/
private void backtrack(int row, int col, int diag1, int diag2, int limit) {
if (row == n) {
result.add(generateBoard());
return;
}
// 计算当前行可用列：取反三个掩码的OR，再与limit做AND（只看后n位）
int available = limit & (~(col | diag1 | diag2));
while (available != 0) {
int position = available & (-available); // lowbit：最低位的1
int c = Integer.numberOfTrailingZeros(position); // 该列的下标
queens[row] = c;
// 递归下一行：
// col | position：将当前列标记为占用
// (diag1 | position) << 1：\对角线左移（占用列向右传播）
// (diag2 | position) >> 1：/对角线右移（占用列向左传播）
backtrack(row + 1,
col | position,
(diag1 | position) << 1,
(diag2 | position) >> 1,
limit);
available &= available - 1; // 清除最低位，枚举下一个可用列
}
}
private List<String> generateBoard() {
List<String> board = new ArrayList<>();
for (int r = 0; r < n; r++) {
char[] line = new char[n];
Arrays.fill(line, '.');
line[queens[r]] = 'Q';
board.add(new String(line));
}
return board;
}
}Mermaid 图：位掩码传递过程（n=4）
复杂度分析
- 时间复杂度： O(n!)，搜索树结构与朴素版相同，但每个节点的处理从 O(n)（HashSet 操作）降到 O(1)（位运算），整体快约 n 倍。
- 空间复杂度： O(n)，queens 数组和递归栈，不需要 HashSet。
四、解法三：数学分析+记忆化（统计方案数）
如果只需要统计方案数（LeetCode 52 N皇后II），可以用数学上已知的结论或者直接位运算统计，无需记录具体方案。这里给出 LeetCode 52 的位运算版本作为参考：
public class Solution_Count {
private int count = 0;
public int totalNQueens(int n) {
int limit = (1 << n) - 1;
solve(0, 0, 0, limit);
return count;
}
private void solve(int col, int diag1, int diag2, int limit) {
if (col == limit) { count++; return; }
int available = limit & (~(col | diag1 | diag2));
while (available != 0) {
int position = available & (-available);
solve(col | position,
(diag1 | position) << 1,
(diag2 | position) >> 1,
limit);
available &= available - 1;
}
}
}这版代码不需要记录皇后位置，代码极简。
五、举一反三
位掩码在约束搜索中的通用模式
// 用位掩码管理"已占用"集合的通用模式：
int occupied = 0; // 初始为空
// 占用位置 pos（0-indexed）
occupied |= (1 << pos);
// 释放位置 pos
occupied ^= (1 << pos);
// 查询位置 pos 是否空闲
boolean free = (occupied >> pos & 1) == 0;
// 枚举所有空闲位置（在 limit 范围内）
int available = limit & ~occupied;
while (available != 0) {
int pos = Integer.numberOfTrailingZeros(available & -available);
// 处理位置 pos
available &= available - 1;
}六、踩坑实录
坑一：diag1 左移还是右移搞混
记忆方法：\ 对角线从左上到右下，向下走一行，同一条对角线的列数增加1（向右）。在掩码视角，"占用的列向右传播"= 掩码左移（低位到高位 = 小列到大列）。所以 \ 对角线传递时掩码左移（<< 1）。/ 对角线相反，传递时右移（>> 1）。
坑二：limit 的作用
每次移位后，掩码可能增长到超过 n 位，& limit 是必须的，否则会把不存在的列（>n-1）当成有效列。
坑三：queens 数组不是必须的
如果题目只需要统计方案数（LeetCode 52），不需要 queens 数组；如果需要输出具体方案（LeetCode 51），才需要 queens 数组记录每行的皇后列。
坑四：available & (-available) 的整型溢出
当 available 的最高位（符号位）为1时，-available 会是一个负数，但 Java 中 int & int 的结果是按位操作，不影响正确性。实际上由于我们始终 & limit（limit 后 n 位有效，n <= 9），available 的高位始终为0，不会出现这个问题。
七、总结
N 皇后的位运算解法是位运算在搜索问题中应用的典范：
- 三个掩码：col（列冲突）、diag1（
\对角线冲突，左移传递）、diag2（/对角线冲突，右移传递）。 - 候选计算：
limit & ~(col | diag1 | diag2)一步得出当前行所有可用列。 - lowbit 枚举：
available & -available提取最低位，available &= available-1清除最低位，O(1) 枚举每个候选列。
这三个技巧的组合，让 N 皇后的代码从 30+ 行的朴素版压缩到了几行的精简版，运行效率提升约 n 倍。
| 解法 | 每节点操作 | 总时间 | 额外空间 |
|---|---|---|---|
| HashSet 回溯 | O(n) | O(n × n!) | O(n) |
| 位运算回溯 | O(1) | O(n!) | O(n) |
补充深入讲解：N皇后问题的数学本质与三位掩码优化
N皇后的历史背景与数学结构
八皇后问题由国际象棋棋手马克斯·贝瑟尔于1848年提出，是组合数学和计算机科学史上最著名的问题之一。推广到 N 皇后后，问题的求解方案数随 N 的增长非常有趣：1,1,0,2,10,4,40,92,352,724,2680,...（N=1到11的方案数）。N=8 时恰好是 92 种方案，这是国际象棋棋盘上的完整答案。
N 皇后问题没有封闭形式的公式来计算方案数，每个 N 都需要实际搜索。对于大 N（比如 N=25），即使是最优化的回溯算法也需要相当长的时间，目前已知 N=27 的方案数是 234907967154122528。N 皇后的求解是测试计算机性能和并行计算算法的经典基准之一。
三位掩码的设计思想
三位掩码（cols、diag1、diag2）是 N 皇后最经典的位运算优化，值得深入理解其设计思想。
普通方法用三个数组分别记录哪些列、哪些正对角线、哪些反对角线已被占用，每次检查需要 O(1) 的数组查找，看起来已经很快。但位掩码方法更进一步：将"当前行哪些列可以放皇后"这个问题，压缩成一个整数运算。
具体地：用 cols（n 位整数）记录哪些列被占用；用 diag1 记录正对角线（""方向），从行 r 到行 r+1 时，diag1 左移一位；用 diag2 记录反对角线（"/"方向），从行 r 到行 r+1 时，diag2 右移一位。
当处理第 r 行时，当前行被占用的列的掩码是 cols | diag1 | diag2，取反后得到当前行可用列的掩码：available = ~(cols | diag1 | diag2) & ((1<<n)-1)。然后通过 lowbit 操作 x = available & (-available) 取最低可用位，枚举所有可用列放皇后。
整个枚举过程只用位运算，每行的可用列计算是 O(1)，枚举可用列是 O(放置皇后数)，比数组方式更快，CPU 缓存友好性也更好（没有随机内存访问）。
对称性与方案数减半
N 皇后的解具有关于中心轴的对称性：如果某个方案中，将棋盘左右翻转（即将每列的列号 c 变为 n-1-c），得到的也是一个合法方案。这意味着方案总是成对出现的（除了某些特殊方案，其本身左右对称，这种方案在 N 为奇数时存在）。
利用这个对称性，我们可以只枚举第一行皇后在左半边（c <= n/2）的方案，然后将方案数乘以 2（或加上中间列的方案数）。这将搜索空间减半，实际计算速度提高约 2 倍。
但由于我们不只要计数，还要输出所有具体方案，利用对称性需要额外存储和生成镜像方案，代码复杂度增加。在只求方案数的问题（变形题）中，这个优化很有价值；在需要输出所有方案时，额外的代码复杂度可能不值得。
从 N 皇后到约束规划的联系
N 皇后是约束规划（Constraint Programming，CP）领域的入门教科书问题。约束规划是求解复杂约束满足问题的专门方法，比通用回溯更高效，因为它结合了约束传播（提前推导无效变量赋值）和智能搜索策略（如 MRV、前向检查）。
在工业界，约束规划被用于调度优化、资源分配、配置管理等复杂问题。IBM 和 Google 都有商业级的约束规划求解器。理解 N 皇后的回溯优化，是理解约束规划更高级技术的基础。
N皇后在实际工程中的类比应用
N 皇后问题在工程中有一个重要的类比：资源互斥分配问题。如果有 n 个任务和 n 个处理器，每个任务必须在某一时段内运行，且同一处理器在同一时段只能运行一个任务，同时各任务对处理器有特殊限制（类似于皇后不能同行/列/对角），则找出所有合法的任务分配方案就是 N 皇后问题的推广。
另一个类比是缓存替换策略测试：在 n 个缓存行中放置 n 个不同的对象，使得没有两个对象因为缓存冲突（类似"同一列"）或地址对齐冲突（类似"同一对角线"）而相互干扰。这类问题在高性能计算和嵌入式系统开发中实际存在，N 皇后的回溯框架提供了求解思路。
N皇后的代码实现细节与输出格式
N 皇后问题的输出要求是字符串列表的列表，每个内层列表代表一个解，每个字符串代表棋盘的一行（'Q' 表示皇后，'.' 表示空格）。这个输出格式要求在回溯过程中记录每行皇后的列下标，最后一次性构建字符串列表。
在记录每行皇后位置时，用一个 int[] queens 数组，queens[r] 表示第 r 行皇后所在的列下标（0-indexed）。找到完整解时，遍历 queens 数组，对每行构建长度为 N 的字符串（第 queens[r] 个字符为 'Q'，其余为 '.'）。
字符串构建可以用 char[] 数组然后 new String(chars)，也可以用 StringBuilder，两种方式都可以。用 String.valueOf(char[]) 或 new String(charArray, offset, count) 可以直接从 char[] 构建字符串。
N皇后与全排列的关联
N 皇后问题与全排列有深刻的联系：如果不考虑对角线约束，N 皇后问题等价于"在每行放一个皇后，且每列恰好放一个皇后"，这就是 1 到 N 的一个全排列（queens[i] = j 表示第 i 行的皇后在第 j 列）。
加上对角线约束后，有效解只是所有全排列的一个子集。因此 N 皇后的回溯可以看作"有约束的全排列"：枚举 N 个列下标的全排列，过滤掉违反对角线约束的排列。
三位掩码优化正是利用了这个视角：cols 掩码对应"已用列"（全排列中已选的元素），diag1 和 diag2 对应正反对角线约束（全排列的附加约束）。相比逐行逐列检查，位掩码一次性计算出当前行所有可用的列位置，是从"全排列"角度对约束检查的极致优化。
N皇后题目的代码量管理
N 皇后（LeetCode 51）虽然逻辑并不复杂，但要写出完整的代码，包括回溯框架、约束检查、结果格式化（构建字符串列表），代码量不小，在面试的压力下容易出现细节错误。
一个管理代码复杂度的好方法是：先写框架，再填细节。框架包括：主函数（初始化，调用 backtrack，返回结果）、backtrack 函数（终止条件，遍历列，检查合法性，做选择，递归，撤销选择）。框架写好后，再实现 isValid（检查是否合法）和 buildResult（根据 queens 数组构建字符串列表）。
用三位掩码优化时，框架更简洁（不需要 isValid 函数，合法性检查在 backtrack 内联完成），但需要正确处理掩码的传递和移位。如果面试时觉得三位掩码实现有风险，可以先用 isValid 方式写出正确代码，再提及"可以用位掩码优化"，展示知识深度而不冒写错的风险。
N皇后的实际运行速度
N=8 时，N 皇后有 92 个解，回溯算法通常在 1 毫秒以内完成（Java 实现）。N=15 时，有 2279184 个解，需要几秒。N=20 时，解的数量约为 3.9 亿，需要分钟级别的计算时间。LeetCode 51 的约束是 N <= 9，所以标准回溯解法绰绰有余。
理解这个量级感有助于在面试中正确评估算法的适用范围：当题目说 N <= 9，回溯没有问题；当 N 可以到 20 或更大，需要考虑更高效的算法（如并行计算、位操作优化）。这种"量级感"是工程师思维的重要组成部分。
N皇后是回溯算法的经典入门问题，三位掩码优化展示了位运算在约束检查中的强大威力。掌握基础回溯框架，理解位掩码的优化原理，这道题就完全掌握了。
N皇后回溯是算法入门的经典题，值得每位工程师认真掌握。