八皇后

题目描述

在 $8 \times 8$ 棋盘上放置 8 个皇后，使任意两个不在同一行、列或对角线上。给定 $b\ (1 \leqslant b \leqslant 92)$ ，输出第 $b$ 个按整数值排序的皇后串（第 $i$ 行皇后列号顺次拼接成的 8 位数）。

输入格式：第 1 行为 $n$ ，随后 $n$ 行每行一个 $b$ 。输出格式： $n$ 行对应皇后串。

样例：输入 2 1 92，输出 15863724 和 84136275。

思路

8 皇后固定且只有 92 个合法解，先按行 DFS + 位运算剪枝全部枚举，按整数值排序后数组回答每次查询。

参考代码

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
44
45
46
47#!/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-09-29 23:51
# update_at: 2026-10-04 13:17

import sys

N = 8          # 棋盘为 N × N
ALL = (1 << N) - 1  # 低位 N 个 1，表示当前行可放的列掩码


def collect(solutions: list[str], row: int, cols: int, diag1: int, diag2: int, path: list[int]) -> None:
    """按行 DFS：row 为当前处理行，cols/diag1/diag2 分别记录已被占用的列、主对角线、副对角线。"""
    if row == N:
        # 列号转换为 1-indexed 后拼成整数串
        solutions.append(''.join(str(c + 1) for c in path))
        return
    # 当前行仍可放的列：未被列或两条对角线攻击
    free = ALL & ~(cols | diag1 | diag2)
    while free:
        low = free & -free                 # 取最低位 1 作为当前列
        col = low.bit_length() - 1         # 列号 0..N-1
        path.append(col)
        # 下一行：列占用不变；对角线分别左移/右移一位表示攻击范围向下延伸
        collect(solutions, row + 1, cols | low, (diag1 | low) << 1, (diag2 | low) >> 1, path)
        path.pop()
        free ^= low                        # 清除这一位，尝试下一列


def solve() -> None:
    solutions: list[str] = []
    collect(solutions, 0, 0, 0, 0, [])
    solutions.sort()                       # 按整数字典序排列

    data = iter(map(int, sys.stdin.buffer.read().split()))
    q = next(data)                         # 询问组数
    out: list[str] = []
    for _ in range(q):
        b = next(data) - 1                 # 询问的序号（1-indexed）
        out.append(solutions[b])
    sys.stdout.write('\n'.join(out))


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/**
 * 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-05 05:42
 * update_at: 2026-10-05 05:42
 */

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;

const int N = 8;                // 棋盘为 8 × 8
const int ALL = (1 << N) - 1;   // 低 8 位为 1，表示当前行可放列的掩码

int col_of_row[N];              // col_of_row[i] 记录第 i 行皇后所在的列号（1..8）
vector<string> solutions;       // 所有合法皇后串

// 按行 DFS：row 为当前处理行，cols/diag1/diag2 分别记录已被占用的列、主对角线、副对角线
void dfs(int row, int cols, int diag1, int diag2) {
    if (row == N) {
        string s;
        for (int i = 0; i < N; ++i) s.push_back('0' + col_of_row[i]);
        solutions.push_back(s);
        return;
    }
    int free = ALL & ~(cols | diag1 | diag2); // 当前行仍可放的列
    while (free) {
        int low = free & -free;                // 取最低位 1 作为当前列
        int c = __builtin_ctz(low);            // 列号 0..7
        col_of_row[row] = c + 1;
        // 下一行：列占用不变；对角线分别左移/右移一位表示攻击范围向下延伸
        dfs(row + 1, cols | low, (diag1 | low) << 1, (diag2 | low) >> 1);
        free ^= low;                           // 清除这一位，尝试下一列
    }
}

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

    dfs(0, 0, 0, 0);
    sort(solutions.begin(), solutions.end());  // 按整数值排序

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; ++i) {
        int b;
        cin >> b;
        cout << solutions[b - 1] << '\n';
    }
    return 0;
}

目录

题目描述

思路

参考代码