解题思路

在 8×8 的棋盘上放 8 个皇后，要求任意两个皇后都不能在同一行、同一列、同一条对角线（因为皇后能沿横、竖、斜线无限远地吃子）。

这是最经典的回溯问题。

思路：

1. 一行一行地放皇后，从第 1 行放到第 8 行
2. 放第 r 行时，依次尝试第 1 列到第 8 列
3. 判断这个位置能不能放：这一列、这条主对角线、这条副对角线上都不能已经有皇后
4. 能放就放下去，然后递归放下一行
5. 8 行都放完就得到一组解，把它存起来
6. 放完要撤销占用（回溯），再尝试下一个位置

怎么判断列和对角线有没有皇后？

• 列：直接用一个数组记录每一列有没有皇后
• 主对角线（左上到右下）：同一对角线上的格子 行-列 相等，用 行-列+8 做编号
• 副对角线（右上到左下）：同一对角线上的格子 行+列 相等，用 行+列 做编号

为什么按列从小到大试？ 因为要求第 b 组解，且解要按字典序从小到大排，所以放每一行时从第 1 列开始依次试，得到的解自然是从小到大的顺序。

参考代码

#include <iostream>
using namespace std;

int col[10];       // col[r] 表示第 r 行皇后放在第几列
bool row[10];      // row[c] 表示第 c 列有没有皇后
bool d1[20];       // d1 表示某条主对角线上有没有皇后
bool d2[20];       // d2 表示某条副对角线上有没有皇后
int ans[95][10];   // 存所有 92 组解
int cnt;           // 已经找到几组解

// 深搜：给第 r 行放皇后（r 从 1 放到 8）
void dfs(int r) {
    if (r > 8) {  // 8 行都放好了，得到一组解
        cnt++;
        for (int i = 1; i <= 8; i++) {
            ans[cnt][i] = col[i];  // 存下这组解
        }
        return;
    }
    // 从第 1 列到第 8 列依次尝试，保证解从小到大排列
    for (int c = 1; c <= 8; c++) {
        // 这一列、主对角线、副对角线上都不能已经有皇后
        // 主对角线用 行-列 区分，副对角线用 行+列 区分
        if (!row[c] && !d1[r - c + 8] && !d2[r + c]) {
            col[r] = c;                             // 第 r 行放到第 c 列
            row[c] = d1[r - c + 8] = d2[r + c] = true;  // 占住这一列和两条对角线
            dfs(r + 1);                             // 继续放下一行
            row[c] = d1[r - c + 8] = d2[r + c] = false;  // 回溯：撤销占用
        }
    }
}

int main() {
    dfs(1);  // 先把全部 92 组解都算出来存好

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int b;
        cin >> b;  // 要第几组解
        // 输出第 b 组解的皇后串
        for (int j = 1; j <= 8; j++) {
            cout << ans[b][j];
        }
        cout << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：回溯搜索，8 皇后解一共 92 组，计算量很小
• 空间复杂度：O(1)，固定大小的几个数组