1. 从8皇后到N皇后一个困扰了数学家170年的谜题先问一个问题在8×8的国际象棋棋盘上放置8个皇后让它们彼此之间不能互相攻击总共有多少种摆法这个问题最早可以追溯到1848年德国国际象棋杂志上一位叫Max Bezzel的棋手发表了这个问题之后陆续有数学家给出了92种不同的解。但真正的转折点出现在1850年伟大的数学家高斯在研究这个问题时最初他认为有96种解法实际上是92种——这位数学王子也算错了由此可见这个题目在直觉上有多反人类。到了现代这个问题被推广成N皇后问题在N×N的棋盘上放置N个皇后任意两个皇后不能处于同一行、同一列或同一条对角线上问有多少种放置方法或者具体如何放置。你可能会说这不就是经典的八皇后吗面试题而已。但N皇后问题远不止面试题这么简单。它背后承载的是图论、约束满足问题CSP、搜索算法、并行计算等一堆计算机科学的核心思想。从N1到N27每一种规模背后都有不同的优化策略和math故事可以讲。在数据结构和算法的学习路径上N皇后几乎是回溯算法的标准教材案例是许多人第一次接触递归回退这个概念的地方。这篇文章我会从实际问题出发把N皇后问题彻底讲透从暴力枚举到经典回溯从位运算优化到对称性剪枝再到它在真实业务中的映射——你会发现很多看似与棋盘无关的工程问题本质上就是N皇后问题的变体。2. 为什么暴力解法走不通先算一笔穷举的账2.1 暴力枚举的第一直觉如果让你不用任何算法、直接硬算8皇后第一个直觉可能是什么既然要求任意两个皇后不在同一行那干脆从8行里每行放一个皇后然后检查列和对角线是否冲突。这样总状态数是多少每一行有8个位置可选8行就是8^8 16,777,216约1677万个组合。看起来不算太夸张但你需要对每个组合检查C(8,2)28对皇后之间是否冲突总的计算量大约在4.7亿次现代计算机跑下来也就几秒。但问题在于当你把N从8扩大到1515^15 4.37×10^17这就完全不是几秒级别了。再扩大到3030^30根本不是普通机器能算完的量级。所以暴力解法只适合N≤8稍微大一点的N直接让计算复杂度爆炸。2.2 关键洞察从排列到全排列的降维既然每行放一个皇后其实每一行选择的列号不能重复——因为任意两个皇后不能在同一列。所以N皇后问题的解本质上就是0到N-1的一个全排列每一列的数字表示第row行的皇后放在哪一列。于是问题规模从N^N降到了N!。但是N!也不够看。8! 40320检查排列是否合法只需要O(N)时间8皇后瞬间解决。可是15! 1.3×10^12无论如何也撑不住。N20时20!约等于2.4×10^18这已经是天文数字了。2.3 核心矛盾在于提前判断与事后检查暴力解法最大的浪费在于你先把整个排列生成完再逐对检查冲突。就好比装修房子你把每一面墙都刷完颜色之后才发现客厅和厨房颜色严重不搭只能砸掉重来。有多少排列在前面几步就已经冲突了后面全部白算回溯算法的精髓在于边放边检查一旦发现当前行的某个位置和之前所有皇后冲突立刻放弃这个位置回到上一行重新选择——这就是剪枝。3. 回溯法的完整拆解一行一行试出所有解3.1 回溯的数学结构一棵N叉树回溯法对应的是一棵深度为N的N叉树。从根节点出发第1层是第0行皇后放在哪一列N种选择第2层是第1行皇后放在哪一列理论上N种选择但排除冲突以此类推。整棵树的叶子节点理论上共N^N个回溯的作用就是在遍历这棵树的过程中一旦发现某个节点已经不满足约束就不再进入它的子树。用业内的话说这叫剪枝。3.2 冲突检测的三种方式在实现回溯时最核心的是判断当前位置是否合法。判断标准有三条不能和之前某一行的皇后在同一列即列号不能重复。不能和之前某一行的皇后在同一撇对角线左上到右下此时行列差是一个常数。不能和之前某一行的皇后在同一捺对角线左下到右上此时行列和是一个常数。这里的关键技巧是用三个布尔数组来分别标记列是否被占用、撇对角线是否被占用、捺对角线是否被占用。列数组col[j] True表示第j列已有皇后。撇对角线diag1[i j]表示从左上到右下方向的对角线。同一撇对角线上的格子满足 i j 为常数。捺对角线diag2[i - j N - 1]表示从左下到右上方向的对角线。同一捺对角线上的格子满足 i - j 为常数加上 N-1 是为了让下标不为负。这三条判断的时间复杂度都是O(1)比每次遍历之前所有皇后判断快得多。3.3 经典回溯代码Python版def solveNQueens(n): result [] board [[.] * n for _ in range(n)] col [False] * n diag1 [False] * (2 * n - 1) # i j 范围 0 ~ 2n-2 diag2 [False] * (2 * n - 1) # i - j n - 1 范围 0 ~ 2n-2 def dfs(row): if row n: result.append([.join(r) for r in board]) return for c in range(n): d1 row c d2 row - c n - 1 if col[c] or diag1[d1] or diag2[d2]: continue board[row][c] Q col[c] diag1[d1] diag2[d2] True dfs(row 1) board[row][c] . col[c] diag1[d1] diag2[d2] False dfs(0) return result这段代码的核心逻辑就两件事尝试放皇后、发现冲突立刻撤回回溯。dfs(row)代表当前正在放置第 row 行的皇后当 row n 时说明所有行都放完了记录一个解。3.4 为什么说回溯是DFS加剪枝你如果看过《算法导论》或《算法竞赛入门经典》会发现回溯其实就是深度优先搜索DFS在约束满足问题上的特化。DFS负责遍历整棵状态树剪枝负责把所有注定失败的子树提前砍掉。两者缺一不可。在N皇后问题里剪枝的时机非常关键。很多初学者的误区是在递归到 row 这一层时去检查从第0行到第row-1行之间所有皇后对是否冲突这是O(N)的检查。而正确的做法是在放置第row行皇后时用O(1)时间去查三个标记数组。这个差别在N15以上会体现为数量级的性能差距。3.5 一个容易踩的坑对角线的编号范围很多人在写diag1和diag2的数组大小时会出错。我们仔细算一下i j的最小值是 000最大值是 (n-1)(n-1)2n-2所以共 2n-1 个值。i - j n - 1的最小值是 0-(n-1)(n-1)0最大值是 (n-1)-0(n-1)2n-2也是 2n-1 个值。所以两个对角线数组的长度都应该是2*n - 1。如果你只分配成 n 长度那就越界或者漏判了。这是我见过最多人踩的坑没有之一。4. 从正确到高效位运算、对称剪枝与性能进阶4.1 位运算优化用三个整数的二进制位代替三个布尔数组当N比较大时布尔数组的读写开销虽然不大但依然存在。更极致的做法是用整数的二进制位来标记冲突——这是竞赛选手最常用的写法。核心思路col的二进制表示中第 k 位为1表示第k列已有皇后。ld表示撇对角线方向左上到右下已被占用的位置它会在下一行向左移动一位。rd表示捺对角线方向右上到左下已被占用的位置它会在下一行向右移动一位。仔细想一下这个移位逻辑当你在第 row 行的第 col 列放了一个皇后后下一行中撇对角线碰撞的位置是 (row1, col-1)也就是列号向左偏移一位所以 ld 左移一位捺对角线碰撞的位置是 (row1, col1)列号向右偏移一位所以 rd 右移一位。代码非常精简class Solution { public: int totalNQueens(int n) { this-n n; dfs(0, 0, 0, 0); return count; } private: int n, count 0; void dfs(int row, int col, int ld, int rd) { if (row n) { count; return; } // 所有可用位置就是 ((1n)-1) 与上三个冲突标记取反 int pos ((1 n) - 1) ~(col | ld | rd); while (pos) { int p pos (-pos); // 取出最低位的1即当前能放置的最右列 pos - p; // 清除该位 dfs(row 1, col | p, (ld | p) 1, (rd | p) 1); } } };这段代码为什么快因为整个搜索过程中没有数组访问的寻址开销全部是CPU整数运算。pos (-pos)是经典的低位取位操作你可以在很多位运算相关的算法题中看到它的影子。实测下来对N16位运算版本比布尔数组版本快5~8倍N越大差距越明显。4.2 对称性剪枝把搜索空间砍到1/8N皇后问题有一个很重要的性质如果直接把棋盘旋转90度、180度、270度或者做水平/垂直翻转解仍然是合法解。所以我们可以利用这种对称性来减少搜索量。但注意不是所有解都是非对称的。有些解本身就是对称的翻转后和原解相同。所以要想精确计算唯一解的个数单纯除以8是不行的需要对每个解判重或者进行等价类划分。不过对于求所有解的场景我们可以做一个简单而有效的优化当N是奇数时只搜索第0行前一半的列位置再特殊处理中间列。这样能砍掉接近一半的搜索时间。哦对了更准确地说由于棋盘旋转180度后第0行的皇后在列c的位置会映射到第N-1行的N-1-c列所以我们可以只搜索第0行列号 ≤ N/2 的情况来减少重复解的生成。但如果你只关心最终解的数量而不是所有具体的摆法这个优化并不会改变最终答案因为两种搜索得到的总解数是相同的只是重复计算被避免了一半左右。4.3 不同N规模下的实测表现我在一台普通的MacBook ProM2芯片上跑了几个不同N的值用位运算版本计算总解数结果如下N解的数量位运算版本耗时约892约 1ms10724约 3ms1214200约 50ms14365596约 1s152279184约 5s1614772512约 25s可以看到N每增加1耗时大约增长3~5倍。到了N16之后普通回溯算法已经非常吃力。如果要冲击N20以上就需要并行化——开多线程分别从不同的初始列开始搜索或者用GPU并行遍历搜索树。4.4 已知的N皇后解数速查表如果你想验证自己的算法是否正确可以参考下面这个前几个N的解数包括所有非重复解的总数N1: 1N2: 0N3: 0N4: 2N5: 10N6: 4N7: 40N8: 92N9: 352N10: 724N11: 2680N12: 14200N13: 73712N14: 365596注意N6的解数比N5还少这个反直觉的现象很正常——棋盘变大并不意味着约束变松因为皇后的个数也变多了。5. 从回溯到通用搜索算法N皇后教会我们的设计模式5.1 回溯的本质是增量式试探加冲突撤销把N皇后问题抽象到更通用的层面它解决的是这样一类问题在一个状态空间中按照一定的顺序逐步决策每一步做选择时都要满足一组约束如果后续发现走不通就撤销当前选择并尝试其他选项。这个模式在工程上太常见了。举几个例子排课表问题每门课要安排到某个时间教室教师和教室都是稀缺资源任意两门课不能冲突。旅行商问题TSP的暴力分支从一个城市出发逐次选择下一个城市直到遍历完所有城市再返回起点。正则表达式引擎的回溯当正则表达式匹配失败时引擎会回溯到上一个可选的分支重新匹配。电脑下棋的博弈搜索Alpha-beta剪枝本质上就是回溯 评估函数 剪枝的组合。你会发现一旦你彻底理解了N皇后中的回溯结构理解这些问题的难度会大幅下降。5.2 一个工程化的思路从N皇后到约束满足问题(CSP)框架如果你去大学里学人工智能课程第一章讲搜索时一定会提到把N皇后建模为约束满足问题变量每个皇后所在行的列号即Q_0, Q_1, ..., Q_{N-1}值域每个变量的值域为{0, 1, ..., N-1}约束Q_i ! Q_j任意两列不同Q_i i ! Q_j j撇对角线不冲突Q_i - i ! Q_j - j捺对角线不冲突一旦建模为CSP你就可以套用通用求解器比如Google OR-Tools、python的python-constraint库来求解而不需要自己写回溯。现实中很多调度、排程、分配类问题都能用这个框架描述。from constraint import Problem def solve_nqueens(n): problem Problem() queens range(n) problem.addVariables(queens, queens) for q1 in queens: for q2 in range(q11, n): problem.addConstraint( lambda q1, q2: q1 ! q2 and abs(q1 - q2) ! abs(q1 - q2), (q1, q2) ) # 注意这里的约束写法仅示意实际需要对索引和值分别处理这种做法的好处是你不需要手写递归把注意力集中在约束定义上。缺点是灵活性不如手写回溯剪枝策略不好定制。但两者解决问题的视角是完全一致的。5.3 为什么说N皇后是图论问题的特例如果你把棋盘的每个格子看作图的节点把可以被同一皇后攻击的格子之间连一条边那么N皇后问题就转化为在这个图中找一个大小为N的独立集。所以N皇后问题本质上是最大独立集问题在一个特殊图上的变体。这正是算法学习中很奇妙的地方一个看似只是在摆棋子的题目背后连接着图论中的经典难题。知道了这一点你对它的理解会完全不一样——你不是在单纯解一个回溯题目而是在研究一个NP-hard问题当N是输入时N皇后问题本身有组合爆炸的性质在特定约束下的解法。6. 我的N皇后调试笔记几个容易让人卡住的细节6.1 边界条件的重灾区i - j 出现负数如果不用i - j n - 1直接当索引第一次运行就会报IndexError。这种错误很好排查报错信息会直接提示下标越界。但更隐蔽的问题是当你用的是C的vectorbool下标访问越界时并不会抛出异常而是产生未定义行为——程序运行结果看起来正常但答案偶尔出现莫名其妙的多解或少解。所以建议优先用Python把逻辑跑通再用C重写。6.2 集合 vs 布尔数组回溯时需要正确撤销有人喜欢用set来存储已占用的列和对角线好处是代码可读性高但需要记得remove。如果忘记撤销会残留之前状态导致漏解。我见过好几个同学的代码问题都出在尝试之后没有撤销。记住回溯的回字就体现在这里——状态变更是可逆的递归返回后必须恢复到进入之前的状态。6.3 位运算版本容易犯的错忘记限定n位有效范围在位运算版本中~(col | ld | rd)会把最高位之外的所有位都变成1所以必须与上((1 n) - 1)来只保留低n位。漏掉这一步程序会尝试放置超出n列的位置结果必然错乱。这个bug极其隐蔽因为C溢出不报错只有当你打印输出中间状态时才可能发现。6.4 对称剪枝的一个大坑剪掉的是解不是时间有些文章为了追求速度在for循环里只遍历range(n//2)以为这样利用对称性减少一半搜索但忽略了一个问题棋盘上存在自对称的解这部分解在range(n//2)中的某一侧根本不会被搜索到导致最终解数变少。如果只求 能否放置比如判断N皇后是否有解这种剪枝没问题但如果要求输出所有解就必须谨慎判断对称映射关系并在搜索结束后做去重。我给一个实用建议先用不带对称剪枝的版本验证解数正确再逐步加优化。这样即使优化出错你也知道问题肯定出在优化逻辑里。6.5 性能实测的另一个小技巧只计数 vs 打印全部棋盘打印所有解会带来巨大的I/O开销。实测中N12 的 14200 个解如果全部格式化打印到终端耗时可能从几十毫秒飙升到好几秒。所以如果你想测试算法本身的性能建议只统计解的数量或者把解压缩成整数序列再输出。7. 从竞赛到工作流N皇后算法的实用工具箱如果你是在准备算法竞赛或面试我建议你在本地搭一个顺手的工作流。这里分享一个我的常用模板用Python快速验证正确性用C位运算版跑性能上限用Python的unittest做回归测试。import unittest class TestNQueens(unittest.TestCase): def test_known_counts(self): self.assertEqual(len(solveNQueens(4)), 2) self.assertEqual(len(solveNQueens(8)), 92) self.assertEqual(len(solveNQueens(9)), 352) self.assertEqual(len(solveNQueens(10)), 724) if __name__ __main__: unittest.main()这样每次改动算法跑一遍测试就知道有没有破坏已知结果比肉眼查代码靠谱得多。另外如果你需要画图来看不同N下的棋盘布局可以用Python的matplotlib画一个简单的棋盘并标出皇后。视觉化输出对理解冲突和对角线的含义特别有帮助尤其是你自己亲手实现一遍之后再回头看棋盘上的格子会觉得之前抽象难懂的ij和i-j一下子变得那么自然。. . Q . Q . . . . . . Q . Q . .上面这个8皇后布局用二维数组表示看起来很直观。这也是我在调试时最常用的方式先把 N 设小一点比如N4验证布局符合直觉再逐步扩大N。8. 我的一点实际体会N皇后问题在我刷过的算法题中属于越写越有味道的那一类。最初写回溯版的时候我总是在想这玩意儿除了应付面试还有什么用直到后来做排课系统才意识到回溯、剪枝、CSP建模这些思想在真实业务里几乎是信手拈来。你不需要真的去写一个摆皇后的程序但你需要这种尝试-冲突-回退的思维方式。如果你现在已经能独立写出回溯版本并且跑挂了N14都不出错那恭喜你你已经掌握了回溯算法最核心的骨架。接下来想挑战自己可以尝试不用递归用显式栈模拟回溯过程。把回溯改成随机重启爬山看能否快速找到一个可行解而不是所有解。用多线程或GPU并行求N20以上的解数。最后分享一个小技巧如果你被 N 皇后问题里的对角线下标搞得头晕可以在草稿纸上画一个4×4的棋盘把每个格子的ij和i-j都标出来标完之后你就理解了为什么diag1和diag2的长度是2N-1也永远不会再搞混下标计算。这个办法我后来讲给很多学生都说一张纸胜过看十遍代码。算法这东西纸上得来终觉浅你亲手把N皇后的92种摆法跑出来那一刻比任何书里的回溯法定义都更让你理解它到底是什么。