八皇后问题
程序员文章站
2022-05-25 12:33:05
...
问题描述
在8*8的国际象棋棋盘中,摆放8个皇后,使得每一行、每一列、每一条斜线上都只有一个皇后。
问题分析
先在第一行的第一个位置摆放第一个皇后
接着在第二行顺序查找摆皇后的位子
以此类推:
下一行没有符合摆放皇后的位置。说明上一行摆放的皇后位置不合适。返回上一行重新摆放皇后。(开始回溯)
当前行依旧摆放不了皇后,继续回溯
以此类推直到八个皇后都放到棋盘上。
算法描述:
记录每个坐标的状态:
用数组:
col[8]——–记录每一列的状态
left[15]——记录每一条左斜线的状态
right[15]—–记录每一条右斜线的状态
坐标和左右斜线的关系:
(i,j)
left[i+j]
right[7+i-j]
用Queen[8]来记录皇后的坐标—-下标代表皇后所在的行,所对应的值代表皇后所在的列。
#include<stdio.h>
#include<stdlib.h>
int col[8] = { 0 };//用来记录皇后在每一行的状态
int Queen[8];//用来记录皇后的坐标
int left[15] = { 0 }, right[15] = { 0 };//分别用来记录皇后在每一条斜线(左右)的状态
int count = 0;//用来记录摆法的组数
//输出八皇后
void printQueen(int Queen[8]){
for (int i = 0; i < 8; i++){
for (int j = 0; j < 8; j++){
if (Queen[i] == j){
printf(" $ ");
}
else{
printf(" + ");
}
}
printf("\n\n");
}
printf("\n\n");
}
//八皇后问题
void queen(int i){
for (int j = 0; j < 8; j++){
if (!col[j] && !left[i + j] && !right[7 + i - j]){
//证明当前位置和之前摆放皇后的位置不发生冲突,(当前位置可以摆放皇后)
Queen[i] = j;//在当前位置摆放皇后
//更改当前位置的状态
col[j] = left[i + j] = right[7 + i - j] = 1;
if (i < 7){
queen(i + 1);//摆放下一个皇后
//当前行摆放不了皇后,开始回溯,更改上一个皇后的位置
col[j] = left[i + j] = right[7 + i - j] = 0;
}
else{
printf("第%d组\n", ++count);
printQueen(Queen);
//找下一组解
col[j] = left[i + j] = right[7 + i - j] = 0;
}
}
}
}
int main(void){
queen(0);
printf("共计:%d\n", count);
system("pause");
return 0;
}
调试结果:
上一篇: 安装jupyter遇到的问题
下一篇: 八皇后