[USACO1.5] 八皇后 Checker Challenge

题意

在 n × n 的棋盘上放 n 个皇后。

要求：

每一行恰好放一个；
每一列恰好放一个；
任意两皇后不能在同一条对角线上。

把一个解表示成长度为 n 的序列，第 i 个数表示第 i 行皇后所在的列号。

需要按字典序输出前 3 个解，并在最后输出总解数。

思路

最直接的想法是按行搜索。

第 row 行枚举皇后放在哪一列，只要和前面已经放过的皇后不冲突，就继续递归到下一行。

这个最朴素、最容易理解的版本如下：

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int n;
int pos[MAXN];   // pos[i]：第 i 行皇后放置的列
long long total_ans;
int printed_cnt;

bool can_place(int row, int col) {
    for (int i = 1; i < row; i++) {
        if (pos[i] == col) {
            return false;
        }
        if (abs(i - row) == abs(pos[i] - col)) {
            return false;
        }
    }
    return true;
}

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

void dfs(int row) {
    if (row > n) {
        total_ans++;
        if (printed_cnt < 3) {
            print_solution();
            printed_cnt++;
        }
        return;
    }

    for (int col = 1; col <= n; col++) {
        if (!can_place(row, col)) {
            continue;
        }
        pos[row] = col;
        dfs(row + 1);
    }
}

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

    cin >> n;

    total_ans = 0;
    printed_cnt = 0;
    dfs(1);
    cout << total_ans << '\n';

    return 0;
}

为什么按行搜就够了

因为题目要求每一行恰好放一个皇后，所以我们完全可以固定“递归深度 = 当前处理到哪一行”。

这样每层只需要决定这一行放在哪一列，不需要再考虑“这一行放几个”的问题。

朴素检查的瓶颈

在 brute.cpp 里，如果想判断 (row, col) 能不能放，就要枚举前面所有已经放过的皇后，检查：

是否同列；
是否在同一条对角线。

这个思路虽然正确，但每次判断都要扫一遍之前的行。

用三个数组做剪枝

我们维护三个数组：

used_col[col]：这一列是否已有皇后；
used_diag1[row-col+n]：这一条主对角线是否已有皇后；
used_diag2[row+col]：这一条副对角线是否已有皇后。

这样判断某个位置能不能放，就从“扫描前面所有皇后”变成了 $O(1)$ 查询。

为什么输出顺序天然是字典序

我们递归时：

行号从小到大处理；
每一行的列号从小到大枚举。

因此搜索出来的完整序列天然就是按字典序出现的。只要在找到解时先输出前 3 个，就正好满足题意。

Python 知识

用一个整数的二进制位表示已占用列；available & -available 每次取出最低可用位，因此列号仍按升序枚举。
bit.bit_length() 把单独的二进制位转换成从 1 开始的列号。
path.append(...)、递归、path.pop() 是 Python 回溯的标准“选择、递归、撤销”结构。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：DFS 回溯与状态恢复。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：保存路径和递归状态时的可变对象陷阱。

代码

python

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
30n = int(input())
full = (1 << n) - 1
path = []
first_solutions = []
total = 0


def dfs(columns, left_diagonals, right_diagonals):
    global total
    if columns == full:
        total += 1
        if len(first_solutions) < 3:
            first_solutions.append(" ".join(map(str, path)))
        return

    available = full & ~(columns | left_diagonals | right_diagonals)
    while available:
        position = available & -available
        available -= position
        path.append(position.bit_length())
        dfs(
            columns | position,
            (left_diagonals | position) << 1 & full,
            (right_diagonals | position) >> 1,
        )
        path.pop()


dfs(0, 0, 0)
print(*first_solutions, total, sep="\n")

复杂度

时间复杂度：最坏为搜索复杂度，通常记作回溯搜索
空间复杂度： $O(n)$

因为这是典型搜索题，实际运行时间取决于剪枝效果。这里 n <= 13，配合列和对角线数组已经足够通过。

总结

这题是非常经典的回溯搜索题。

核心不是“怎么存答案”，而是把“某个位置能不能放”这件事尽量判断得快。列、主对角线、副对角线三类约束拆开维护后，搜索就会顺畅很多。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。