c++代码bfs方法解决n皇后问题

下面是使用 BFS 算法来解决 n 皇后问题的 C 代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_N 100

// 皇后的位置
typedef struct {
    int x;  // 行
    int y;  // 列
} Queen;

// 状态
typedef struct {
    Queen queens[MAX_N];    // 皇后的位置
    int n;                  // 皇后的数量
} State;

// 队列
typedef struct {
    State states[MAX_N * MAX_N];
    int front, rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = q->rear = 0;
}

// 判断队列是否为空
bool isEmpty(Queue *q) {
    return q->front == q->rear;
}

// 入队
void enqueue(Queue *q, State *s) {
    q->states[q->rear++] = *s;
}

// 出队
void dequeue(Queue *q, State *s) {
    *s = q->states[q->front++];
}

// 判断两个皇后是否有冲突
bool conflict(Queen *q1, Queen *q2) {
    return q1->x == q2->x || q1->y == q2->y || abs(q1->x - q2->x) == abs(q1->y - q2->y);
}

// 判断状态是否合法
bool isValid(State *s) {
    for (int i = 0; i < s->n; i++) {
        for (int j = i + 1; j < s->n; j++) {
            if (conflict(&s->queens[i], &s->queens[j])) {
                return false;
            }
        }
    }
    return true;
}

// 打印状态
void printState(State *s) {
    for (int i = 0; i < s->n; i++) {
        for (int j = 0; j < s->n; j++) {
            if (s->queens[i].y == j) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

// 解决 n 皇后问题
void solve(int n) {
    State initial;
    initial.n = n;
    for (int i = 0; i < n; i++) {
        initial.queens[i].x = 0;
        initial.queens[i].y = i;
    }

    Queue q;
    initQueue(&q);
    enqueue(&q, &initial);

    State current;
    while (!isEmpty(&q)) {
        dequeue(&q, &current);
        if (current.n == n && isValid(&current)) {
            printState(&current);
        } else {
            for (int i = 0; i < n; i++) {
                State next = current;
                next.queens[next.n].x = next.n;
                next.queens[next.n].y = i;
                next.n++;
                enqueue(&q, &next);
            }
        }
    }
}

int main() {
    int n;
    printf("请输入皇后的数量：");
    scanf("%d", &n);
    printf("%d 皇后问题的解为：\n", n);
    solve(n);
    return 0;
}

上述代码中，使用了一个 `State` 结构体来表示状态，其中包含了当前放置的皇后的位置和数量。使用一个队列来存储状态，初始状态为第一行的皇后都放在不同的列中。在每次出队时，将当前状态的下一行所有可能放置的位置都入队，直到找到一个合法的解为止。