[USACO1.5] 八皇后 Checker Challenge

形式化题目

有一个 $n \times n$ 的棋盘，要求放入 $n$ 个皇后，使得任意两个皇后都不互相攻击：每行、每列恰好一个皇后，任意两个皇后不在同一条对角线（含两条主对角线方向的所有平行线）上。

一个方案用长度为 $n$ 的序列表示，第 $i$ 个数是第 $i$ 行皇后所在的列号。要求按字典序从小到大输出前 $3$ 个合法方案，最后一行输出合法方案总数。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-13 13:19
 * update_at: 2026-08-13 13:19
 */
// brute.cpp：小数据暴力解，把每一行选择的列号看成选择序列，先完整枚举再检查合法性。
// 与 main.cpp 的"边放边剪枝"形成对比，只适合 n <= 10 左右的小数据对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n;
int choose[MAXN];   // choose[i]：第 i 行皇后选择的列号（完整的选择序列）
int used_col[MAXN]; // 枚举时保证列号互不重复，形成 n 个列的排列
long long total_ans;
int printed_cnt;

// 检查当前完整选择序列是否合法：任意两行不能在同一条对角线上。
// 列号由 used_col 保证了互不重复，这里只需检查对角线冲突。
bool check() {
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (abs(i - j) == abs(choose[i] - choose[j])) {
                return false; // 行差等于列差，说明两点在同一条对角线上
            }
        }
    }
    return true;
}

void print_solution() {
    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << choose[i];
    }
    cout << '\n';
}

// 生成完整选择序列：第 dep 层决定第 dep 行皇后放在哪一列。
// 叶子节点（dep == n + 1）才统一检查合法性并统计答案。
void dfs(int dep) {
    if (dep == n + 1) {
        if (check()) {
            total_ans++;
            if (printed_cnt < 3) {
                print_solution();
                printed_cnt++;
            }
        }
        return;
    }

    // 这一层从还没用过的列里选一个，保证最终序列是一个排列。
    for (int col = 1; col <= n; col++) {
        if (used_col[col]) {
            continue;
        }
        choose[dep] = col;
        used_col[col] = 1;
        dfs(dep + 1);
        used_col[col] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    dfs(1);
    cout << total_ans << '\n';

    return 0;
}

这个暴力把每一行看成一个选择位置：choose[dep] 表示第 dep 行皇后选哪一列，used_col[] 保证列不重复，于是完整枚举的就是 $n$ 个列号的所有排列（ $n!$ 种）。递归先生成完整的 choose[]，到叶子节点才用 check() 统一检查对角线冲突，合法就计数，前 3 个直接输出。

这种写法只适合小数据，因为 $n = 13$ 时排列数高达 $6.2 \times 10^9$ ，即使每个方案只检查一次也不可能在时限内完成。瓶颈不是"检查"，而是把明显冲突的棋盘状态也完整枚举完了——例如第 1 行放了第 1 列后，第 2 行只要稍微一想就知道没希望，但暴力仍然会一路填到底，最后在叶子处才宣布非法。

关键观察：冲突只由三类信息决定

一个位置 $(row, col)$ 能否放皇后，只取决于：

这一列 col 是否已有皇后；
这一条主对角线（方向 $\backslash$ ，row - col 相同的格子）上是否已有皇后；
这一条副对角线（方向 $/$ ，row + col 相同的格子）上是否已有皇后。

同一条主对角线上的格子 $row - col$ 相等，同一条副对角线上的格子 $row + col$ 相等。于是可以用三个数组把"有没有皇后占用"存下来，判断一个位置是否合法从扫描前面所有皇后变成 $O(1)$ 查询，并且一旦冲突就立即剪掉整棵子树，不再向下递归：

used_col[col]：第 col 列是否已占用；
used_diag1[row - col + n]：主对角线（加 $n$ 把下标平移到正数）是否已占用；
used_diag2[row + col]：副对角线是否已占用。

样例棋盘

这张图展示样例 $n = 6$ 的第一个解 $2\ 4\ 6\ 1\ 3\ 5$ 在棋盘上的样子：

text

1
2
3
4
5
6
7    列:  1  2  3  4  5  6
 行 1:   .  Q  .  .  .  .
 行 2:   .  .  .  Q  .  .
 行 3:   .  .  .  .  .  Q
 行 4:   Q  .  .  .  .  .
 行 5:   .  .  Q  .  .  .
 行 6:   .  .  .  .  Q  .

先看"行"和"列"：每行每列恰好一个 Q，对应列号互不重复。再看对角线：任意两个 Q 都不在斜线方向上对齐，用公式说就是任意两行 $i < j$ 都满足 $|p[i] - p[j]| \neq j - i$ ——这正是主解里两个对角线数组各自检查的条件。

回溯剪枝

从第 $1$ 行开始递归，当前行按列号从小到大枚举：能放的位置放皇后、打三个标记、递归下一行，回来后撤销标记（回溯）；row > n 说明得到一个完整方案，总数加一，前 3 个方案直接输出。因为行号从小到大、列号也从小到大，搜索出来的完整序列天然按字典序出现，输出前 3 个就正好满足题意。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-13 13:19
 * update_at: 2026-08-13 13:19
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15; // n 最大为 13，多开一点防止越界
const int MAXD = 30; // 对角线编号范围：row - col + n 最大 25，row + col 最大 26

int n;
int pos[MAXN];        // pos[i]：第 i 行皇后所在的列号
int used_col[MAXN];   // used_col[c]：第 c 列是否已放皇后
int used_diag1[MAXD]; // used_diag1[k]：主对角线 row - col + n 是否已放皇后
int used_diag2[MAXD]; // used_diag2[k]：副对角线 row + col 是否已放皇后
long long total_ans;  // 合法方案总数
int printed_cnt;      // 已经输出的方案个数

// 输出当前完整方案：一行内按行号输出皇后所在列号。
void print_solution() {
    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << pos[i];
    }
    cout << '\n';
}

