前言

N 皇后问题要求在n × n的棋盘上放置n个皇后，使得任意两个皇后都不在同一行、同一列或同一条斜线上，返回所有不同的摆放方案。棋盘用字符串数组表示，'Q'表示皇后，'.'表示空位。

最直观的想法是枚举所有格子「放或不放」，但复杂度是2^(n^2)，完全不可行。正确的建模是：每一行恰好放一个皇后。因为共有n行、n个皇后，且每行最多一个，所以每行必须一个。这样搜索空间从「格子组合」降到「每行选一列」，再配合列与斜线的冲突剪枝，规模就可控了。

常见的误解是只检查列、不检查斜线，或者斜线下标算错导致负下标。还有人把「回溯」写成「递归后不撤销状态」，结果第一个解之后所有分支都被污染。本文以 C++17 为准，用三个布尔数组分别记录列、主对角线、副对角线的占用情况，逐行放置并收集棋盘。

一、约束建模：三个方向

皇后放在(row, col)时，会占用：

1. 
   
2. 列：col，范围为0..n-1。
3. 
   
4. 主对角线方向（左上到右下）：同一条线上的格子满足row - col相等。加上偏移n - 1后，索引为row - col + n - 1，范围0..2n-2。
5. 
   
6. 副对角线方向（右上到左下）：同一条线上的格子满足row + col相等，索引为row + col，范围0..2n-2。
7. 
   

之所以能用一个一维数组表示一条对角线，是因为同一条对角线上的所有格子，其row - col（或row + col）是同一个常数。只要该常数对应的布尔值为真，整条线都被占用。

主对角线索引必须加偏移n - 1，否则row < col时得到负数。用负数下标访问std::vector<bool>会转换为巨大的无符号值，属于越界访问，是未定义行为（undefined behavior, UB），通常直接崩溃。

二、逐行回溯

搜索按行推进：

backtrack(row):
如果 row == n：收集当前棋盘，返回
对 col 从 0 到 n-1：
如果 col、主对角线、副对角线任一被占用：跳过
在 (row, col) 放皇后，标记三个方向
backtrack(row + 1)
撤销标记，恢复棋盘

由于每行只放一个，行冲突天然不存在，不需要额外的行数组。递归深度为n，每一层尝试n列，最坏搜索树节点数为O(n!)量级；实际节点数远小于这个上界，因为冲突剪枝会砍掉大量分支。这里不给出具体运行时间，具体规模取决于n和实现。

三、完整实现

// 适用于 C++17
#include <iostream>
#include <string>
#include <vector>

class Solution {
public:
std::vector<std::vector<std::string>> solveNQueens(int n) {
std::vector<std::vector<std::string>> result;
if (n <= 0) return result;

std::vector<std::string> board(
static_cast<std::size_t>(n),
std::string(static_cast<std::size_t>(n), '.'));

std::vector<bool> column(static_cast<std::size_t>(n), false);
std::vector<bool> diag1(static_cast<std::size_t>(2 * n - 1), false);
std::vector<bool> diag2(static_cast<std::size_t>(2 * n - 1), false);

backtrack(0, n, board, column, diag1, diag2, result);
return result;
}

private:
void backtrack(int row, int n,
std::vector<std::string>& board,
std::vector<bool>& column,
std::vector<bool>& diag1,
std::vector<bool>& diag2,
std::vector<std::vector<std::string>>& result) {
if (row == n) {
result.push_back(board); // 拷贝当前棋盘
return;
}

for (int col = 0; col < n; ++col) {
const int d1 = row + col;
const int d2 = row - col + n - 1;

if (column[static_cast<std::size_t>(col)] ||
diag1[static_cast<std::size_t>(d1)] ||
diag2[static_cast<std::size_t>(d2)]) {
continue;
}

board[static_cast<std::size_t>(row)][static_cast<std::size_t>(col)] = 'Q';
column[static_cast<std::size_t>(col)] = true;
diag1[static_cast<std::size_t>(d1)] = true;
diag2[static_cast<std::size_t>(d2)] = true;

backtrack(row + 1, n, board, column, diag1, diag2, result);

board[static_cast<std::size_t>(row)][static_cast<std::size_t>(col)] = '.';
column[static_cast<std::size_t>(col)] = false;
diag1[static_cast<std::size_t>(d1)] = false;
diag2[static_cast<std::size_t>(d2)] = false;
}
}
};

