用c语言写回溯法求解皇后问题
时间: 2023-10-14 19:04:56 浏览: 51
皇后问题是经典的回溯算法问题,以下是用 C 语言实现的代码。
```c
#include <stdio.h>
#include <stdlib.h>
#define N 8
int queen[N]; // 存放每一行皇后所在的列数
int count = 0; // 统计解的个数
// 判断 i 行 j 列是否可以放置皇后
int is_valid(int i, int j) {
for (int k = 0; k < i; k++) {
// 判断是否在同一列或同一对角线上
if (queen[k] == j || abs(queen[k] - j) == abs(k - i)) {
return 0;
}
}
return 1;
}
// 回溯函数
void backtrack(int i) {
if (i == N) {
count++; // 找到一组解
printf("Solution %d: ", count);
for (int j = 0; j < N; j++) {
printf("%d ", queen[j]);
}
printf("\n");
return;
}
// 在第 i 行尝试放置皇后
for (int j = 0; j < N; j++) {
if (is_valid(i, j)) {
queen[i] = j;
backtrack(i + 1);
}
}
}
int main() {
backtrack(0);
printf("Total solutions: %d\n", count);
return 0;
}
```
上述代码中,`queen` 数组存放每一行皇后所在的列数,`is_valid` 函数用于判断当前位置是否可以放置皇后,`backtrack` 函数用于回溯求解皇后问题。在 `main` 函数中,调用 `backtrack` 函数进行求解,并输出解的个数。