C编程使用回溯法求N皇后问题
时间: 2023-09-17 09:12:15 浏览: 40
N皇后问题是经典的回溯算法问题,可以用C语言实现。以下是一个简单的实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAXN 100
int n; // 皇后数量
int ans; // 解的数量
int queen[MAXN]; // 存放皇后的列号
// 判断当前列是否可以放置皇后
bool is_valid(int row, int col) {
for (int i = 0; i < row; ++i) {
// 判断是否在同一列或对角线上
if (queen[i] == col || abs(queen[i] - col) == abs(i - row)) {
return false;
}
}
return true;
}
// 回溯搜索
void search(int row) {
if (row == n) { // 找到一个解
++ans;
return;
}
for (int col = 0; col < n; ++col) {
if (is_valid(row, col)) { // 判断当前列是否可以放置皇后
queen[row] = col; // 在当前行放置皇后
search(row + 1); // 继续搜索下一行
}
}
}
int main() {
printf("Enter the number of queens:\n");
scanf("%d", &n);
search(0);
printf("Total solutions: %d\n", ans);
return 0;
}
```
该代码中,`is_valid()`函数用于判断当前列是否可以放置皇后,`search()`函数进行回溯搜索,`main()`函数获取用户输入的皇后数量并调用`search()`函数进行求解。