题目描述

在n×n的棋盘上放置n个皇后，使得任意两个皇后不能在同一行、同一列或同一对角线上。输出所有合法解的数量，并在数量不超过3时输出前三个解。

解题思路

采用回溯法（深度优先搜索），通过数组记录行、列、主对角线、副对角线的占用情况，避免重复搜索。具体步骤：

1. 使用row数组记录每行是否已放置皇后；
2. 使用col数组记录每列是否已放置皇后；
3. 使用ls数组记录主对角线（左上到右下，坐标i+j-1）是否被占用；
4. 使用rs数组记录副对角线（右上到左下，坐标i-j+n）是否被占用；
5. 递归搜索每一行，对每一行尝试每一列，若该位置未被占用，则放置皇后并标记占用，继续搜索下一行；
6. 回溯时恢复状态，继续尝试下一列。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n, row[N], col[N], ls[N*2], rs[N*2];
int sum, a[N];  // a[x]记录第x行皇后所在的列号

void dfs(int x) {  // x表示当前处理第x行
    if(x > n) {  // 所有行都已处理完，找到一个解
        sum++;
        if(sum <= 3) {  // 输出前三个解
            for(int i=1; i<=n; i++) printf("%d ", a[i]);
            printf("\n");
        }
        return;
    }
    for(int i=1; i<=n; i++) {  // 尝试在第x行的第i列放置皇后
        // 检查列i、主对角线i+x-1、副对角线i-x+n是否被占用
        if(!row[x] && !col[i] && !ls[i+x-1] && !rs[i-x+n]) {
            row[x] = col[i] = ls[i+x-1] = rs[i-x+n] = 1;  // 标记占用
            a[x] = i;  // 记录列号
            dfs(x+1);  // 处理下一行
            row[x] = col[i] = ls[i+x-1] = rs[i-x+n] = 0;  // 回溯，恢复状态
            a[x] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    memset(row, 0, sizeof(row));
    memset(col, 0, sizeof(col));
    memset(ls, 0, sizeof(ls));
    memset(rs, 0, sizeof(rs));
    sum = 0;
    dfs(1);  // 从第1行开始搜索
    printf("%d\n", sum);  // 输出解的总数
    return 0;
}