如果让我从刷题生涯里挑一道“看起来很难、想通了其实就那一层窗户纸”的题目，n皇后绝对排得上号。我第一次在刷题网站里看到它的时候，脑子里第一反应是：这不就是八皇后换了个更大的棋盘吗，模拟搜索不就行了？真动手写了才发现，搜索可以很简单，但怎么搜得优雅、搜得快，甚至怎么把“判断冲突”从O(n)优化到O(1)，这里面藏着一整套算法基本功。n皇后问题也是面试和算法竞赛里的熟客，很多人以为它只是道递归练手题，其实它考察的是回溯、剪枝、状态压缩、对称性优化这一整条链路。
这篇文章我就按自己实际刷题和带新人时常用的一条路径来写：先搞清楚问题模型，再写出能跑通的回溯解法，接着做剪枝和位运算优化，最后汇总一些我实际踩过或者见别人踩过的坑。无论你是刚接触回溯的初学者，还是想从n皇后里再榨出点性能的熟练工，应该都能从这里拿走点东西。
1. 从题目到模型：n皇后问题到底在考什么
1.1 题面与核心约束
n皇后问题的标准描述非常简单：在 n×n 的棋盘上放置 n 个皇后，使得任意两个皇后不在同一行、同一列，也不在同一条对角线上。n=8 就是经典的八皇后，n 可以继续扩大到 10、12、15，甚至更大的规模。
这里的关键是理解“皇后”的攻击方式。国际象棋里的皇后可以横着走、竖着走、斜着走，而且不限步数。所以在棋盘上，一个皇后的势力范围就是它所在的整行、整列，以及横纵两个方向上的所有对角线。任何两个皇后只要进入了彼此的势力范围，就算互相攻击。
我第一次自己推导的时候就被“对角线”坑过。行冲突和列冲突好理解，但对角线上的冲突判断，很多人第一反应是遍历当前行之前的每一行，逐个比较坐标差值。这么做不是不行，但不够优雅，也没理解对角线判断的本质。其实同一个“左上到右下”方向的对角线，上面的格子都满足 row - col 是同一个常数；同一个“右上到左下”方向的对角线，上面的格子都满足 row + col 是同一个常数。这就是后面所有优化方案的数学基础。
1.2 为什么这道题是面试和竞赛的常客
很多人觉得n皇后是“经典老题”，现在的面试早就不考了。但实际情况是，它依然是高频出现的一类题。原因很简单：它能在一道题里同时考察递归、回溯、状态管理、剪枝思想、复杂度分析，而且题目本身不需要任何前置知识，不需要复杂的领域背景。面试官跟你聊这道题，不需要先解释业务背景，直接给你棋盘，你就能写。
另外，n皇后几乎是“回溯算法”的最佳教学案例。回溯算法有一个很通用的模板：做选择、递归、撤销选择。n皇后逐行放置皇后的过程，天然就是一条决策树上的深度优先搜索。每一行选择一个合法的列位置，进入下一行；如果某一行找不到任何合法位置，就回退到上一行，修改上一行的放置位置。这个过程写出来，就是回溯。
竞赛里它出现的频率也不低。不过竞赛题通常不会只让你输出所有解，而是会加一层包装，比如在棋盘上预置一些障碍物、增加一些特殊约束条件，或者把它包装成“放置n个互不攻击的皇后有多少种方案”的计数问题。无论怎么变，核心模型还是那套冲突判断和搜索框架。
1.3 搜索空间到底有多大
在动手写代码之前，我建议先做一个复杂度估算。n皇后最直观的暴力做法是：在 n×n 棋盘上选出 n 个格子，每个格子放一个皇后，方案数是 C(n², n)。这个数字大得离谱，n=8 的时候就已经是 4.4 亿级别了。
而回溯法利用了“每行只能放一个皇后”这个硬约束，把搜索空间压缩到 nⁿ 量级，也就是每一行有 n 种选择，共 n 行。n=8 时是 16,777,216，虽然比 4.4 亿小了很多，但依然不少。实际加上“列冲突和对角线冲突”的剪枝后，能搜索到的节点数会进一步大幅下降。n=8 的解只有92个，n=10 是724个，n=12 是14200个。实测跑一遍就知道，合法解在所有搜索路径里占比非常低，所以剪枝的质量直接决定程序能不能在合理时间内跑完。
2. 回溯法：从最直观的解法到完整可运行的代码
2.1 核心思路：逐行放置 + 冲突检查
回溯法的思路可以拆成三句话：
- 从第0行开始，逐行放置皇后。
- 每一行尝试所有列的位置，如果当前位置不与前面行放置的皇后冲突，就放下去，然后递归进入下一行。
- 如果递归到某一行发现所有列都无法放置，就撤销上一次的放置选择，回到上一行继续尝试下一个列位置。
这个“放置 → 递归 → 撤销”的结构就是回溯算法的基本盘。
我个人的习惯是先不追求效率，写一版最笨但一定能跑对的版本，然后再逐步优化。这样可以确认思路本身没有问题，后续优化出的问题也容易定位。
2.2 先写一版用O(n)扫描的“笨”回溯
第一版实现里，判断当前位置是否合法可以直接遍历之前已经放置好的皇后，检查是否同列、是否在同一对角线上。代码很直观，适合作为“基线版本”。
#include <iostream> #include <vector> #include <string> using namespace std; bool isValid(const vector<string>& board, int row, int col, int n) { // 检查同一列 for (int i = 0; i < row; i++) { if (board[i][col] == 'Q') return false; } // 检查左上到右下的对角线 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 'Q') return false; } // 检查右上到左下的对角线 for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] == 'Q') return false; } return true; } void dfs(vector<vector<string>>& res, vector<string>& board, int row, int n) { if (row == n) { res.push_back(board); return; } for (int col = 0; col < n; col++) { if (!isValid(board, row, col, n)) continue; board[row][col] = 'Q'; dfs(res, board, row + 1, n); board[row][col] = '.'; } } vector<vector<string>> solveNQueens(int n) { vector<vector<string>> res; vector<string> board(n, string(n, '.')); dfs(res, board, 0, n); return res; }这段代码的逻辑很直白。isValid函数负责检查当前位置是否安全，分别扫描当前列、左上方对角线、右上方对角线里有没有已经放置的皇后。dfs函数负责递归搜索，在每一行逐列尝试放置，如果row == n说明所有行都放上了皇后，记录当前棋盘。
这个版本的优点是容易读懂，逻辑不容易出错；缺点是每次检查合法位置都要扫描前面的棋盘，复杂度高。n=8 跑起来完全没问题，n=12 就开始有明显卡顿，n=15 以上基本跑不动。作为初版实现用来验思路足够了。
2.3 用空间换时间的优化：对角线数组
接下来做第一个关键优化：把“检查合法位置”从 O(n) 降到 O(1)。
方法就是引入三个布尔数组：
col[i]：第 i 列是否已经被占用。diag1[i - j + n - 1]：主对角线方向（左上到右下）是否已经被占用。因为 i - j 范围是 -(n-1) 到 n-1，加上 n-1 偏移后映射到数组下标 0 到 2n-2。diag2[i + j]：副对角线方向（右上到左下）是否已经被占用。i + j 范围是 0 到 2n-2，正好对应数组下标。
这三个数组统一用 true 表示被占用，false 表示可放置。每放置一个皇后，就标记对应的列和两条对角线；回溯撤销时再恢复标记。
#include <iostream> #include <vector> #include <string> using namespace std; void dfs(vector<vector<string>>& res, vector<string>& board, vector<bool>& col, vector<bool>& diag1, vector<bool>& diag2, int row, int n) { if (row == n) { res.push_back(board); return; } for (int c = 0; c < n; c++) { int id1 = row - c + n - 1; // 主对角线编号 int id2 = row + c; // 副对角线编号 if (col[c] || diag1[id1] || diag2[id2]) continue; board[row][c] = 'Q'; col[c] = diag1[id1] = diag2[id2] = true; dfs(res, board, col, diag1, diag2, row + 1, n); // 撤销 board[row][c] = '.'; col[c] = diag1[id1] = diag2[id2] = false; } } vector<vector<string>> solveNQueens(int n) { vector<vector<string>> res; vector<string> board(n, string(n, '.')); vector<bool> col(n, false); vector<bool> diag1(2 * n - 1, false); vector<bool> diag2(2 * n - 1, false); dfs(res, board, col, diag1, diag2, 0, n); return res; }写这个版本的时候有个细节值得注意：diag1的数组大小必须是2 * n - 1，diag2同样也是2 * n - 1。我第一次自己写的时候，diag1想当然地用了n，结果 n=4 的时候还好，n 稍微大一点就数组越界或者漏判。这个数组大小是这类题最容易踩的坑之一。
这个版本的性能已经比第一版好很多了。n=12 可以秒出，n=14 也只需要几秒。如果面试要求“写一个能跑的解法”，这个版本基本就够了。
2.4 恢复现场为什么重要
回溯算法里最容易被忽略、也最容易被面试官追问的细节就是“恢复现场”。刚才的代码里，递归返回之后要做的三件事非常关键：把board[row][c]重新改成.，把col[c]、diag1[id1]、diag2[id2]改回 false。
如果你只标记不撤销，下一轮尝试其他列位置的时候，状态会被污染，导致明明可以放置的位置被误判为冲突，进而丢失合法解。我曾经帮人排查过一段n皇后代码，输出结果总是少几个解，最后定位到问题就是递归返回后没有恢复对角线标记。
恢复现场的本质是：递归函数内部对状态的修改，只应该影响当前搜索分支，不应该泄漏到兄弟分支或上层分支。这也是回溯算法和普通递归最大的不同点。记住这句话，很多回溯类问题的调试思路就清晰了。
3. 剪枝与位运算：把性能压榨到极限
3.1 对称性剪枝：利用棋盘的对称性质
如果你只是单纯求n皇后的解的数量，还有一个很酷的优化思路：利用棋盘的对称性。
棋盘左右对称，意味着一个解经过镜像翻转之后还是合法解。比如 n=4 有两个解，把它们镜像翻转一下你就得到另外两个解，但其实总数只有两个，说明每个解自身是镜像对称的。更一般的规律是：如果某一个解在左右镜像后和原来的解不相同，那么镜像后的那个解一定会被枚举到。这就意味着，第一行的皇后列位置其实只需要枚举左半部分就够了，右侧的解可以通过对称性推算出来。
写成计数逻辑大致是这样：
long long total = 0; // 第一行枚举 c = 0 到 n/2（左半部分） for (int c = 0; c <= n / 2; c++) { int id1 = 0 - c + n - 1; int id2 = 0 + c; col[c] = diag1[id1] = diag2[id2] = true; // 如果 n 是奇数且 c 是正中间的列，对称翻转后还是自身，只算一次 if (n % 2 == 1 && c == n / 2) { total += dfsCount(row + 1, col, diag1, diag2, n); } else { total += 2 * dfsCount(row + 1, col, diag1, diag2, n); } col[c] = diag1[id1] = diag2[id2] = false; }这里dfsCount不再是输出棋盘，而是返回从第二行开始能形成的解数量。第一行左边的每一种放法，最终统计时乘 2；只有第一行放在正中间时，镜像前后是同一个搜索分支，不乘 2。
实测下来，对称剪枝能让搜索量大约减少一半，配合后面的位运算优化，n=15 以上也能跑出结果。但要注意一点：如果你要让程序输出所有具体棋盘解，对称剪枝就不好直接用了。因为你剪掉的“右半部分解”需要额外生成镜像棋盘才能输出，代码复杂度会上去不少。我个人遇到“输出所有解”的题目还是老老实实全量搜索，只有遇到“只计数”的题目才上对称剪枝。
3.2 位运算优化：用整数位表示棋盘占用状态
如果说对称剪枝是“思路上的优化”，那
