C++实现LeetCode(51.N皇后问题)

前言N 皇后问题要求在n × n的棋盘上放置n个皇后使得任意两个皇后都不在同一行、同一列或同一条斜线上返回所有不同的摆放方案。棋盘用字符串数组表示Q表示皇后.表示空位。最直观的想法是枚举所有格子「放或不放」但复杂度是2^(n^2)完全不可行。正确的建模是每一行恰好放一个皇后。因为共有n行、n个皇后且每行最多一个所以每行必须一个。这样搜索空间从「格子组合」降到「每行选一列」再配合列与斜线的冲突剪枝规模就可控了。常见的误解是只检查列、不检查斜线或者斜线下标算错导致负下标。还有人把「回溯」写成「递归后不撤销状态」结果第一个解之后所有分支都被污染。本文以 C17 为准用三个布尔数组分别记录列、主对角线、副对角线的占用情况逐行放置并收集棋盘。一、约束建模三个方向皇后放在(row, col)时会占用列col范围为0..n-1。主对角线方向左上到右下同一条线上的格子满足row - col相等。加上偏移n - 1后索引为row - col n - 1范围0..2n-2。副对角线方向右上到左下同一条线上的格子满足row col相等索引为row col范围0..2n-2。约束判定量索引范围数组大小列col0..n-1n主对角线row - col-(n-1)..n-12n-1加偏移副对角线row col0..2n-22n-1之所以能用一个一维数组表示一条对角线是因为同一条对角线上的所有格子其row - col或row col是同一个常数。只要该常数对应的布尔值为真整条线都被占用。主对角线索引必须加偏移n - 1否则row col时得到负数。用负数下标访问std::vectorbool会转换为巨大的无符号值属于越界访问是未定义行为undefined behavior, UB通常直接崩溃。二、逐行回溯搜索按行推进backtrack(row):如果 row n收集当前棋盘返回对 col 从 0 到 n-1如果 col、主对角线、副对角线任一被占用跳过在 (row, col) 放皇后标记三个方向backtrack(row 1)撤销标记恢复棋盘由于每行只放一个行冲突天然不存在不需要额外的行数组。递归深度为n每一层尝试n列最坏搜索树节点数为O(n!)量级实际节点数远小于这个上界因为冲突剪枝会砍掉大量分支。这里不给出具体运行时间具体规模取决于n和实现。三、完整实现// 适用于 C17#include iostream#include string#include vectorclass Solution {public:std::vectorstd::vectorstd::string solveNQueens(int n) {std::vectorstd::vectorstd::string result;if (n 0) return result;std::vectorstd::string board(static_caststd::size_t(n),std::string(static_caststd::size_t(n), .));std::vectorbool column(static_caststd::size_t(n), false);std::vectorbool diag1(static_caststd::size_t(2 * n - 1), false);std::vectorbool diag2(static_caststd::size_t(2 * n - 1), false);backtrack(0, n, board, column, diag1, diag2, result);return result;}private:void backtrack(int row, int n,std::vectorstd::string board,std::vectorbool column,std::vectorbool diag1,std::vectorbool diag2,std::vectorstd::vectorstd::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_caststd::size_t(col)] ||diag1[static_caststd::size_t(d1)] ||diag2[static_caststd::size_t(d2)]) {continue;}board[static_caststd::size_t(row)][static_caststd::size_t(col)] Q;column[static_caststd::size_t(col)] true;diag1[static_caststd::size_t(d1)] true;diag2[static_caststd::size_t(d2)] true;backtrack(row 1, n, board, column, diag1, diag2, result);board[static_caststd::size_t(row)][static_caststd::size_t(col)] .;column[static_caststd::size_t(col)] false;diag1[static_caststd::size_t(d1)] false;diag2[static_caststd::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 - 1n 1时为 1基准情形row n正常收集。6. 用std::vectorbool的引用跨层保存❌ 把column[col]的代理引用存起来后续赋值作用到错误位置。 ✅ 只做布尔读写不保存vectorbool的引用或指针。7. 认为每行可以不放皇后❌ 在每行加一个「跳过」分支生成少于n个皇后的非法解。 ✅ 每行必须放一个若当前行无合法列自然回溯到上一行。8. 输出格式错误❌ 用#或1/0表示皇后或返回坐标列表。 ✅ 按题目要求返回vectorvectorstring每行由Q和.组成。总结要点做法搜索单位一行一个皇后冲突判断列、rowcol、row-coln-1状态恢复棋盘 三个布尔数组收集时机row n时拷贝棋盘复杂度搜索树O(n!)量级解拷贝O(n^2)N 皇后是回溯法的标准范例选择空间是「当前行放哪一列」约束是三个方向撤销是恢复四个状态。把对角线下标的偏移写对把收集时的拷贝与撤销写全剩下的就是让递归自然展开。它也能很好地说明「剪枝不是可选项」——没有冲突判断搜索空间会大到无法完成。