结论：backtrack函数每层只尝试当前行的一个合法列位置，用三个布尔数组（cols、diag1、diag2）O(1)判断列、主对角线（row−col+n−1）、副对角线（row+col）是否被占用，避免O(N)遍历检查导致整体退化。

回溯法解N皇后：核心是递归+剪枝，不是暴力试错

直接说结论：backtrack 函数每层只尝试当前行的一个合法列位置，用三个布尔数组（或 std::set）快速判断列、主对角线（row−col 不变）、副对角线（row+col 不变）是否已被占用。关键不在“写递归”，而在“怎么高效判断冲突”。

常见错误是把 isSafe 写成遍历已放置的皇后逐个比对——O(N) 判断导致整体退化到 O(N!)×O(N)，N=12 就明显卡顿。正确做法是预维护三组状态，判断降为 O(1)。

列和两个对角线的冲突标记怎么选数据结构？

推荐用三个 std::vector<bool></bool>，而非 std::set 或 map：

• cols[col]：大小为 n，索引即列号
• diag1[row - col + n - 1]：主对角线（左上→右下），row−col 范围是 [−(n−1), n−1]，加 n−1 映射到 [0, 2n−2]
• diag2[row + col]：副对角线（右上→左下），范围是 [0, 2n−2]，无需偏移

用 vector 是因为访问快、内存紧凑；用 set 会引入 log N 开销，且无必要——对角线索引可完全离散化。

立即学习“C++免费学习笔记（深入）”；

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

回溯函数的参数设计和终止条件怎么定？

backtrack(row) 是最简洁接口：参数只传当前处理的行号，不用传棋盘二维数组（结果可存在全局 solutions 中，路径用一维 positions 记录每行的列位置）。

终止条件就是 row == n，此时把 positions 转成一种输出格式（比如 vector）存入结果。注意不要在递归入口就 push，而应在确认完成时才保存——否则会多存中间状态。

递归体里用 for 循环枚举当前行所有列，对每个 col 检查：!cols[col] && !diag1[row-col+n-1] && !diag2[row+col]，满足才进入下一层。

为什么 N=14 时结果数量暴涨但运行不慢？

因为剪枝足够早：只要某行找不到合法列，立刻回退，不会继续向下递归。实际搜索树远小于满 N 叉树。但要注意：若用 string 拼接每行棋盘（如 "....Q..."）作为状态传递，会产生大量临时对象拷贝；应避免在递归参数中传 vector，改用一维 vector<int></int> 存列号，最后统一生成输出。

真正容易被忽略的是 diag1 数组大小——写成 2 * n 会越界（最大索引是 2*n-2），必须分配 2 * n - 1 个元素。