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