八皇后问题c语言递归代码
时间: 2024-09-27 09:01:53 浏览: 33
八皇后问题是经典的回溯算法示例,用于在一个8x8的棋盘上放置8个皇后,使得任意两个皇后都不在同一行、同一列,以及对角线上。下面是一个简单的C语言递归实现:
```c
#include <stdio.h>
#define N 8
// 检查皇后是否能安全放置在 (row, col) 位置
int isSafe(int row, int col, int board[N]) {
// 检查行
for (int i = 0; i < col; i++) {
if (board[i] == row)
return false;
}
// 检查左上方对角线
int di = row - col;
for (int i = 0; i < di; i++)
if (board[i] == row + i)
return false;
// 检查右上方对角线
di = N - row - col;
for (int i = 0; i < di; i++)
if (board[col + i] == row + i)
return false;
return true;
}
// 递归函数,放置皇后
void solveNQueens(int board[N], int row) {
if (row >= N) { // 如果放置了所有皇后,打印结果
for (int i = 0; i < N; i++)
printf("%d ", board[i]);
printf("\n");
return;
}
// 尝试每一列
for (int col = 0; col < N; col++) {
if (isSafe(row, col, board)) {
board[row] = col; // 安置皇后
solveNQueens(board, row + 1); // 递归下一行
board[row] = -1; // 回溯,移除皇后
}
}
}
int main() {
int board[N];
for (int i = 0; i < N; i++)
board[i] = -1; // 初始化为空
solveNQueens(board, 0);
return 0;
}
```
在这个代码中,`isSafe()` 函数检查当前位置是否安全,`solveNQueens()` 是核心递归函数,通过尝试每行的每个列来逐步解决问题。当所有的皇后都放置好,就会打印出解决方案。