n皇后问题的回溯算法及运行时间c代码

n皇后问题是一个经典的回溯算法问题，其目标是在一个n×n的棋盘上放置n个皇后，使得每个皇后都不会互相攻击（即不在同一行、同一列、同一对角线上）。下面是n皇后问题的回溯算法及运行时间C代码：

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

#define MAX_N 100

int n; // 棋盘大小
int queen[MAX_N]; // 存储皇后位置的数组
int count = 0; // 解的个数

// 判断当前位置是否可以放置皇后
int is_valid(int row, int col) {
    for (int i = 0; i < row; i++) {
        if (queen[i] == col || abs(queen[i] - col) == abs(i - row)) {
            return 0;
        }
    }
    return 1;
}

// 回溯函数
void backtrack(int row) {
    if (row == n) { // 找到一个解
        count++;
        return;
    }
    for (int col = 0; col < n; col++) {
        if (is_valid(row, col)) { // 当前位置可以放置皇后
            queen[row] = col; // 记录皇后位置
            backtrack(row + 1); // 继续搜索下一行
        }
    }
}

int main() {
    scanf("%d", &n);
    backtrack(0); // 从第0行开始搜索
    printf("%d\n", count);
    return 0;
}

该算法的时间复杂度为O(n^n)，因为在最坏情况下，每个皇后都有n个可选位置，总共需要搜索n^n个状态。