usaco-1.5.4 跳棋的挑战

题目描述

在 $N \times N$ 的棋盘上放 $N$ 个棋子，要求每行、每列、每条对角线上至多一个棋子。用序列 $c_1 \dots c_N$ 表示解， $c_i$ 为第 $i$ 行棋子所在列号。按字典序输出前 3 个解，最后一行输出解的总数。 $6 \le N \le 13$ 。

输入：一个整数 $N$ 。
输出：前三行各为一个解，数字间用空格隔开；第四行为解的总数。

样例输入 6 的样例输出：

text

1
2
3
42 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

思路

逐行 DFS 放置棋子，用三个整数位掩码分别记录已占用的列、主对角线（ $r+c$ ）、副对角线（ $r-c$ ）。下一行时主对角线掩码左移一位、副对角线掩码右移一位，再用 free & -free 取最小合法列，天然按字典序搜索。到达第 $N$ 行时保存前 3 个解并统计总数。

参考代码

Python 版：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43#!/usr/bin/env python3
# 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-10-01 03:20
# update_at: 2026-10-01 03:20

import sys

SHOW = 3  # 题面只要求前 3 个解，而按列号升序展开时它们正好是字典序最小的 3 个


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    full = (1 << n) - 1          # 低 n 位全 1：第 c 位为 1 表示列 c 还没被占
    head: list[list[int]] = []   # 前 SHOW 个解，每个解是各行的列号
    pos = [0] * n                # pos[row] 是第 row 行的列号；放棋子即写入，回溯即被覆盖
    total = 0

    def dfs(row: int, col: int, diag1: int, diag2: int) -> None:
        """在第 row 行及其之后摆完剩下的棋子：三个掩码是已被占用的列 / 两条斜线。"""
        nonlocal total
        if row == n:                     # n 行都放好了，得到一个完整解
            total += 1
            if len(head) < SHOW:
                head.append(pos.copy())  # 不复制的话，回溯会把这份棋盘改掉
            return
        free = full & ~(col | diag1 | diag2)   # 本行所有合法列
        while free:
            bit = free & -free           # 取列号最小的合法列，同一层天然按字典序展开
            free ^= bit
            pos[row] = bit.bit_length()  # bit = 1 << (列号-1)，bit_length() 还原成 1 起算的列号
            # r+c 与 r-c 分别由 diag1、diag2 记录，走到下一行时两条斜线朝相反方向平移一位
            dfs(row + 1, col | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1)

    dfs(0, 0, 0, 0)
    print('\n'.join(' '.join(map(str, solution)) for solution in head))
    print(total)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-06 09:41
 * update_at: 2026-10-06 09:41
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 15;
const int SHOW = 3; // 题面只要求输出前 3 个解

int n;
int pos[MAXN]; // pos[row] 表示第 row 行棋子所在的列号（从 1 开始）
int total;     // 解的总数
int head[MAXN][MAXN]; // 保存前 SHOW 个解
int head_cnt;         // 已保存的解数

// 在第 row 行放置棋子，col/diag1/diag2 为已占用的列、主对角线、副对角线的位掩码
void dfs(int row, int col, int diag1, int diag2) {
    if (row == n) { // n 行都放好了，得到一个完整解
        ++total;
        if (head_cnt < SHOW) {
            for (int i = 0; i < n; ++i) {
                head[head_cnt][i] = pos[i];
            }
            ++head_cnt;
        }
        return;
    }
    int full = (1 << n) - 1; // 低 n 位全 1
    int free = full & ~(col | diag1 | diag2); // 本行所有合法列
    while (free) {
        int bit = free & -free; // 取列号最小的合法列，保证字典序
        free ^= bit;
        pos[row] = __builtin_ctz(bit) + 1; // bit = 1 << (列号-1)，还原列号
        // 下一行：列直接合并；两条对角线朝相反方向各平移一位
        dfs(row + 1, col | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    total = 0;
    head_cnt = 0;
    dfs(0, 0, 0, 0);
    for (int k = 0; k < head_cnt; ++k) {
        for (int i = 0; i < n; ++i) {
            if (i) cout << ' ';
            cout << head[k][i];
        }
        cout << '\n';
    }
    cout << total << '\n';
    return 0;
}

usaco-1.5.4 跳棋的挑战

目录

题目描述

思路

参考代码