// 从第 row 行开始放皇后，枚举这一行可以放在哪一列。
// 列从小到大枚举，保证完整方案按字典序出现。
void dfs(int row) {
    if (row > n) { // 所有行都放完了，得到一个完整方案
        total_ans++;
        if (printed_cnt < 3) { // 只输出前 3 个解
            print_solution();
            printed_cnt++;
        }
        return;
    }

    for (int col = 1; col <= n; col++) {
        int d1 = row - col + n; // 主对角线编号：同一条对角线上 row - col 相等
        int d2 = row + col;     // 副对角线编号：同一条对角线上 row + col 相等
        if (used_col[col] || used_diag1[d1] || used_diag2[d2]) {
            continue; // 这一列或某条对角线已被占用，不能放
        }

        pos[row] = col;
        used_col[col] = 1;
        used_diag1[d1] = 1;
        used_diag2[d2] = 1;

        dfs(row + 1);

        // 回溯：撤销本行放的皇后
        used_col[col] = 0;
        used_diag1[d1] = 0;
        used_diag2[d2] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    dfs(1);
    cout << total_ans << '\n';

    return 0;
}

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-14 15:18
 * update_at: 2026-08-14 15:18
 */
/* P1219 八皇后：按行放皇后，用列、主对角线、副对角线三个标记数组剪枝，回溯求全部方案。 */

#include <iostream>

const int max_n = 14;    // n 最大为 13，多开一位
const int max_diag = 30; // 0 起始时对角线编号最大不超过 2 * max_n

int n;
int col_of_row[max_n];    // col_of_row[row]：第 row 行皇后所在的列
int used_col[max_n];      // used_col[col] = true 表示第 col 列已有皇后
int used_diag1[max_diag]; // used_diag1[k] = true 表示主对角线（row - col + n）已有皇后
int used_diag2[max_diag]; // used_diag2[k] = true 表示副对角线（row + col）已有皇后
int total_count = 0;      // 合法方案总数
int printed_count = 0;    // 已经输出的方案个数

// 输出一个完整方案：第 row 行皇后所在的列号，题目从 1 开始编号
void print_solution() {
    for (int row = 0; row < n; row += 1) {
        if (row > 0) {
            std::cout << ' ';
        }
        std::cout << col_of_row[row] + 1;
    }
    std::cout << '\n';
}

// 从第 row 行开始放皇后；列从小到大尝试，保证完整方案按字典序出现
void dfs(int row) {
    if (row == n) {  // 所有行都放完了，得到一个完整方案
        total_count += 1;
        if (printed_count < 3) {  // 只输出前 3 个方案
            print_solution();
            printed_count += 1;
        }
        return;
    }

    for (int col = 0; col < n; col += 1) {
        int d1 = row - col + n;  // 主对角线编号：同一条对角线上 row - col 相等
        int d2 = row + col;      // 副对角线编号：同一条对角线上 row + col 相等
        if (used_col[col] || used_diag1[d1] || used_diag2[d2]) {
            continue;  // 这一列或某条对角线已被占用，不能放
        }

        col_of_row[row] = col;
        used_col[col] = 1;
        used_diag1[d1] = 1;
        used_diag2[d2] = 1;

        dfs(row + 1);

        // 回溯：撤销本行放的皇后，让其他分支可以重新使用
        used_col[col] = 0;
        used_diag1[d1] = 0;
        used_diag2[d2] = 0;
    }
}

int main() {
    std::cin >> n;

    dfs(0);
    std::cout << total_count << '\n';

    return 0;
}

复杂度

时间复杂度：回溯搜索，最坏为排列规模 $O(n!)$ ，但三类标记把几乎全部非法分支剪在很浅的位置，实际搜索量远小于 $n!$ ；对 $n \leqslant 13$ 毫秒级完成。
空间复杂度： $O(n)$ ，包括方案数组 pos[]、三个标记数组和递归栈。

总结

八皇后是回溯搜索的经典模型：把"每个位置能不能放"拆成列、主对角线、副对角线三类互不干扰的约束，分别用数组记录，冲突立即剪枝，回溯时对称撤销。理解 $row - col$ 与 $row + col$ 两条对角线的编号方法，是这类"对角线约束"题目的通用钥匙，同模型的问题（如数独的宫约束、覆盖类搜索）都可以照搬"三类标记 + 回溯"的套路。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19暴力：枚举所有列排列，叶子统一检查 (brute.cpp)
  choose[dep]：第 dep 行选一列，used_col 保证列不重复
  -> 完整生成 n 列排列后 check() 对角线冲突，合法才计数
        |
        | 瓶颈：n = 13 时叶子 6.2e9 个，合法方案被埋在其中
        v
关键观察：冲突只由三类信息决定
  列：col 已占用
  主对角线：row - col 相同（方向 \）
  副对角线：row + col 相同（方向 /）
        |
        v
三数组回溯剪枝 (main.cpp)
  放皇后前 O(1) 查 used_col / used_diag1 / used_diag2
  冲突立即剪掉整棵子树，回溯撤销标记
        |
        v
输出：行号、列号都从小到大枚举
  方案天然按字典序出现 -> 前 3 个 + 总数

从上往下看：暴力的枚举对象是"完整列排列"，它把非法方案也全部生成了一遍，这是慢的根源；中间一行是把冲突拆成三类互不相关的约束，这是能剪枝的根源；最下面一行说明主解把合法性判断提前到放皇后之前，同时列号递增枚举顺便保证了输出顺序。