- 1、本文档共11页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
八皇后算法
回溯算法的实现
(1)为解决这个问题,我们把棋盘的横坐标定为i,纵坐标定为j,i和j的取值范围是从1到8。当某个皇后占了位置(i,j)时,在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。用语句实现,可定义如下三个整型数组:a[8],b[15],c[24]。其中:
a[j-1]=1 第j列上无皇后
a[j-1]=0 第j列上有皇后
b[i+j-2]=1 (i,j)的对角线(左上至右下)无皇后
b[i+j-2]=0 (i,j)的对角线(左上至右下)有皇后
c[i-j+7]=1 (i,j)的对角线(右上至左下)无皇后
c[i-j+7]=0 (i,j)的对角线(右上至左下)有皇后
(2)为第i个皇后选择位置的算法如下:
for(j=1;j=8;j++) /*第i个皇后在第j行*/
if ((i,j)位置为空)) /*即相应的三个数组的对应元素值为1*/
{占用位置(i,j) /*置相应的三个数组对应的元素值为0*/
if i8
为i+1个皇后选择合适的位置;
else 输出一个解
}
#include graphics.h
#include stdlib.h
#include stdio.h
#include dos.h
char n[3]={0,0};/*用于记录第几组解*/
int a[8],b[15],c[24],i;
int h[8]={127,177,227,277,327,377,427,477};/*每个皇后的行坐标*/
int l[8]={252,217,182,147,112,77,42,7};/*每个皇后的列坐标*/
void *arrow;
void try(int i)
{int j;
for (j=1;j=8;j++)
if (a[j-1]+b[i+j-2]+c[i-j+7]==3) /*如果第i列第j行为空*/
{a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*占用第i列第j行*/
putimage(h[i-1],l[j-1],arrow,COPY_PUT);/*显示皇后图形*/
delay(500);/*延时*/
if(i8) try(i+1);
else /*输出一组解*/
{n[1]++;if (n[1]9) {n[0]++;n[1]=0;}
bar(260,300,390,340);/*显示第n组解*/
outtextxy(275,300,n);
delay(3000);
}
a[j-1]=1;b[i+j-2]=1;c[i-j+7]=1;
putimage(h[i-1],l[j-1],arrow,XOR_PUT);/*消去皇后,继续寻找下一组解*/
delay(500);
}
}
int main(void)
{int gdrive=DETECT,gmode,errorcode;
unsigned int size;
inITgraph(gdrive,gmode,);
errorcode=graphresult();
if (errorcode!=grOk)
{printf(Graphics error\n);exIT(1);}
rectangle(50,5,100,40);
rectangle(60,25,90,33);
/*画皇冠*/
line(60,28,90,28);line(60,25,55,15);
line(55,15,68,25);line(68,25,68,10);
line(68,10,75,25);line(75,25,82,10);
line(82,10,82,25);line(82,25,95,15);
line(95,15,90,25);
size=imagesize(52,7,98,38); arrow=malloc(size);
getimage(52,7,98,38,arrow);/*把皇冠保存到缓冲区*/
clearviewport();
settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4);
setusercharsize(3, 1, 1, 1);
setfillstyle(1,4);
for (i=0;i=7;i++) a[i]=1;
for (i=0;i=14;i++) b[i]=1;
for (i=0;i=23;i++) c[i]=1;
for (i=0;i=8;i++) line(125,i*35+5,525,i*35+5);/*画棋盘*/
for (i=0;i=8;i++) line(125+i*50,5,125+i*50,285);
try(
文档评论(0)