P1219 [USACO1.5] 八皇后 Checker Challenge
题目描述
一个如下的 \(6 \times 6\) 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列 \(2\ 4\ 6\ 1\ 3\ 5\) 来描述，第 \(i\) 个数字表示在第 \(i\) 行的相应位置有一个棋子，如下：
行号 \(1\ 2\ 3\ 4\ 5\ 6\)
列号 \(2\ 4\ 6\ 1\ 3\ 5\)
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 \(3\) 个解。最后一行是解的总个数。
输入格式
一行一个正整数 \(n\)，表示棋盘是 \(n \times n\) 大小的。
输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
【数据范围】
对于 \(100\%\) 的数据，\(6 \le n \le 13\)。
题目翻译来自NOCOW。
USACO Training Section 1.5s
Tip
📌 题目分析
给定数据：
要求在棋盘上放置 \(n\) 个皇后，使得她们互不攻击（不在同一行、同一列、同一对角线上）。输出前 3 个字典序解，以及总解数。
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 为什么使用回溯法
在 \(N \times N\) 的棋盘上放 \(N\) 个皇后，意味着每一行必定只有一个皇后。
我们可以逐行放置皇后：
到了第 row 行，我们尝试把皇后放在第 1 到 \(N\) 列。
如果某个位置不和前面的皇后冲突，就放下去，然后继续去搜第 row + 1 行。
如果走进了死胡同（某一行怎么放都冲突），就退回上一行，换个位置继续试。这就是典型的回溯（退一步海阔天空）。
2️⃣ 核心技巧：如何高效判断对角线冲突
如果用循环去检查前面所有的皇后是否冲突，每次都要遍历，效率太低。
我们可以开三个布尔数组，记录列、主对角线、副对角线是否被占用。
在网格坐标系中，对角线有极其优美的数学规律：
* 同一列：列坐标 col 相同。
* 副对角线（右上到左下 /）：横纵坐标之和恒定，即 row + col 的值是一样的。
* 主对角线（左上到右下 \）：横纵坐标之差恒定，即 row - col 的值是一样的。为了防止数组下标出现负数，我们统一加上 \(N\)，变成 row - col + n。
通过这三个规律，我们可以用 \(O(1)\) 的时间瞬间判断出当前位置能不能放。
3️⃣ 如何保证字典序输出
字典序其实就是优先小的数字排在前面。
在 DFS 的过程中，我们从第 1 列到第 \(N\) 列使用 for 循环按顺序枚举。
这样搜索树最先触达的底层叶子节点（即最先找齐的完整解），天然就是字典序最小的解，不需要把所有答案存下来再去排序。
4️⃣ 时间复杂度
最坏情况下是排列数级别：
但由于我们在搜索时加上了严格的冲突限制（也就是剪枝），实际上绝大多数分支在半路就被砍掉了。在 \(n \le 13\) 的数据范围下，优化后的回溯算法只需要几毫秒就能跑完。
💻 C++代码
#include <iostream>
using namespace std;
int n;
int total_solutions = 0; // 记录解的总数
int path[20]; // path[i] 表示第 i 行皇后所在的列数
bool col[20]; // 标记某列是否已有皇后
bool diag1[40]; // 标记副对角线 (row + col) 是否已有皇后
bool diag2[40]; // 标记主对角线 (row - col + n) 是否已有皇后
void dfs(int row) {
// 边界条件：如果已经成功放完了第 n 行（准备放第 n+1 行时）
if (row > n) {
total_solutions++; // 找到一个解
// 题目要求只输出前 3 个解
if (total_solutions <= 3) {
for (int i = 1; i <= n; i++) {
cout << path[i] << " ";
}
cout << "\n";
}
return;
}
// 尝试在当前行 row 的第 i 列放置皇后
for (int i = 1; i <= n; i++) {
// 检查该列、两条对角线是否安全
if (!col[i] && !diag1[row + i] && !diag2[row - i + n]) {
// 记录路径
path[row] = i;
// 占位标记（保护现场）
col[i] = true;
diag1[row + i] = true;
diag2[row - i + n] = true;
// 递归进入下一行
dfs(row + 1);
// 回溯（恢复现场）：把刚刚放的皇后拿走，尝试下一列
col[i] = false;
diag1[row + i] = false;
diag2[row - i + n] = false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
// 从第 1 行开始搜索
dfs(1);
// 最后输出解的总数
cout << total_solutions << "\n";
return 0;
}
⚠️ 易错点
❌ 1. 对角线数组开得太小导致越界
行和列的最大值是 13，但对角线的公式是 row + col 和 row - col + n。
它们的最大值会达到 \(2 \times N\)，也就是将近 30。
如果对角线的判定数组 diag1 和 diag2 只开 20 的大小，会导致数组越界崩溃（RE）。建议开到 40 确保绝对安全。
❌ 2. 忘记恢复现场（回溯）
这是回溯法最致命的错误：
如果你进入递归后，退出来时不把标记重新变回 false，后面的搜索就会以为这列还被占着，导致什么也搜不到，最后输出全为 0。
❌ 3. 主对角线的偏移量
row - col 是有可能产生负数的，比如在第 1 行第 13 列，1 - 13 = -12。
C++ 数组下标不能为负数，必须统一加上一个常数（这里用了 n），写成 row - col + n 把它平移到正数区间。
🚀 一句话总结
🔥 补充
硬核知识点：N皇后的极限优化 —— 位运算（Bitmask）
这道题的数据范围是 \(n \le 13\)，普通的布尔数组完全够用。但如果在进阶比赛中，数据范围拉高到了 \(n \le 15\) 甚至 \(n \le 16\) 时，布尔数组的读写和 for 循环就会显得太慢而导致 TLE（超时）。
这时候，竞赛大佬们会祭出位运算优化：
用三个整型变量（int）的二进制位来代替布尔数组。
* column：记录哪些列有皇后（二进制位为 1 表示有）。
* diag1：记录左下对角线的占用情况。
* diag2：记录右下对角线的占用情况。
最惊艳的位运算魔法： 在寻找当前行有哪些列可以放皇后时，只需一行代码：
这行代码利用按位取反~ 和按位与 &，瞬间计算出当前行所有可以放置皇后的安全位置（用 1 表示），然后配合 x & -x（提取最低位的 1）来快速跳过那些不能放的位置，彻底干掉了内层的 for 循环。
位运算版本的 N 皇后，速度可以比普通数组版快上 10 到 20 倍！虽然本题不需要这么极致的优化，但这绝对是算法进阶路上必须要领略的暴力美学。