八皇后问题是一个经典的回溯算法问题,要求在一个8x8的棋盘上放置8个皇后,使得它们不能相互攻击(即不能在同一行、同一列或同一对角线上)。下面是一个使用C语言编写的八皇后问题的解决方案:
```c
include
void fun(int i, int j);
static int b;
int main() {
fun(0, 0);
return 0;
}
void fun(int i, int j) {
int temp_i, temp_j, k;
temp_i = i;
temp_j = j;
// 递归终止条件
if (i == 8) {
for (int k = 1; k <= 8; k++) {
for (int l = 1; l <= 8; l++) {
printf("%d ", b[k - 1][l - 1]);
}
printf("\n");
}
return;
}
// 检查当前位置是否可以放置皇后
for (int k = 1; k <= 8; k++) {
if (b[temp_i][k - 1] == 0 && b[k - 1][temp_j] == 0 && (temp_i - temp_j != k - 1 && temp_i + temp_j != k - 1)) {
b[temp_i][k - 1] = 1;
fun(temp_i + 1, temp_j + 1);
b[temp_i][k - 1] = 0;
}
}
}
```
代码解释
全局变量
`b`:用于记录每一行皇后所在的列。
主函数
`main()`:调用`fun(0, 0)`开始递归过程。
递归函数
`fun(int i, int j)`:表示当前在第`i`行第`j`列尝试放置皇后。
如果`i`等于8,说明已经成功放置了8个皇后,打印所有皇后的位置并返回。
否则,遍历当前行的每一列,检查是否可以放置皇后(即该位置及其对角线位置是否已经放置了皇后)。如果可以放置,则放置皇后并递归调用`fun(i + 1, j + 1)`,否则回溯(将当前位置重置为0)。
编译和运行
将上述代码保存为一个C文件(例如`eight_queens.c`),然后使用C编译器(如`gcc`)进行编译和运行:
```sh
gcc eight_queens.c -o eight_queens
./eight_queens
```
运行程序后,将会输出所有可能的八皇后排列。