用c写一个皇后问题
时间: 2023-12-10 07:39:59 浏览: 27
皇后问题是一个经典的回溯算法问题,下面是用C语言实现的代码:
```c
#include <stdio.h>
#define N 8
int board[N][N]; // 棋盘,0表示没有皇后,1表示有皇后
// 判断当前位置是否可以放置皇后
int canPlace(int row, int col) {
int i, j;
// 检查该列是否有皇后
for (i = 0; i < row; i++) {
if (board[i][col]) {
return 0;
}
}
// 检查左上方是否有皇后
i = row - 1;
j = col - 1;
while (i >= 0 && j >= 0) {
if (board[i][j]) {
return 0;
}
i--;
j--;
}
// 检查右上方是否有皇后
i = row - 1;
j = col + 1;
while (i >= 0 && j < N) {
if (board[i][j]) {
return 0;
}
i--;
j++;
}
return 1;
}
// 打印棋盘
void printBoard() {
int i, j;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
printf("%d ", board[i][j]);
}
printf("\n");
}
printf("\n");
}
// 回溯求解皇后问题
void solve(int row) {
int i, j;
if (row == N) { // 找到一组解
printBoard();
return;
}
for (j = 0; j < N; j++) {
if (canPlace(row, j)) { // 可以放置皇后
board[row][j] = 1; // 放置皇后
solve(row + 1); // 继续放下一行的皇后
board[row][j] = 0; // 回溯,撤销皇后的位置
}
}
}
int main() {
int i, j;
// 初始化棋盘
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
board[i][j] = 0;
}
}
solve(0); // 从第0行开始放皇后
return 0;
}
```
上面的代码中,`canPlace`函数用于判断当前位置是否可以放置皇后,它检查该列、左上方和右上方是否有皇后。`printBoard`函数用于打印棋盘,`solve`函数是回溯求解皇后问题的核心部分,它从第0行开始递归地寻找可行解。`main`函数初始化棋盘并调用`solve`函数。
相关推荐
![](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)