n皇后c语言非递归实现

以下是n皇后问题的C语言非递归实现，利用栈的数据结构来实现回溯过程：

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

#define MAX_N 20

int n; // 棋盘大小
int col_count[MAX_N]; // 棋盘每一列已经放置的皇后数
int diag1_count[2 * MAX_N - 1]; // 棋盘左上角到右下角的对角线已经放置的皇后数
int diag2_count[2 * MAX_N - 1]; // 棋盘右上角到左下角的对角线已经放置的皇后数

struct queen {
    int row;
    int col;
};

struct stack {
    struct queen data[MAX_N];
    int top;
};

void push(struct stack *s, struct queen q) {
    s->data[++s->top] = q;
}

struct queen pop(struct stack *s) {
    return s->data[s->top--];
}

int is_valid(int row, int col) {
    return col_count[col] == 0 && diag1_count[row + col] == 0 && diag2_count[row - col + n - 1] == 0;
}

void print_board(struct queen *queens) {
    char board[MAX_N][MAX_N];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = '.';
        }
        board[queens[i].row][queens[i].col] = 'Q';
    }
    for (int i = 0; i < n; i++) {
        printf("%s\n", board[i]);
    }
    printf("\n");
}

void n_queen() {
    struct stack s = {{0}, -1};
    push(&s, (struct queen) {.row = 0, .col = 0});
    while (s.top >= 0) {
        struct queen q = pop(&s);
        int row = q.row, col = q.col;
        col_count[col]++;
        diag1_count[row + col]++;
        diag2_count[row - col + n - 1]++;
        if (row == n - 1) {
            struct queen queens[MAX_N];
            for (int i = 0; i < n; i++) {
                queens[i] = s.data[i];
            }
            queens[n - 1] = q;
            print_board(queens);
        } else {
            for (int next_col = 0; next_col < n; next_col++) {
                if (is_valid(row + 1, next_col)) {
                    push(&s, (struct queen) {.row = row + 1, .col = next_col});
                }
            }
        }
        col_count[col]--;
        diag1_count[row + col]--;
        diag2_count[row - col + n - 1]--;
    }
}

int main() {
    scanf("%d", &n);
    n_queen();
    return 0;
}

该算法的时间复杂度为 $O(n!)$，空间复杂度为 $O(n)$。