P1219 [USACO1.5] 八皇后 Checker Challenge

题目描述

一个如下的 ​6 \times 6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 ​2\ 4\ 6\ 1\ 3\ 5 来描述，第 ​i 个数字表示在第 ​i 行的相应位置有一个棋子，如下：

行号 ​1\ 2\ 3\ 4\ 5\ 6

列号 ​2\ 4\ 6\ 1\ 3\ 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 ​3 个解。最后一行是解的总个数。

输入格式

一行一个正整数 ​n，表示棋盘是 ​n \times n 大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

输入输出样例 #1

输入 #1
6
输出 #1
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
说明/提示

【数据范围】
对于 ​100\% 的数据，​6 \le n \le 13。

题目翻译来自NOCOW。

USACO Training Section 1.5

题解

通过题意我们可以知道任意两个皇后 不可以在同一行 同一列 同一斜线 因此 我们可以采用深度优先搜索搜索出所有的可能性

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1005;
int ans[N], x[N], y[N] ,z[N];//
int sum;//记录已经输出了多少行结果 题意要求三行结果
int n;//n个皇后
void dfs(int r) {
    //如果当递归深度已经大于所求的皇后的数量
    if (r>n) {
        if (sum<3) {//题目要求输出前三种
            for (int i=1; i<=n; i++) {
                cout << ans[i]<< " ";
            }
            cout << endl;
        }
        sum++;
        return;
    }
    for (int i=1; i<=n; i++) {
        if (x[i]==0 && y[i+r]==0 && z[r-i+n]==0) {//如果当前状态下 行 列 斜 都没有皇后占用
            //占用当前位置 并标记所在的行列斜
            ans[r]=i;
            x[i]=1;
            y[i+r]=1;
            z[r-i+n]=1;
            //继续搜
            dfs(r+1);
            //回溯
            ans[r]=0;
            x[i]=0;
            y[i+r]=0;
            z[r-i+n]=0;
        }
    }
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);
    cin >> n;
    dfs(1);
    cout << sum << endl;
    return 0;
}