课程设计实验——八皇后_VC++游戏

时间:2011-12-18 16:29:14
【文件属性】:

文件名称:课程设计实验——八皇后_VC++游戏

文件大小:904KB

文件格式:RAR

更新时间:2011-12-18 16:29:14

八皇后

八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。   高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。   对于八皇后问题的实现,如果结合动态的图形演示,则可以使算法的描述更形象、更生动,使教学能产生良好的效果。下面是用Turbo C实现的八皇后问题的图形程序,能够演示全部的92组解。八皇后问题动态图形的实现,主要应解决以下两个问题。   (1)回溯算法的实现   (a)为解决这个问题,我们把棋盘的横坐标定为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)的对角线(右上至左下)有皇后   (b)为第i个皇后选择位置的算法如下:   for(j=1;j<=8;j++) /*第i个皇后在第j行*/   if ((i,j)位置为空)) /*即相应的三个数组的对应元素值为1*/   {占用位置(i,j) /*置相应的三个数组对应的元素值为0*/   if i<8   为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 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(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);   }}   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=1;   for (i=0;i<=14;i++) b=1;   for (i=0;i<=23;i++) c=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);   }   二、循环实现 Java   /*   * 8皇后问题:   *   * 问题描述:   * 在一个8×8的棋盘里放置8个皇后,要求每个皇后两两之间不相冲突   *(在每一横列,竖列,斜列只有一个皇后)。   *   * 数据表示:   * 用一个 8 位的 8 进制数表示棋盘上皇后的位置:   * 比如:45615353 表示:   * 第0列皇后在第4个位置   * 第1列皇后在第5个位置   * 第2列皇后在第6个位置   * 。。。   * 第7列皇后在第3个位置   *   * 循环变量从 00000000 加到 77777777 (8进制数)的过程,就遍历了皇后所有的情况   * 程序中用八进制数用一个一维数组 data[] 表示   *   * 检测冲突:   * 横列冲突:data == data[j]   * 斜列冲突:(data+i) == (data[j]+j) 或者 (data-i) == (data[j]-j)   *   * 好处:   * 采用循环,而不是递规,系统资源占有少   * 可计算 n 皇后问题   * 把问题线性化处理,可以把问题分块,在分布式环境下用多台计算机一起算。   *   * ToDo:   * 枚举部分还可以进行优化,多加些判断条件速度可以更快。   * 输出部分可以修改成棋盘形式的输出   *   * @author cinc 2002-09-11   *   */   public class Queen {   int size;   int resultCount;   public void compute ( int size ) {   this.size = size;   resultCount = 0;   int data[] = new int[size];   int count; // 所有可能的情况个数   int i,j;   // 计算所有可能的情况的个数   count = 1;   for ( i=0 ; i I - K THEN 90   70 G = 0   80 GOTO 100   90 NEXT K   100 IF I <> 8 THEN 180   110 IF G = 0 THEN 180   120 FOR L = 1 TO 8   130 PRINT USING “##”; A(L);   140 NEXT L   150 PRINT “*”;   160 M = M + 1   170 IF M MOD 3 = 0 THEN PRINT   180 IF G = 0 THEN 230   190 IF I = 8 THEN 230   200 I = I + 1   210 A(I) = 1   220 GOTO 30   230 IF A(I) < 8 THEN 270   240 I = I - 1   250 IF I = 0 THEN 290   260 GOTO 230   270 A(I) = A(I) + 1   280 GOTO 30   290 PRINT   300 PRINT “SUM=”; USING “##”; M;   310 PRINT   320 END   四、八皇后问题的高效解法-递归版   //8 Queen 递归算法   //如果有一个Q 为 chess=j;   //则不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置   class Queen8{   static final int QueenMax = 8;   static int oktimes = 0;   static int chess[] = new int[QueenMax];//每一个Queen的放置位置   public static void main(String args[]){   for (int i=0;i= 0) && (chess+k < QueenMax) ) qsave[chess+k]=false;   if ( (chess-k >= 0) && (chess-k < QueenMax) ) qsave[chess-k]=false;   i++;   }   //下面历遍安全位   for(i=0;i


【文件预览】:
queen.suo
queen.sln
queen
----resource.h(905B)
----stdafx.h(2KB)
----queen.h(435B)
----Debug()
--------BuildLog.htm(12KB)
----stdafx.cpp(136B)
----ReadMe.txt(3KB)
----queen.vcproj.8x8.Wendell.user(1KB)
----queenDlg.cpp(6KB)
----queen.cpp(2KB)
----queen.rc(5KB)
----cup.bmp(7KB)
----res()
--------queen.rc2(361B)
--------queen.ico(766B)
----queenDlg.h(1KB)
----queen.bmp(7KB)
----queen.vcproj(5KB)
debug
----queen.ilk(5.32MB)

网友评论

  • 写得还不错
  • 挺好的,学到了不少东西,谢谢分享