八皇后问题 C 语言代码实现：回溯算法详解

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

typedef struct {
    int x;
    int y;
} Queen;

int n; //皇后个数
int cnt; //解的个数
Queen* stack; //栈
int top; //栈顶指针

void push(Queen q) {
    stack[++top] = q;
}

Queen pop() {
    return stack[top--];
}

int canPlace(Queen q) {
    int i;
    for (i = 1; i <= top; ++i) {
        if (stack[i].y == q.y // 同列
            || abs(stack[i].x - q.x) == abs(stack[i].y - q.y)) { // 同对角线
            return 0;
        }
    }
    return 1;
}

void showSolution() {
    int i, j;
    printf("Solution %d:\n", ++cnt);
    for (i = 1; i <= top; ++i) {
        for (j = 1; j <= n; ++j) {
            if (stack[i].y == j) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
}

void solve() {
    top = 0;
    Queen q = {1, 1};
    while (1) {
        while (q.y <= n && !canPlace(q)) {
            ++q.y;
        }
        if (q.y > n) {
            if (top == 0) {
                break; // 搜索结束
            }
            q = pop();
            ++q.y;
        }
        else {
            push(q);
            if (top == n) {
                showSolution(); // 找到一组解
                q = pop();
                ++q.y;
            }
            else {
                ++q.x;
                q.y = 1;
            }
        }
    }
}

int main() {
    printf("Please input the number of Queens: ");
    scanf("%d", &n);
    stack = malloc(sizeof(Queen) * (n + 1));
    solve();
    free(stack);
    return 0;
}

代码解释：

该代码使用回溯算法解决八皇后问题。

定义结构体：Queen 结构体表示皇后，包含其行号 (x) 和列号 (y)。
定义变量：n 表示皇后数量，cnt 表示找到的解的数量，stack 表示皇后位置的栈，top 表示栈顶指针。
栈操作函数：push 和 pop 函数实现栈的基本操作。
冲突判断函数：canPlace 函数用于判断当前位置是否可以放置皇后，如果与已放置的皇后在同一列或同一对角线上，则返回 0，否则返回 1。
输出解函数：showSolution 函数用于输出找到的一组解。
回溯算法函数：solve 函数使用循环和条件判断进行回溯搜索。首先尝试将第一个皇后放置在第一列的第一行，如果可以放置则放置，并递归地尝试放置下一个皇后。如果无法放置，则尝试将当前皇后放置在下一行，如果下一行也无法放置，则回溯到上一层，尝试将上一层的皇后放置在下一行，以此类推。
主函数：接收用户输入的皇后数量，分配栈空间，调用 solve 函数进行求解，最后释放栈空间。

时间复杂度:

该代码的时间复杂度为 O(n^n)，因此仅适用于 n 较小的情况。