#include <stdlib.h> int isok(i,j){ for(int k=0;k<4;k++){ if(chess[k][j]==1){ return 0; } for(int m=i-1,int n=j-1;m>0&&n>0;m--,n--){ if(chess[m][n]==1){ return 0; } } } } int queen(int row){ for(int i=0;i<4;i++){ } } int main() { chess[4][4]={0}; for(int i=0;i) }优化解决四皇后问题
时间: 2024-03-17 16:39:47 浏览: 13
首先,代码存在一些语法错误,需要修正。
1. 函数 isok 应该声明返回类型 int,即:`int isok(int i, int j)`
2. 变量定义应该加上类型,即:`int m = i - 1, n = j - 1;`
3. 函数 queen 中的 for 循环没有写完整,需要补充。
4. for 循环中的条件不正确,需要改为 `i < 4`。
5. 变量 chess 的定义方式不正确,应该为 `int chess[4][4] = {0};`
接下来,我们对代码进行优化。
1. 简化 isok 函数
我们可以将判断列和判断对角线的部分合并,简化代码。
```c
int isok(int i, int j) {
for (int k = 0; k < 4; k++) {
if (chess[k][j] == 1 ||
(i - k >= 0 && j - k >= 0 && chess[i - k][j - k] == 1) ||
(i - k >= 0 && j + k < 4 && chess[i - k][j + k] == 1)) {
return 0;
}
}
return 1;
}
```
2. 优化 queen 函数
我们可以使用递归的方法,将每一行的皇后位置逐个确定,然后递归下一行。
```c
int queen(int row) {
if (row == 4) { // 找到一组解
return 1;
}
for (int j = 0; j < 4; j++) {
if (isok(row, j)) {
chess[row][j] = 1; // 将皇后放在当前位置
if (queen(row + 1)) { // 递归下一行
return 1;
}
chess[row][j] = 0; // 回溯,将当前位置重置为0
}
}
return 0;
}
```
3. 完整代码
```c
#include <stdlib.h>
int chess[4][4] = {0};
int isok(int i, int j) {
for (int k = 0; k < 4; k++) {
if (chess[k][j] == 1 ||
(i - k >= 0 && j - k >= 0 && chess[i - k][j - k] == 1) ||
(i - k >= 0 && j + k < 4 && chess[i - k][j + k] == 1)) {
return 0;
}
}
return 1;
}
int queen(int row) {
if (row == 4) { // 找到一组解
return 1;
}
for (int j = 0; j < 4; j++) {
if (isok(row, j)) {
chess[row][j] = 1; // 将皇后放在当前位置
if (queen(row + 1)) { // 递归下一行
return 1;
}
chess[row][j] = 0; // 回溯,将当前位置重置为0
}
}
return 0;
}
int main() {
if (queen(0)) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
printf("%d ", chess[i][j]);
}
printf("\n");
}
}
return 0;
}
```