int main() {
Solution sol;
const auto solutions = sol.solveNQueens(4);
for (const auto& board : solutions) {
for (const std::string& row : board) {
std::cout << row << '\n';
}
std::cout << "---\n";
}
return 0;
}

以n = 4为例，按标准语义推演，应当得到两组解：..Q./Q.../...Q/.Q..与.Q../...Q/Q.../..Q.。第一组的第一行皇后在第 2 列（0 起算），第二行只能在第 0 列，第三行第 3 列，第四行第 1 列。

result.push_back(board)必须拷贝。若写成result.push_back(std::move(board))，后续回溯会把棋盘改掉，已收集的解也被破坏，而且board被移走后无法继续搜索。

撤销顺序与设置顺序相反不是强制要求，但四个状态必须全部恢复：棋盘格、列、两条对角线。漏掉任何一个，后续分支都会带着错误状态继续，结果要么少解，要么产生非法解。

四、复杂度与变体

时间复杂度：搜索树的节点数上界是1 + n + n(n-1) + ...，粗略为O(n!)；每个节点做O(1)的冲突判断，每个解拷贝棋盘需要O(n^2)。空间复杂度：递归栈O(n)，三个布尔数组O(n)，结果集另计（每个解O(n^2)）。

52 题只要求返回解的个数，不需要收集棋盘，可以把result换成一个计数变量，省掉所有棋盘拷贝，速度会明显不同。但具体差多少取决于n和实现，不应给出未经测量的倍数。

如果只需要判断某个n是否有解，n = 1有解，n = 2、n = 3无解，n >= 4均有解，这是经典的结论。但 51 题要求列出全部解，不能只做存在性判断。

常见坑点

1. 主对角线下标为负

❌const int d2 = row - col;后直接diag2[d2]，row < col时越界。 ✅ 加偏移n - 1，索引范围变为0..2n-2。

2. 只检查列，不检查斜线

❌if (column[col]) continue;，两个皇后可能落在同一斜线。 ✅ 同时检查diag1[row + col]与diag2[row - col + n - 1]。

3. 递归返回后不撤销

❌ 标记后直接进入下一列，列/对角线一直为真。 ✅ 递归返回后恢复棋盘格与三个布尔值。

4. 收集结果时移动棋盘

❌result.push_back(std::move(board));，后续搜索无法继续。 ✅ 拷贝board，或每层用局部棋盘按值构造。

5. 忘记处理n = 1

❌ 循环或数组大小按n - 1计算，n = 1时得到 0。 ✅ 数组大小用2 * n - 1，n = 1时为 1；基准情形row == n正常收集。

6. 用std::vector<bool>的引用跨层保存

❌ 把column[col]的代理引用存起来，后续赋值作用到错误位置。 ✅ 只做布尔读写，不保存vector<bool>的引用或指针。

7. 认为每行可以不放皇后

❌ 在每行加一个「跳过」分支，生成少于n个皇后的非法解。 ✅ 每行必须放一个；若当前行无合法列，自然回溯到上一行。

8. 输出格式错误

❌ 用'#'或1/0表示皇后，或返回坐标列表。 ✅ 按题目要求返回vector<vector<string>>，每行由'Q'和'.'组成。

总结

N 皇后是回溯法的标准范例：选择空间是「当前行放哪一列」，约束是三个方向，撤销是恢复四个状态。把对角线下标的偏移写对，把收集时的拷贝与撤销写全，剩下的就是让递归自然展开。它也能很好地说明「剪枝不是可选项」——没有冲突判断，搜索空间会大到无法完成。