N 皇后问题回溯法 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; }

这段代码实现了 N 皇后问题的求解。

N 皇后问题是指在 N×N 的棋盘上放置 N 个皇后，使得任意两个皇后都不能在同一行、同一列或同一对角线上。本算法使用回溯法进行求解。

代码中定义了一个 Queen 结构体，表示一个皇后的位置。同时定义了栈 stack 和栈顶指针 top，用来存储已经放置的皇后。

push() 函数将一个皇后压入栈中，pop() 函数将栈顶的皇后弹出。

canPlace() 函数用来判断一个皇后是否可以放置在当前位置。如果同一列或同一对角线上已经有皇后了，就不能放置。

showSolution() 函数用来输出一组解。

solve() 函数是求解 N 皇后问题的主函数。首先将栈清空，从第一行第一列开始，依次放置皇后。如果当前位置不能放置皇后，就尝试在当前行的下一列放置。如果所有列都不能放置皇后，就回溯到上一个皇后所在的位置，然后尝试在下一列放置。如果在最后一行放置了皇后，就找到了一组解。

在 main() 函数中，首先输入 N，然后动态分配栈空间，调用 solve() 函数求解，最后释放栈空间。

总体来说，这段代码实现比较简洁，但也有一些缺陷。例如，栈的空间大小是固定的，不能动态调整；同时，该算法只能找到一组解，如果需要找到所有解，需要进行一些改进。