C语言精解八个皇后问题C语言精解八个皇后问题
8.Algorithm8.Algorithm8.Algorithm Gossip:Gossip:Gossip: 八皇后
说明西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八
个皇后如何相安无事的放置在棋盘上，1970年与1971年， E.W.Dijkstra与N.Wirth曾经用
这个问
题来讲解程式设计之技巧。
解法关于棋盘的问题，都可以用递回求解，然而如何减少递回的次数,在八个皇后的问题中，
不必要所有的格子都检查过，例如若某列检查过，该该列的其它...
C语言精解八个皇后问题
8.Algorithm8.Algorithm8.Algorithm Gossip:Gossip:Gossip: 八皇后
说明西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八
个皇后如何相安无事的放置在棋盘上，1970年与1971年， E.W.Dijkstra与N.Wirth曾经用
这个问
题来讲解程式设计之技巧。
解法关于棋盘的问题，都可以用递回求解，然而如何减少递回的次数,在八个皇后的问题中，
不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个
方
法称为分支修剪。
#include #include #defineN 8
int column[N+1];// 同栏是否有皇后，1表示有 in trup[2*N+1];// 右上至左下是否有皇后 int lup[2*N+1];// 左上至右下是否有皇后 int queen[N+1]={0}; int num; // 解答编号
void backtrack(int);// 递回求解
intmain(void) {
inti;
num=0;
for(i =1;i<=N;i++) column[i] =1;
for(i =1;i<=2*N; i++) rup[i]= lup[i]=1; backtrack(1);
return 0;
}
void showAnswer(){ intx,y;
printf("\n解答 %d\n",++num); for(y =1;y<= N;y++) { for(x =1;x<= N;x++) { if(queen[y] == x){ printf(" Q");
}
else{
printf(" .");
}
}
printf("\n");
}
}
void backtrack(inti){ intj;
if(i >N){
showAnswer();
}
else{
for(j =1;j<=N;j++) {
if(column[j] ==1&&
rup[i+j]== 1 &&lup[i-j+N]==1){ queen[i]= j;
// 设定为占用
column[j] =rup[i+j] =lup[i-j+N] =0;
backtrack(i+1);
9.Algorithm Gossip:
column[j] =rup[i+j] =lup[i-j+N] =1;
}
}
}
}
本文档为【C语言精解八个皇后问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483