n皇后问题回溯法c语言
时间: 2023-10-07 12:04:25 浏览: 40
下面是n皇后问题的回溯法C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100
int n, ans = 0; // n为棋盘大小,ans为合法解的数量
int c[MAXN]; // c[i]表示第i行皇后所在的列
// 检查在第row行第col列放置皇后是否合法
int check(int row, int col) {
for (int k = 0; k < row; k++) {
if (c[k] == col || abs(row - k) == abs(col - c[k])) {
return 0;
}
}
return 1;
}
// 在第row行放置皇后
void dfs(int row) {
if (row == n) { // 找到一组合法解
ans++;
return;
}
for (int col = 0; col < n; col++) {
if (check(row, col)) {
c[row] = col;
dfs(row + 1);
c[row] = 0; // 回溯,撤销当前选择
}
}
}
int main() {
scanf("%d", &n);
dfs(0);
printf("%d\n", ans);
return 0;
}
```
在上面的代码中,check函数用来检查在第row行第col列放置皇后是否合法。如果合法,将c[row]赋值为col,然后继续在下一行放置皇后,直到放满n个皇后为止。如果在第n行放置了皇后,说明找到了一组合法解,ans加1。dfs函数中,每次循环都会调用check函数检查当前选择是否合法。如果合法,将c[row]赋值为col,然后递归调用dfs函数,在下一行放置皇后。当找到一组合法解后,需要回溯,撤销当前选择,继续寻找其他解。