回溯法 n皇后问题 c代码

下面是回溯法解决N皇后问题的C代码：

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

int n, count = 0; //n为皇后数量，count为解的数量
int *queen; //用于存储皇后位置的数组

//检查该位置是否可以放置皇后
int check(int k, int j) {
    for (int i = 0; i < k; i++) {
        if (queen[i] == j || abs(queen[i] - j) == abs(k - i)) {
            return 0;
        }
    }
    return 1;
}

//回溯函数
void backtrack(int k) {
    if (k == n) { //如果所有皇后都已放置
        count++;
        printf("Solution %d:\n", count);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (queen[i] == j) {
                    printf("Q ");
                } else {
                    printf(". ");
                }
            }
            printf("\n");
        }
        printf("\n");
    } else {
        for (int j = 0; j < n; j++) { //尝试放置皇后
            if (check(k, j)) {
                queen[k] = j;
                backtrack(k + 1);
            }
        }
    }
}

int main() {
    printf("Enter the number of queens: ");
    scanf("%d", &n);
    queen = (int*)malloc(n * sizeof(int));
    backtrack(0);
    printf("Total solutions: %d\n", count);
    return 0;
}

在此代码中，`check`函数用于检查某个位置是否可以放置皇后，`backtrack`函数是主要的回溯函数，它尝试放置皇后并继续递归，直到所有皇后都已放置。在主函数中，我们读取皇后数量并分配一个数组来存储皇后位置，然后调用`backtrack`函数来解决问题，最后输出解的数量。