# USACO15 八皇后 Checker Challenge## 题目描述一个如下的 $6 times 6$ 的跳棋棋盘有六个棋子被放置在棋盘上使得每行、每列有且只有一个每条对角线包括两条主对角线的所有平行线上至多有一个棋子。!httpscdnluogucomcnuploadimage_hosting3h71x0yfpng上面的布局可以用序列 $2 4 6 1 3 5$ 来描述第 $i$ 个数字

#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)
{
    if (x > a)
    {
        if (INIT())
        {
            ans++;
            if (ans <= 3)
            {
                for (int i = 1; i <= a; i++)
                {
                    cout << fig[i] << ' ';
                }
                cout << endl;
            }
        }
        return;
    }
    for (int i = 1; i <= a; i++)
    {
        if (!fig[i])
        {
            fig[i] = x;
            pos(x + 1);
            fig[i] = 0;
        }
    }
    return;
}
int main()
{
    cin >> a;
    pos(1);
    cout << ans;
    return 0;
}

这个代码是一个典型的回溯算法，通过递归枚举八皇后的放置方式，并使用一个数组fig[]记录每行皇后所在的列数。

首先，通过memset函数将dp数组中的元素都初始化为空格字符。

然后，将每行皇后所在的位置标记为'Q'。

接下来，遍历每个皇后所在的位置，通过向八个方向进行扫描，将扫描到的位置标记为'1'。

如果扫描到的位置已经有皇后（即为'Q'），则说明此次放置不合法，返回false。

如果所有的扫描都没有冲突，则说明此次放置合法，返回true。

在每次递归中，先判断是否已经放置了所有的皇后，如果是，则调用INIT函数判断此次放置是否合法。

如果合法，则将ans自增，并判断ans是否小于等于3，如果是，则输出当前的放置方式。

最后，在主函数中，输入棋盘的大小，调用pos函数开始递归，最后输出ans的值。