c语言回溯算法n皇后问题

n皇后问题是一个经典的回溯算法问题，其目标是在n×n的棋盘上放置n个皇后，使得它们互相之间不能攻击，即任意两个皇后都不能在同一行、同一列或同一斜线上。

以下是C语言实现n皇后问题的回溯算法代码：

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

#define MAX_N 100

int N;               // 棋盘大小
int queen[MAX_N];    // 存储每行皇后的列号
int col[MAX_N];      // 列占用标记
int diag1[MAX_N*2];  // 正对角线占用标记
int diag2[MAX_N*2];  // 反对角线占用标记

// 放置第i个皇后
void put_queen(int i) {
    int j;
    if (i == N) {   // 已经放置了N个皇后，输出方案
        for (j = 0; j < N; j++) {
            printf("%d ", queen[j]);
        }
        printf("\n");
        return;
    }
    for (j = 0; j < N; j++) {
        if (!col[j] && !diag1[i+j] && !diag2[i-j+N]) {
            queen[i] = j;       // 在第i行第j列放置皇后
            col[j] = diag1[i+j] = diag2[i-j+N] = 1;  // 更新占用标记
            put_queen(i+1);     // 放置下一个皇后
            col[j] = diag1[i+j] = diag2[i-j+N] = 0;  // 恢复占用标记
        }
    }
}

int main() {
    scanf("%d", &N);
    put_queen(0);
    return 0;
}

在该算法中，我们使用四个数组来记录已经占用的列、正对角线和反对角线，每次放置皇后时，判断是否可以放置，若可以则更新占用标记，继续放置下一个皇后，否则回溯到上一个状态，恢复占用标记。

该算法的时间复杂度为O(n!)，空间复杂度为O(n)，其中n为棋盘大小。