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

八皇后问题动态图形的实现著名的八皇后问题。八个皇后在排列时不能同在一行、一列或一条斜线上。在8!=40320种排列中共有92种解决方案。不是很难，试试看？ 窗体顶部窗体底部“八皇后”动态图形的实现八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动，使教学能产生良好的效果。下面是笔者用Turbo C实现的八皇后问题的图形程序，能够演示全部的92组解。八皇后问题动态图形的实现，主要应解决以下两个问题。1回溯算法的实现（1）为解决这个问题，我们把棋盘的横坐标定为i，纵坐标定为j,i和j的取值范围是从到。当某个皇后占了位置(i,j)时，在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。用语句实现，可定义如下三个整型数组：a8,b15,c24。其中：aj-1=1 第j列上无皇后aj-1=0 第j列上有皇后bi+j-2=1 (i,j)的对角线（左上至右下）无皇后bi+j-2=0 (i,j)的对角线（左上至右下）有皇后ci-j+7=1 (i,j)的对角线（右上至左下）无皇后ci-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 输出一个解2图形存取在Turbo C语言中，图形的存取可用如下标准函数实现：size=imagesize(x1,y1,x2,y2) ;返回存储区域所需字节数。arrow=malloc(size);建立指定大小的动态区域位图，并设定一指针arrow。getimage(x1,y1,x2,y2,arrow);将指定区域位图存于一缓冲区。putimage(x,y,arrow,copy)将位图置于屏幕上以（x，y）左上角的区域。3 程序清单如下#include #include #include #include char n3=0,0;/*用于记录第几组解*/int a8,b15,c24,i;int h8=127,177,227,277,327,377,427,477;/*每个皇后的行坐标*/int l8=252,217,182,147,112,77,42,7;/*每个皇后的列坐标*/void *arrow;void try(int i)int j;for (j=1;j=8;j+)if (aj-1+bi+j-2+ci-j+7=3) /*如果第i列第j行为空*/aj-1=0;bi+j-2=0;ci-j+7=0;/*占用第i列第j行*/putimage(hi-1,lj-1,arrow,COPY_PUT);/*显示皇后图形*/delay(500);/*延时*/if(i9) n0+;n1=0;bar(260,300,390,340);/*显示第n组解*/outtextxy(275,300,n);delay(3000);aj-1=1;bi+j-2=1;ci-j+7=1;putimage(hi-1,lj-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 errorn);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+) ai=1;for (i=0;i=14;i+) bi=1;for (i=0;i=23;i+) ci=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(1);/*调用递归函数*/delay(3000);closegraph();free(arrow);八皇后问题的串行算法 1八皇后问题 所谓八皇后问题,是在8*8格的棋盘上,放置8个皇后。要求每行每列放一个皇后,而且每一条对角线和每一条反对角线上不能有多于1个皇后,也即对同时放置在棋盘的两个皇后(row1,column1)和(row2,column2),不允许(column1-column2)=(row1-row2)或者(column1+row1)=(column2+row2)的情况出现。 2八皇后问题的串行递归算法 八皇后问题最简单的串行解法为如下的递归算法: (2.1)深度递归函数: go(intstep,intcolumn) inti,j,place; rowstep=column; if(step=8) outputresult();/*结束递归打印结果*/ else/*继续递归*/ for(place=1;place=8;place+) for(j=1;j=step;j+) if(collision(j,rowj,step+1,place) /*判断是否有列冲突、对角线或反对角线*/ gotoskip_this_place; go(step+1,place); skip_this_place:; /*go*/ (2.2)主函数: voidmain() intplace,j; for(place=1;place=8;place+) go(1,place); /*main*/八皇后问题的并行算法 该算法是将八皇后所有可能的解放在相应的棋盘上,主进程负责生成初始化的棋盘，并将该棋盘发送到某个空闲的子进程,由该子进程求出该棋盘上满足初始化条件的所有的解。这里，我们假定主进程只初始化棋盘的前两列，即在棋盘的前两列分别放上2个皇后,这样就可以产生8*8=64个棋盘。 1主进程算法 主进程等待所有的子进程,每当一个子进程空闲的时侯，就向主进程发送一个Ready(就绪)信号。主进程收到子进程的Ready信号后,就向该子进程发送一个棋盘。当主进程生成了所有的棋盘后,等待所有的子进程完成它们的工作。然后向每个子进程发送一个Finished信号,打印出各个子进程找到的解的总和，并退出。子进程接收到Finished信号也退出。 2子进程算法 每个子进程在收到主进程发送过来的棋盘后,对该棋盘进行检查。若不合法,则放弃该棋盘。子进程回到空闲状态,然后向主进程发送Ready信号,申请新的棋盘;若合法,则调用move_to_right(board,rowi,colj)寻找在该棋盘上剩下的6个皇后可以摆放的所有位置,move_to_right(board,rowi,colj)是个递归过程,验证是否能在colj列rowi行以后的位置是否能放一个皇后。 1)首先将more_queen设置成FALSE； 以LEAF,TRUE和FLASE区分以下三种情况: A)LEAF:成功放置但是已到边缘,colj现在已经比列的最大值大1,回退两列,检查是否能将待检查皇后放在哪一行:如果能,把more_queen设成TRUE; B)TRUE:成功放置皇后,检查这一列是否能有放置皇后的其他方式,如有,把more_queen设成TRUE; C)FALSE:不能放置,回退一列再试,如果能把more_queen设成TRUE,如果皇后已在最后一行,必须再检查上一列。 2)如果more_queens=TRUE,仍需再次调用move_to_right(),为新棋盘分配空间,用xfer()将现有棋盘拷贝到nextboard，并进行下列情况的处理： TRUE:得到一个皇后的位置,增大列数再试； FALSE:失败,如果more_queen为真,取回棋盘,保存上次调用的棋盘。将列数减小,取走皇后,增加行数,再调用move_to_right()； LEAF:得到一种解法,solution增一,将解法写入log_file,由于已到边缘,列数回退1,检查是否放置一个皇后,如果能,新加一个皇后后,调用move_to_right；如果不能,检查more_queen如果more_queen为真,将棋盘恢复到上次调用时保存的棋盘,将待检查的皇后下移,调用move_to_right。八皇后问题的高效解法-递归版 shadowkiss（原作）转自CSDN /Yifi2003havefun!:) /8Queen递归算法/如果有一个Q为chessi=j;/则不安全的地方是k行j位置,j+k-i位置,j-k+i位置 classQueen8 staticfinalintQueenMax=8;staticintoktimes=0;staticintchess=newintQueenMax;/每一个Queen的放置位置 publicstaticvoidmain(Stringargs)for(inti=0;iQueenMax;i+)chessi=-1;placequeen(0);System.out.println(nnn八皇后共有+oktimes+个解法madebyyifi2003); publicstaticvoidplacequeen(intnum)/num为现在要放置的行数inti=0;booleanqsave=newbooleanQueenMax;for(;iQueenMax;i+)qsavei=true;/下面先把安全位数组完成i=0;/i是现在要检查的数组值while(i=0)&(chessi+k=0)&(chessi-kQueenMax)qsavechessi-k=false;i+;/下面历遍安全位for(i=0;iQueenMax;i+)if(qsavei=false)continue;if(numQueenMax-1)chessnum=i;placequeen(num+1);else/numislastonechessnum=i;oktimes+;System.out.println(这是第+oktimes+个解法如下:);System.out.println(第n行:12345678);for(i=0;iQueenMax;i+)Stringrow=第+(i+1)+行:;if(chessi=0);elsefor(intj=0;jchessi;j+)row+=-;row+=+;intj=chessi;while(jQueenMax-1)row+=-;j+;System.out.println(row);/历遍完成就停止#include #include #include #define QUEENS 8 /!记录解的序号的全局变量。 int iCount = 0; /!记录皇后在各列上的放置位置的全局数组。 int SiteQUEENS; /!递归求解的函数。 void Queen(int n); /!输出一个解。 void Output(); /!判断第n个皇后放上去之后，是否有冲突。 int IsValid(int n); /*-Main：主函数。-*/ void main() /!从第0列开始递归试探。 Queen(0); /!按任意键返回。 getch(); /*-Queen：递归放置第n个皇后，程序的核心!-*/ void Queen(int n) int i; /!参数n从0开始，等于8时便试出了一个解，将它输出并回溯。 if(n = QUEENS) Output(); return; /!n还没到8，在第n列的各个行上依次试探。 for(i = 1 ; i = QUEENS ; i+) /!在该列的第i行上放置皇后。 Siten = i; /!如果放置没有冲突，就开始下一列的试探。 if(IsValid(n) Queen(n + 1); /*-IsValid：判断第n个皇后放上去之后，是否合法，即是否无冲突。-*/ int IsValid(int n) int i; /!将第n个皇后的位置依次于前面n1个皇后的位置比较。 for(i = 0 ; i n ; i+) /!两