第一次在USACO训练题库里刷到P1219 [USACO1.5] 八皇后 Checker Challenge的时候我还愣了一下——标题写的是 Checker Challenge翻了样例才发现这其实就是八皇后问题只不过棋盘不一定是 8×8。题目的棋盘大小 N 在 6 到 13 之间你要输出前三个合法摆放方案再统计总共有多少种方案。说实话八皇后几乎是每个算法竞赛选手的启蒙搜索题。我在学 DFS 的时候刷过它在准备省赛的时候优化过它后来写数独求解器时又用到了它的思想。USACO 这个版本的特殊之处在于它不满足于“随便输出一种方案”而是要求你输出所有解N 最大到 13。如果你只会最朴素的回溯不优化某些语言在极限数据下真的会卡到超时。这篇文章就从题目本身开始把模型建模、标准回溯、对称剪枝、位运算优化这些细节一次讲透也把我踩过的几个坑交代清楚。1. 为什么这道题叫“Checker Challenge”而不是“八皇后”1.1 题面其实是在讲 N 皇后不是写死 8 个皇后USACO 1.5 章节的这道题题面用的是国际象棋棋盘checkerboard来描述在一个 N×N 的棋盘上放置 N 个皇后使得任意两个皇后不能互相攻击。N 的范围是 6 到 13。“八皇后”只是大家叫顺口的名字真正要处理的是一族 N 皇后问题。我第一次做的时候差点吃了这个亏以为 N 固定是 8结果看样例发现 N6 的输出只有 4 个解跟八皇后 92 个解完全对不上。后来仔细读题才发现 N 是输入的变量。USACO 的老题有个特点题面叙述很简洁甚至有点绕但每一个字都有用。N between 6 and 13这句话意味着你要考虑 N6 这种小数据也要考虑 N13 这种中等数据。1.2 输出细节才是一道题的灵魂前三解加总数这道题的输出要求和课本上的练习题不太一样如果有解先输出前三个解按字典序排列每个解占一行如果解的总数不足三个就把所有解都输出最后单独输出一行表示解的总个数。每个解由 N 个数字组成第 i 个数字表示第 i 行的皇后放在第几列列号从 1 开始。比如 N6 的第一个解是2 4 6 1 3 5意思就是第一行皇后在第 2 列第二行在第 4 列第三行在第 6 列以此类推。这个“按字典序输出前三个”的要求看起来只是输出规范实际上直接影响了你的搜索顺序设计。常规的回溯按行从上往下、每一行按列从左往右枚举得到的解自然就是字典序的。但如果你为了提速加上某些剪枝或对称优化搜索顺序一变前三个解就可能不是真正的字典序前三个这个坑我放到后面专门讲。1.3 这道题在 USACO 训练体系里的定位USACO 的训练章节是循序渐进的1.5 这个章节主要围绕“搜索与回溯”展开。八皇后是这一章里最容易理解、也最能体现状态建模重要性的题目。同一个章节里后续还会出现排序相关的题目比如三值排序但搜索题的核心思想是通用的状态怎么表示、约束怎么判断、剪枝怎么设计。把这题吃透后面做数独、迷宫、全排列类问题都会轻松很多。2. 数学模型先行为什么每行放一个皇后就够了2.1 皇后的攻击范围与三类约束国际象棋里的皇后可以横着走、竖着走、斜着走且步数不限。也就是说棋盘上的任意两个皇后不能出现在同一行、同一列、同一条对角线否则就会互相攻击。初看这个问题你可能会想我要在二维棋盘上选 N 个格子暴力枚举的组合数大得离谱。但稍微一想就会发现一个关键简化棋盘有 N 行要放 N 个皇后皇后不能在同一行所以每一行必然恰好放一个皇后。于是问题从“在 N×N 个格子里选 N 个”变成“每一行选择一列”搜素深度就是 N 层每一层的选择数最多 N 个。这个降维思路是整个八皇后问题的基石。所有高效解法无论是标准回溯还是位运算都是建立在“按行搜索、逐行确定列位置”这个框架上的。2.2 两条对角线的编号公式与数组偏移行和列的冲突很容易处理用一个布尔数组标记哪些列已经被占用即可。真正容易搞错的是对角线。把棋盘上的格子用坐标(行, 列)表示下标从 0 开始。可以发现两条对角线方向分别对应两个不变量从左上到右下方向的“主对角线”同一对角线上的格子满足行 - 列为常数从右上到左下方向的“副对角线”同一对角线上的格子满足行 列为常数。所以判断一个位置(row, col)是否可用只需要查三个数组col[col] // 列是否被占用 diag1[row col] // 副对角线是否被占用 diag2[row - col n] // 主对角线是否被占用加 n 是为了把负数变成正数这里的diag2数组为什么要加偏移量因为row - col的范围是-(N-1)到N-1数组下标不能为负所以统一加上N让它变成1到2N-1的范围。很多人的第一版代码 WA 都是栽在这个偏移量上数组开小一档或者忘记加偏移运行到一半就崩了。2.3 状态压缩思维从二维棋盘到一维排列一旦确定了“每行放一个皇后”这个框架一个完整的解就可以表示成一个长度为 N 的排列ans[row] col表示第 row 行的皇后放在第 col 列。这种把二维选择压缩成一维排列的思路是很多棋盘类搜索题的通用套路。我在给初学者讲这道题的时候喜欢把皇后问题类比成“给 N 个行程安排座位”每个人必须坐在不同的排每排要选不同的列而且斜对角的人不能互相看见。当你把问题改写成“安排座位”搜索的时候就只关注每排选哪一列而不是整天盯着棋盘发呆。这个类比看似简单但对建立搜索题的状态意识很有帮助。3. 第一版 AC 代码标准回溯先把正确性拿下3.1 C 标准 DFS 完整实现不搞花哨优化先把一份能正确通过 N6 到 N13 的 C 回溯写出来。核心逻辑就是递归枚举每一行尝试所有可用列找到解就记录并继续回溯。#include bits/stdc.h using namespace std; int n, cnt; vectorint ans; bool col[20], diag1[40], diag2[40]; void dfs(int row) { if (row n) { cnt; if (cnt 3) { for (int i 0; i n; i) { if (i) cout ; cout ans[i] 1; } cout \n; } return; } for (int c 0; c n; c) { if (col[c] || diag1[row c] || diag2[row - c n]) continue; ans[row] c; col[c] diag1[row c] diag2[row - c n] true; dfs(row 1); col[c] diag1[row c] diag2[row - c n] false; } } int main() { cin n; ans.resize(n); dfs(0); cout cnt \n; return 0; }这份代码有几个细节值得说明。第一diag1和diag2数组的大小可以开成2 * n 5也就是 31 左右我习惯直接开到 40省得边界算错。第二cnt在本题最大也只有 73712N13用 int 完全够但如果你以后要扩展到 N18 以上建议直接开long long因为皇后问题的解数增长非常恐怖。第三输出时ans[i] 1是因为代码里列号从 0 开始题目要求从 1 开始。3.2 从 6 到 13解数和搜索规模的实测感受在本地跑一下这份朴素回溯你会发现小数据完全没压力但 N 到 12、13 时递归调用次数明显增加。下面我整理了 N 从 6 到 13 对应的解总数N解的总数备注64不足 3 个解按题意输出全部740输出前 3 个 40892经典八皇后答案9352解数开始增加1072411268012142001373712题目最大数据用这份朴素 DFS 跑 N13C 开启-O2优化后大约需要零点几秒能在时限内通过。但如果你用 Python 照搬同样的回溯逻辑N13 大概率会在 23 秒甚至更久在一些严格限时的 OJ 上就有超时风险。所以优化不是可选项而是给“慢语言”留的救命稻草。3.3 常见 WA 原因数组开小、偏移忘记、输出格式我见过不少人在这道题上反复提交 WA整理一下高频错误数组开小。diag1[row col]的最大下标是(N-1)(N-1)2N-2有些人只开了N或2N访问越界后行为不可预测。忘记diag2偏移。row - col可能为负数不加N直接当下标用轻则越界重则程序崩溃。输出行号和解的列号混淆。题目要求第 i 行皇后的列号不是第 i 列皇后的行号。ans[row]表示行 row 对应的列输出ans[i]1方向反了样例就对不上。行尾空格问题。USACO 老版本对行尾空格通常不敏感但为了保险我习惯用if (i) cout ;这种方式只在数字之间加空格。先把正确性搞扎实再谈速度这是做搜索题的铁律。下面的优化都是在“已有一份正确回溯”基础上的增量改进。4. 提速三板斧对称剪枝、位运算、提前终止4.1 为什么棋盘左右对称可以省一半搜索棋盘是左右对称的。如果有一个解 S它的第一行皇后在第 c 列那么把整个棋盘镜像翻转就会得到另一个以第N-1-c列为第一行的合法解。这两个解互为镜像解的个数一定成对出现。利用这个性质我们可以只搜索第一行皇后位于左半边的解然后根据对称性推算出另一半解的数量搜索量直接减半。但对本题来说直接只搜左半边有一个隐患题目要求输出字典序前三个解而字典序最小的解不一定全部落在左半边N 较小的时候尤其明显。以 N6 为例总解数只有 4 个左半边解只有 2 个。只搜左半边的话顶多输出 2 个解凑不齐题目要求的前 3 个必须继续搜右半边才能补足。所以对称剪枝虽好在这个题目上不能无脑套。4.2 对称剪枝在本题的隐藏坑输出顺序和计数规则一个相对稳妥的对称剪枝写法是第一行仍然从第 0 列到第 N-1 列依次枚举但用一个skip[]数组记录哪些第一列已经被镜像覆盖掉。搜完第 c 列的解后把第N-1-c列标记为跳过。这样搜索顺序仍然保持字典序只是跳过了那些可以由镜像推导出来的第一列位置。bool skip[20]; void dfs(int row) { if (row n) { cnt; if (cnt 3) { for (int i 0; i n; i) { if (i) cout ; cout ans[i] 1; } cout \n; } return; } for (int c 0; c n; c) { if (row 0 skip[c]) continue; if (col[c] || diag1[row c] || diag2[row - c n]) continue; if (row 0) skip[n - 1 - c] true; ans[row] c; col[c] diag1[row c] diag2[row - c n] true; dfs(row 1); col[c] diag1[row c] diag2[row - c n] false; } }但请注意这段代码统计出来的cnt并不是完整解数而是“第一列位于左半边”的解数。因为每出现一个第一列属于左半边的解一定存在一个第一列属于右半边的镜像解所以最终计数需要额外处理偶数 N 时直接cnt * 2奇数 N 时还要减去第一列恰好为中轴线的解数避免把它的“自我镜像”重复计算进去。这也是我做这道题时印象最深的一个坑优化看似简单但边界条件一变输出和计数都跟着变。如果你只想拿满分不打算折腾这些我建议输出阶段老老实实不剪枝只在统计总数时临时启用对称剪枝或者干脆用下面的位运算优化速度已经完全够用。4.3 位运算 DFS三个整数替代三个数组位运算是解决 N 皇后问题的终极提速手段。核心思想是用整数的二进制位来表示占用状态某个位是 1 表示对应的列或对角线已被占用。col记录哪些列被占用ld记录左对角线左上到右下方向的占用情况rd记录右对角线右上到左下方向的占用情况。每次枚举可用列时计算available full ~(col | ld | rd)其中full的低 N 位全是 1用来截断超出棋盘范围的位。然后取最低位的 1递归传入更新后的状态。void dfs(int row, int col, int ld, int rd) { if (row n) { cnt; if (cnt 3) { for (int i 0; i n; i) { if (i) cout ; cout ans[i] 1; } cout \n; } return; } int available full ~(col | ld | rd); while (available) { int bit available -available; // 取出最低位的 1 available - bit; int c __builtin_ctz(bit); // 得到列号 ans[row] c; dfs(row 1, col | bit, (ld | bit) 1, (rd | bit) 1); } }递归参数里(ld | bit) 1和(rd | bit) 1的移动方向一开始很容易搞反。我建议用一个具体例子验证第一行皇后在第 0 列它在左上到右下方向的对角线上下一行它会攻击到第 1 列所以这个方向要左移一位而在右上到左下方向下一行它影响的位置是“列号减 1”所以要右移一位。位运算版本在 N13 时速度非常快即使不用对称剪枝C 也是瞬间完成Python 配合位运算也能把耗时压到 1 秒以内。它的意义在于把三个“数组查询加赋值”变成几个整数位操作同时在枚举可用列时跳过大量无效尝试搜索效率提升很明显。5. 这道题留给我的经验5.1 “先跑对再跑快”的顺序为什么在这里尤其适用我见过不少同学一上来就直接写位运算结果代码又长又难调出了问题不知道是状态转移写错还是输出格式写错。我的习惯是先写最朴素、最不容易出错的回溯版本确保小数据全部正确然后再逐步加入优化。每一轮优化后都重新跑一遍 N6 到 N13 的完整数据确认输出和解数没有变化。搜索题的优化很容易引入隐匿 bug回归测试是最便宜的安全网。5.2 用八皇后思想解决其他搜索问题八皇后模型可以推广到很多地方。数独求解器本质上就是“每一行选数字、检查列和小宫格冲突”和皇后问题的约束判断是同构的图的 m-着色问题也是类似的“逐点尝试、回溯撤销”流程全排列生成更是八皇后的退化版本去掉对角线约束即可。掌握了“状态建模 约束判定 回溯撤销”这个组合你在面对其他搜索题时会自然形成套路。5.3 你真正应该从 USACO 1.5 里带走的习惯USACO 老题对输入输出格式要求严格这逼着你养成读题仔细、输出规范的习惯。我当时做完这道题后给自己定了一个规矩不管什么 OJ 题先看输出样例再反向确认自己的输出格式涉及多解输出的题先想清楚字典序的搜索顺序再动手写代码。这个习惯后来帮我避开了很多“思路全对、格式 WA”的尴尬局面。八皇后这道题算法本身不难难的是把每一步的为什么想透。你可以在网上找到现成的位运算模板但我还是建议你自己从朴素回溯开始亲手推到 N13再尝试加剪枝、加位运算。只有自己踩过“数组越界”“偏移量忘加”“输出顺序不对”这些坑这些优化对你来说才是活的而不是死记硬背的模板。