八皇后问题 - USACO 1.5 挑战

八皇后问题 - USACO 1.5 挑战

一个如下的 $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;
int a, ans = 0;
#define N 15
int fig[N];
char dp[N][N];
int posx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int posy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
bool INIT()
{
    memset(dp, ' ', sizeof(dp));
    for (int i = 1; i <= a; i++)
    {
        dp[i][fig[i]] = 'Q';
    }
    for (int i = 1; i <= a; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            int x = i, y = fig[i];
            while (x >= 1 && y >= 1 && x <= a && y <= a)
            {
                x += posx[j];
                y += posy[j];
                if (dp[x][y] == 'Q')
                {
                    return false;
                }
                dp[x][y] = '1';
            }
        }
    }
    return true;
}
void pos(int x, vector<vector<int>> &res)
{
    if (x > a)
    {
        if (INIT())
        {
            ans++;
            vector<int> temp;
            for (int i = 1; i <= a; i++)
            {
                temp.push_back(fig[i]);
            }
            res.push_back(temp);
        }
        return;
    }
    for (int i = 1; i <= a; i++)
    {
        if (!fig[i])
        {
            fig[i] = x;
            pos(x + 1, res);
            fig[i] = 0;
        }
    }
    return;
}
int main()
{
    cin >> a;
    vector<vector<int>> res;
    pos(1, res);
    sort(res.begin(), res.end());
    for (int i = 0; i < min(3, (int)res.size()); i++)
    {
        for (int j = 0; j < a; j++)
        {
            cout << res[i][j] << ' ';
        }
        cout << endl;
    }
    cout << res.size();
    return 0;
}

为了按照字典序输出解，可以在生成解的过程中，对解进行排序。具体做法是，在pos函数中，将所有的解存储在一个vector中，然后对vector进行排序，最后输出前三个解即可。

修改后的代码如下：

#include <bits/stdc++.h>
using namespace std;
int a, ans = 0;
#define N 15
int fig[N];
char dp[N][N];
int posx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int posy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
bool INIT()
{
    memset(dp, ' ', sizeof(dp));
    for (int i = 1; i <= a; i++)
    {
        dp[i][fig[i]] = 'Q';
    }
    for (int i = 1; i <= a; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            int x = i, y = fig[i];
            while (x >= 1 && y >= 1 && x <= a && y <= a)
            {
                x += posx[j];
                y += posy[j];
                if (dp[x][y] == 'Q')
                {
                    return false;
                }
                dp[x][y] = '1';
            }
        }
    }
    return true;
}
void pos(int x, vector<vector<int>> &res)
{
    if (x > a)
    {
        if (INIT())
        {
            ans++;
            vector<int> temp;
            for (int i = 1; i <= a; i++)
            {
                temp.push_back(fig[i]);
            }
            res.push_back(temp);
        }
        return;
    }
    for (int i = 1; i <= a; i++)
    {
        if (!fig[i])
        {
            fig[i] = x;
            pos(x + 1, res);
            fig[i] = 0;
        }
    }
    return;
}
int main()
{
    cin >> a;
    vector<vector<int>> res;
    pos(1, res);
    sort(res.begin(), res.end());
    for (int i = 0; i < min(3, (int)res.size()); i++)
    {
        for (int j = 0; j < a; j++)
        {
            cout << res[i][j] << ' ';
        }
        cout << endl;
    }
    cout << res.size();
    return 0;
}

这样，就可以保证输出的解按照字典序排列。