八皇后问题c语言,用递归算法
时间: 2024-06-30 09:00:17 浏览: 156
八皇后问题是一个经典的回溯算法问题,目标是在一个8x8的棋盘上放置8个皇后,使得任意两个皇后都不在同一行、同一列或同一斜线上。这里,我们使用C语言的递归方法来解决这个问题:
```c
#include <stdio.h>
#define N 8
// 检查皇后是否能安全放置在给定位置
int isSafe(int row, int col, int chessboard[N][N]) {
for (int i = 0; i < row; i++) {
if (chessboard[i][col] == 1 || // 同行
abs(chessboard[row][i] - col) == abs(chessboard[row][col] - col)) { // 对角线
return 0;
}
}
return 1;
}
// 递归函数,用于放置皇后
void placeQueens(int row, int chessboard[N][N], int placed) {
if (row == N) { // 如果所有皇后都放置完成
// 输出解决方案
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", chessboard[i][j]);
}
printf("\n");
}
return;
}
// 尝试将皇后放在每一列
for (int col = 0; col < N; col++) {
if (isSafe(row, col, chessboard)) {
chessboard[row][col] = placed + 1; // 标记为已放置
placeQueens(row + 1, chessboard, placed + 1); // 递归到下一行
chessboard[row][col] = 0; // 回溯,尝试下一个位置
}
}
}
int main() {
int chessboard[N][N] = {0};
// 从第一行开始
placeQueens(0, chessboard, 1);
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)