洛谷P1219-八皇后_Checker_Challenge-题解

八皇后 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

P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷

思路

这道题目应该算是dfs回溯使用的模板题目了，dfs递归实现的特性非常适合回溯，在这题体现的特别明显。

题目的意思是说，给定一个 $n\times{n}$ 的矩阵，能组成多少种在同一对角线或直线上不拥有重复皇后的组合，并且输出前三种。

玩过国际象棋的话，可以理解成是在问可以排列出多少种位置，保证这 $n$ 个皇后谁都不能吃到谁。

那么我们暴力搜索思路很快就来了 声明四个数组，表示行，列，左对角线，右对角线，只要对角线上没有棋子，说明可以走，反之不可以，若下一步不能走了，回溯到上一步。

这里的行和列用数组表示容易，那么左右对角线如何表示呢。

我们知道，一个矩阵的对角线有 $2（n - 1）$ 条，其中左对角线（/）有 $n-1$ 条，为

$(1,1), (1,2)-(2,1), (1,3)-(2-2)-(3,1),\cdots,(1,n)-(2,n-1)-(3,n-2)-\cdots-(n,1),\cdots,(n,n)$

他们的 $x$ 和 $y$ 的和为 $2,3,4,\cdots,n+1,\cdots,2n$ 具有规律，因此我们可以用他们的下标和来表示左对角线

而右对角线也有 $n-1$ 条，为

$(1,n), (1,n-1)-(2,n), (1,n-2)-(2-n-1)-(3,n),\cdots,(1,1)-(2,2)-(3,3)-\cdots-(n,n),\cdots,(n,1)$

他们的 $x$ 和 $y$ 的差为 $1-n,2-n,3-n,\cdots,0,\cdots,n-1$ 具有规律，因此我们可以用他们的下标差来表示右对角线（\），但是数组下标不能为负数，所以我们可以给他们整体加上 $n$ 来解决问题，即 $1,2,3,\cdots,n,\cdots,2n-1$

综上所述，我们便可以用 $x$ 来表示行, $y$ 来表示列， $x + y$ 来表示左对角线（/）， $x - y + n$来表示右对角线（\）

标准dfs代码

void dfs(const int &i) {
    if (i > n) {
        if (ans < 3) {
            for (int j = 1; j <= n; j++)
                cout << column[j] << ' ';
            cout.put('\n');
        }
        ++ans;
        return;
    }
    for (int j = 1; j <= n; j++) {
        if (row[j] or leftDiagonal[i + j] or rightDiagonal[i - j + n])
            continue;
        column[i] = j;
        row[j] = leftDiagonal[i + j] = rightDiagonal[i - j + n] = true;
        dfs(i + 1);
        row[j] = leftDiagonal[i + j] = rightDiagonal[i - j + n] = false;
    }
};

栈实现dfs代码（这个需要开O2优化才能过，或者用二进制地图优化，递归层次太多了，栈性能损失）

auto dfs = [&] {
    stack<int> sta;
    struct t {
        int a, b, c;
        bool d;
    };
    stack<t> ways;
    sta.emplace(1);
    ways.emplace(-1, 0, 0, false);
    auto pop = [&] {
        sta.pop();
        auto v = ways.top();
        ways.pop();
        row[v.a] = leftDiagonal[v.b] = rightDiagonal[v.c] = false;
    };
    while (not sta.empty()) {
        int i = sta.top();
        auto &v = ways.top();
        column[i - 1] = v.a;
        if (i > n) {
            ans++;
            if (ans <= 3) {
                for (int j = 1; j <= n; ++j)
                    cout << column[j] << ' ';
                cout.put('\n');
            }
            pop();
            continue;
        }
        if (v.d) {
            pop();
            continue;
        }
        v.d = row[v.a] = leftDiagonal[v.b] = rightDiagonal[v.c] = true;
        for (int j = n; j >= 1; --j) {
            if (row[j] or leftDiagonal[i + j] or rightDiagonal[i - j + n])
                continue;
            sta.emplace(i + 1);
            ways.emplace(j, i + j, i - j + n, false);
        }
    }
    return ans;
};

AC截图