八皇后问题回溯法c语言
时间: 2023-10-06 18:14:09 浏览: 75
八皇后问题是一个经典的回溯算法问题,下面是C语言的实现代码:
```c
#include <stdio.h>
#define N 8
int queen[N] = {0}; // 存放每行皇后的位置
void print_queen() { // 打印棋盘
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (queen[i] == j) {
printf("Q ");
} else {
printf(". ");
}
}
printf("\n");
}
printf("\n");
}
int check(int row, int col) { // 判断当前位置是否合法
for (int i = 0; i < row; i++) {
if (queen[i] == col || queen[i] - col == i - row || queen[i] - col == row - i) {
return 0;
}
}
return 1;
}
void backtrack(int row) { // 回溯算法
if (row == N) { // 找到一个可行解
print_queen();
return;
}
for (int i = 0; i < N; i++) {
if (check(row, i)) { // 判断当前位置是否合法
queen[row] = i; // 放置皇后
backtrack(row + 1); // 递归放置下一行皇后
queen[row] = 0; // 回溯,尝试下一个位置
}
}
}
int main() {
backtrack(0);
return 0;
}
```
在上面的代码中,我们使用一个一位数组`queen`来存放每行皇后的位置,`print_queen()`函数用于打印棋盘,`check()`函数用于判断当前位置是否合法,`backtrack()`函数用于回溯算法求解八皇后问题。在`backtrack()`函数中,如果找到一个可行解,则打印棋盘并返回,否则递归放置下一行皇后。