八皇后问题动态图形的实现

《八皇后问题动态图形的实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、八皇后问题动态图形的实现著名的八皇后问题。八个皇后在排列时不能同在一行、一列或一条斜线上。在8!=40320种排列中共有92种解决方案。不是很难，试试看？窗体顶部窗体底部“八皇后”动态图形的实现　　八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。　　高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。　　对于八皇后问题的实现，如果结合动态的

2、图形演示，则可以使算法的描述更形象、更生动，使教学能产生良好的效果。下面是笔者用TurboC实现的八皇后问题的图形程序，能够演示全部的92组解。八皇后问题动态图形的实现，主要应解决以下两个问题。1．回溯算法的实现　　（1）为解决这个问题，我们把棋盘的横坐标定为i，纵坐标定为j,i和j的取值范围是从１到８。当某个皇后占了位置(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)的对角线（左上至右下

3、）无皇后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*/ifi<8为i+1个皇后选择合适的位置；else输出一个解}2．图形存取　　在TurboC语言中，图形的存取可用如下标准函数实现：size=imagesize(x1,y1,x

4、2,y2);返回存储区域所需字节数。arrow=malloc(size);建立指定大小的动态区域位图，并设定一指针arrow。getimage(x1,y1,x2,y2,arrow);将指定区域位图存于一缓冲区。putimage(x,y,arrow,copy)将位图置于屏幕上以（x，y）左上角的区域。3．程序清单如下#include#include#include#includecharn[3]={'0','0'};/*用于记录第几组解*/inta[8],b[15],c[24],i;inth[8]={127

5、,177,227,277,327,377,427,477};/*每个皇后的行坐标*/intl[8]={252,217,182,147,112,77,42,7};/*每个皇后的列坐标*/void*arrow;voidtry(inti){intj;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);/*延时*

6、/if(i<8)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);}}intmain(void){intgdrive=DETECT,gmode,errorcode;unsignedintsiz

7、e;initgraph(&gdrive,&gmode,"");errorcode=graphresult();if(errorcode!=grOk){printf("Graphicserror");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