回溯法求解n皇后问题c
时间: 2023-10-03 22:07:21 浏览: 42
n 皇后问题指在 n×n 的棋盘上放置 n 个皇后,使得它们互相之间不会攻击到对方(即不在同一行、同一列或同一对角线上)。下面是使用回溯法求解 n 皇后问题的 C 代码:
```c
#include <stdio.h>
#include <stdlib.h>
int n; // 皇后数量
int *pos; // 存储每行皇后所在的列号
// 判断当前位置是否合法
int is_valid(int row, int col) {
for (int i = 0; i < row; i++) {
if (pos[i] == col || abs(i - row) == abs(pos[i] - col)) {
return 0;
}
}
return 1;
}
// 回溯求解
void solve(int row) {
// 所有皇后已经放置完毕,输出解
if (row == n) {
for (int i = 0; i < n; i++) {
printf("%d ", pos[i]);
}
printf("\n");
return;
}
// 尝试在当前行的每个位置放置皇后
for (int col = 0; col < n; col++) {
if (is_valid(row, col)) {
pos[row] = col;
solve(row + 1);
}
}
}
int main() {
printf("请输入皇后数量:");
scanf("%d", &n);
pos = (int *)malloc(n * sizeof(int));
solve(0);
free(pos);
return 0;
}
```
在程序中,首先输入皇后数量 n,然后动态分配数组 pos 来存储每行皇后所在的列号。回溯求解函数 solve 从第 0 行开始尝试在每个位置放置皇后,如果当前位置合法,则将皇后放在该位置,并递归进入下一行求解。如果所有皇后都已经放置完毕,则输出解。函数 is_valid 用来判断当前位置是否合法,即该位置是否与之前已经放置的皇后冲突。当所有解都被找到后,释放 pos 数组的空间。