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.5
Tip
📌 题目分析
给定数据：
经典八皇后问题的扩展。要求在棋盘上放置 N 个皇后，使得她们互不攻击（不在同一行、同一列、同一对角线上）。
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 为什么使用回溯法
每一行必定只有一个皇后。我们可以逐行放置皇后，即：
到了第 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\) 的数据范围下，优化后的回溯算法只需要几毫秒就能跑完。
Danger
我强调一点：
这题需要观察出同一斜对角的行列和相同；
and同一正对角线的行列差的绝对值相同。
💻 C++代码
#include <iostream>
using namespace std;
int n;
int total = 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++; // 找到一个解
// 题目要求只输出前 3 个解
if (total <= 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 << "\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 皇后题目（如 \(N \le 15\)）中，会用到位运算来替代数组判定。用 int 变量的二进制位来表示列和对角线的占用情况，速度可以飙升十几倍。不过对于本题 \(N \le 13\) 的数据，老老实实用布尔数组是完全足够且最稳的！