求以下问题的完整代码

Question

皇后是国际象棋里最厉害的角色(so are women in real world)。 随着社会的不断发展，越来越多的人们意识到皇后在国际象棋里的地位应该降低,这样国际象棋才会更公平，更有意思。在传统的棋盘上，皇后能在任意的方向(横,竖,斜)上移动任意的步数。 新的国际象棋规定，皇后在竖直方向上还是可以移动任意的步数， 但在除此之外的其他方向上（水平和对角），她只能像国王一样移动一格。但皇后们并不罢休，即使他们被剥夺了的某些权利，她们也要想办法联合起来，即每个皇后都能被同伴支援保护。

在每个棋盘上，我们在每一列上放一个皇后。正如前面所说，棋盘上所有的皇后都想要联合起来，也就是说，每两个相邻列的皇后之间的行距离最多只能差一格，这样才可以及时互相支援(下图给出了四个例子，前三个是正确的，最后一个是错误的)。现在我们给出棋盘的大小和初始状态，你能计算出一共有多少种不同的放置皇后的方法使得所有的皇后都能联合起来吗

输入
本题包括多组测试数据。每组数据的第一行包含一个整数n(1 \le n \le 10)n(1≤n≤10)，代表一个n*nn∗n的棋盘。接下来的一行包括nn个整数。代表初始时每列已有的皇后的位置：如果这个值为i，则代表在这一列上，由上向下数第i个格子已经放了皇后；如果这个值为0，代表这一列还没有皇后，这时你可以在满足题目要求的情况下把一个皇后放在这一列的任意位置。当n=0时输入结束，这组数据不包括在需要计算的数据中。

输出
对于每一组输入数据，输出一个整数，代表在这种情况下符合条件的放置皇后的方法种数。输出0代表无法满足条件。

样例
输入

8
0 0 0 0 0 0 0 0
4
1 2 0 3
4
1 2 3 4
4
1 3 2 4
0
输出

11814
2
1
0

Answer 1

详细解答和代码如下，望采纳

• 对于每一列，我们都可以从上到下依次尝试放置皇后。如果当前的放置方式合法，就继续放置下一列的皇后；如果当前的放置方式不合法，就回溯到上一列，并尝试换一个位置放置皇后。
• 我们可以使用一个数组来记录当前每一列皇后的位置，并使用一个布尔变量来记录当前的放置方式是否合法。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_N 10
int n;
int queens[MAX_N];
int count;
bool check(int x, int y) {
    // 检查当前的皇后是否与其他皇后冲突
    for (int i = 0; i < x; i++) {
        // 判断是否在同一行或者同一对角线上
        if (queens[i] == y || abs(x - i) == abs(y - queens[i])) {
            return false;
        }
    }
    return true;
}
void dfs(int x) {
    // 如果已经放置了所有的皇后，就计数器加一
    if (x == n) {
        count++;
        return;
    }
    for (int y = 0; y < n; y++) {
        // 尝试放置皇后
        queens[x] = y;
        // 如果合法，则继续搜索下一列
        if (check(x, y)) {
            dfs(x + 1);
        }
    }
}
int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &queens[i]);
            queens[i]--;
        }
        count = 0;
        dfs(0);
        printf("%d\n", count);
    }
    return 0;
}