N皇后问题：回溯算法实现

#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; } 该代码实现了经典的 N 皇后问题的求解，采用了基于回溯的算法。

代码中主要的数据结构是一个 Queen 结构体，用来表示一个皇后的位置（行、列），同时还定义了一个 stack 数组来实现栈。

主要函数包括 push 和 pop，用来实现栈的基本操作；canPlace 用来判断当前位置是否可以放置皇后；showSolution 用来展示一组解；solve 是核心的求解函数，采用了基于回溯的算法，用栈来保存已经放置的皇后的位置。

在 main 函数中，首先输入了皇后的个数 n，然后动态分配了一个大小为 n+1 的 Queen 数组作为栈，最后调用 solve 函数来求解问题。