C语言解决八皇后问题-创新互联
八皇后问题描述,是回溯算法的典型案例,在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列、同一斜线上。
成都创新互联从2013年成立,是专业互联网技术服务公司,拥有项目网站制作、成都网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元泗县做网站,已为上家服务,为泗县各地企业和个人服务,联系电话:028-86922220回溯算法:简单的说就是循环加递归。
思路:
- 创建棋盘map[8][8],字符‘e’表示空的位置,字符‘Q’表示皇后的位置
- 创建循环,因为棋盘是8x8,所以循环为8(这里的8表示棋盘的中皇后的列),递归棋盘中皇后的行。然后一一试。
- 放棋子的时候检查当前坐标的当前列是否有皇后。左对角线是否有皇后,在检查右对角线是否有皇后。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include#define TRUE 1
#define FALSE 0
#define NUM 8 //棋盘8x8 皇后8个,可以设置其它数量
#define QUEEN 'Q'
#define EMPTY 'e'
char map[NUM][NUM]; //棋盘。empty表示空,queen表示皇后
int sum = 0; //一共有多少种摆法
void initialize(); //初始化棋盘
void output(); //输出当前棋谱
void judge(); //判断现在的位置是否能放棋盘
void putChessman(int row); //摆放棋子
int main(void) {
initialize();
putChessman(0);
return 0;
}
void initialize() {
for (int i = 0; i< NUM; i++)
for (int j = 0; j< NUM; j++)
map[i][j] = EMPTY;
}
void output() {
printf("第%d中摆法\n", ++sum);
for (int i = 0; i< NUM; i++) {
for (int j = 0; j< NUM; j++)
printf("%c ", map[i][j]);
printf("\n");
}
printf("\n\n");
}
int judge(int row, int col) {
for (int i = 0; i< row; i++)
if (map[i][col] == QUEEN)
return FALSE;
int rowCopy = row, colCopy = col;
while (rowCopy >= 0 && colCopy >= 0) //判断左对角线是否有皇后,左对角线的极限是(0,0)
if (map[rowCopy--][colCopy--] == QUEEN)
return FALSE;
while (row >= 0 && col< NUM) //判断右对角线是否有皇后,左对角线的极限是(0,7)
if (map[row--][col++] == QUEEN)
return FALSE;
return TRUE;
}
void putChessman(int row) {
if (row >= NUM) {
output();
return;
}
for (int col = 0; col< NUM; col++) {
if (judge(row, col)) {
map[row][col] = QUEEN;
putChessman(row + 1);
map[row][col] = EMPTY;
}
}
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章标题:C语言解决八皇后问题-创新互联
网站URL:http://pwwzsj.com/article/cdssge.html