八皇后问题非递归求解算法：迭代加深搜索与栈结构

#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; }

对以上代码详细讲解内容：本文讲解八皇后问题的非递归求解算法，使用的是迭代加深搜索和栈结构。

首先看到题目，我们可以考虑使用递归的方式进行搜索，但是递归的深度可能会很大，导致栈溢出。因此，我们需要使用非递归的方式来避免栈溢出的问题。

算法基本思想：

• 用栈来存储已经放置的皇后的位置。
• 用一个循环来控制皇后的位置，每次从当前位置向右移动，直到找到可以放置皇后的位置。
• 如果找到了合适的位置，将皇后的位置入栈，然后继续从左边开始寻找下一个皇后的位置。
• 如果找不到合适的位置，就从栈中弹出上一个皇后，然后继续从右边开始寻找下一个合适的位置。
• 如果栈为空，搜索结束。

具体实现细节：

• 栈中存储的是已经放置的皇后的位置，每个皇后都是一个结构体，包含两个属性：x 表示皇后所在的行，y 表示皇后所在的列。
• 在搜索的过程中，每个皇后都是按照从左到右、从上到下的顺序来放置的。
• canPlace(Queen q) 函数用来判断当前位置是否可以放置皇后，它遍历栈中已经放置的皇后，检查新皇后所在的位置是否与已有的皇后在同一列或同一对角线上，如果是，就返回 0，表示不能放置皇后。如果遍历完所有的皇后，都没有发现冲突，就返回 1，表示可以放置皇后。
• showSolution() 函数用来打印一组解。在栈中保存的皇后的位置，就是八皇后问题的一组解。这个函数遍历栈中的所有皇后，然后用 Q 表示皇后所在的位置，用 . 表示空白位置。
• solve() 函数是主函数，它用来调用其他函数，初始化栈和解的个数，然后开始搜索。在搜索的过程中，使用迭代加深搜索的思想，每次从左边开始搜索，直到找到一组解为止。

完整代码如下：