数据结构八皇后问题实习报告

1、数据结构实习报告专业：数字媒体技术姓名：李义年级：2013级学号：201301052015完成日期：2015.12.31题目：八皇后问题一、项目简介八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8´8格的国际象棋棋盘上，安放八个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即任意两个皇后都不能处于同一行、同一列或同一条对角线上，求解有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法得出结论，有92种摆法。二、概要设计2.1 主要模块：这个程序主要由4个模

2、块组成，分别是画棋盘模块，画皇后模块，输出皇后摆法模块，和解决如何摆置皇后模块。这4个模块隶属于主函数模块。既主函数通过对这4个模块的合理调用解决“8皇后问题”，同时这4个模块之间也互有调用。2.2 程序设计的数据结构及其关系：数据结构的实现：数组ai：a i表示第i个皇后放置的列；i的范围：1-8;对角线数组：bj(主对角线),cj（从对角线），根据程序的运行，去决定主从对角线是否放入皇后；然后进行数据的初始化。从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于（未被占领）:如果是，摆放第n个皇后，并宣布占领(切记要横列竖列斜列一起来)，接

3、着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当时，却发现此时已经无法摆放时，便要进行回溯。三 、详细设计3.1 定义相关的数据类型：3.1.1 定义的相关数据类型：int A21,B21,C21,Y8;void *buff1,*buff23.1.2 设计思想：本程序通过对子函数void qu(int i)的调用，将八皇后的问题关键通过数据结构的思想予以了实现。虽然题目以及演算看起来都比较复杂，繁琐，但在实际中，只要当一只皇后放入棋盘后，在横与列、斜线上没有另外一只皇后与其冲突，再对皇后的定位进行相关的判断。即可完成。如果在这个程序中，我们运用的是非递归的思想，那么将大量使用if

4、等语句，并通过不断的判断，去推出答案，而且这种非递归的思想，大大的增加了程序的时间复杂度。如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。这个程序，我运用到了数据结构中的栈、数组，以及树和回溯的方法。特别是在对于树以及二叉树的学习，更是为八皇后的问题提供了科学的解决方案，通过对树的分析，把八皇后的问题看成了树，而在衍生第一个变化后，上面的第一层八个变化就变成了八个结点，而这八个结点再继续的衍生，这样比较形象的将八皇后的问题简单化了。然后再通过回溯法进行设计，回溯法是设计递归过程的一个重要的方法。它的求解过程实质上是一个先序遍历一棵“状态树“的过程。

5、在这个程序设计中，它先进行判断，棋盘上是否已经得到一个完整的布局（即棋盘是否已经摆上8个棋子），如果是，则输出布局；如果不是则依次先根遍历满足约束条件的各棵子树，流程即是：判断该子树根的布局是否合法：如果合法的话，则先根遍历该子树；如果不合法的话，则剪去该子树的分支。3.2 相关代码及算法3.2.1 主模块C码算法：void main(void)Queen Q;int gdriver=DETECT,gmode;initgraph(&gdriver,&gmode,"D:/Win-TC");SetQueen(&Q);setcolor(YELLOW);Qu

6、eenPic();cleardevice();setcolor(LIGHTGREEN);settextstyle(0,0,3);outtextxy(180,10,"Eight Queens");setcolor(WHITE);settextstyle(0,0,1);outtextxy(250,400,"2009.11.8 3:30pm");QueenRe(&Q,0);getch();closegraph();3.2.2 棋盘模块C码算法void Checker(void) /* 画棋盘函数 */int i,k;for(k=0;k<8;k+)

7、for(i=0;i<8;i+)if(k%2=0&&i%2=0|k%2!=0&&i%2!=0)setfillstyle(SOLID_FILL,LIGHTBLUE);setcolor(LIGHTBLUE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,LIGHTBLUE);elsesetfillstyle(SOLID_FILL,WHITE);setcolor(WHITE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20)

8、;floodfill(i*20+10,20+k*20+10,WHITE);3.2.3 皇后模块C码算法：void QueenPic(void) /* 画皇后图象，然后存储到缓冲区 */ int size,polypoints110=9,1,11,1,20,20,1,20,9,1,polypoints210=29,1,31,1,40,20,21,20,29,1;setfillstyle(SOLID_FILL,LIGHTBLUE); /* 画淡蓝色棋格 */setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);set

9、fillstyle(SOLID_FILL,WHITE); /* 画白色棋格 */setcolor(WHITE);rectangle(21,1,40,20);floodfill(30,10,WHITE);setfillstyle(SOLID_FILL,DARKGRAY);setcolor(YELLOW);drawpoly(5,polypoints1);drawpoly(5,polypoints2);floodfill(10,10,YELLOW);floodfill(30,10,YELLOW);size=imagesize(1,1,20,20); /* 计算缓冲区大小，然后存储 */buff1=(

10、void *)malloc(size);buff2=(void *)malloc(size);getimage(1,1,20,20,buff1);getimage(21,1,40,20,buff2);cleardevice();3.2.4 八皇后摆放方法模块C码:void QueenRe(Queen *Q, int y) 八皇后的递归算法int x;if(y>7)return;for(x=0;x<8;x+)if(!Q->Ax+7&&!Q->Bx+y+7&&!Q->Cx-y+7) 下一棵要遍历的子树由状态数确定 Q->Yy=x;

11、放置皇后Q->Ax+7=1;标记下次这里不能放置皇后Q->Bx+y+7=1;标记下次这里不能放置皇后Q->Cx-y+7=1; 标记下次这里不能放置皇后if(y=7)PrintQueen(Q);调用输出图形函数QueenRe(Q,y+1); 进入下一层递归Q->Ax+7=0;如果上次摆法导致后面不能继续摆放则重置标记为0 Q->Bx+y+7=0;Q->Cx-y+7=0;3.2.5 初始化模块C码:void SetQueen(Queen *Q) /* 初始化 */ int i;for(i=0;i<21;i+)Q->Ai=0; Q->Bi=0;Q

12、->Ci=0;初始化为0，表示可以放置皇后。 for(i=0; i<8; i+)Q->Yi=-1;3.2.6 图形输出：void PrintQueen(Queen *t) /* 图形输出函数 */int k;char str20;static total=0;total+;setviewport(240,80,400,260,1); /* 设置窗口 */sprintf(str,"NO.%d",total);setcolor(GREEN);settextstyle(0,0,1);outtextxy(0,0,str);Checker();for(k=0;k&l

13、t;8;k+)if(k%2=0&&t->Yk%2=0|k%2!=0&&t->Yk%2!=0)putimage(t->Yk)*20,20+k*20,buff1,COPY_PUT);elseputimage(t->Yk)*20,20+k*20,buff2,COPY_PUT);getch();if(getch()=27) exit(0);clearviewport();void QueenRe(Queen *Q, int y) /* 八皇后的递归算法 */ int x;if(y>7)return;for(x=0;x<8;x+)if(

14、!Q->Ax+7&&!Q->Bx+y+7&&!Q->Cx-y+7) /* 下一棵要遍历的子树由状态数确定 */Q->Yy=x;Q->Ax+7=1;Q->Bx+y+7=1;Q->Cx-y+7=1;if(y=7)PrintQueen(Q);QueenRe(Q,y+1); /* 进入下一层递归 */Q->Ax+7=0;Q->Bx+y+7=0;Q->Cx-y+7=0;3.3函数调用图3.4项目流程图四、调试分析通过编译连接后，程序基本上把八皇后的92种摆法的都进行了演示； 但程序运行中也出现了以下缺点：因为八皇

15、后的表现方法甚多，输出后虽能全部显示，但未能使屏幕停留，把一个一个的将其显示出来,但是这样便使得操作步骤太多,也会造成不必要的麻烦!所以只画出了第一种和最后一种的输出结果，演示如图所示：五、设计体会该程序在调试的过程中出现了不少的问题！如数据溢出等（是自己过于粗心而造成的）。在调试的过程中出现的一个最大的问题就是：在运行的时候出现解的个数大于自己所预计的。经过不断的查看内存变量，操作次数但还是没有找出问题的所在。终于在晚上十二点的时候，决定睡觉！但一关上电脑，躺在床上的时候，突然想到了一个问题：经过读了一些资料，知道八皇后问题有12组实质解，92组全解这说明在这12组实质解中有其中的一组解是比

16、其它的解要特殊一点的：其它的解经过等价的变换之后都会产生8组等价的解，只有这个特殊的解只有4组等价的解。说不定我的问题就出在这里！我之前也写了一些有关的代码处理这个问题，但我之前以为这个特殊的解是一个完全中心对称的图形（每转90度得到的图形就是它自己本身），所以我的在这里的判断就出现错误了！后来经过相关代码的修改，问题终于解决了，程序正确运行。本课程设计本人的目的也是通过用WIN-TC程序设计平台将一个的棋盘上放上个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现最终将其问题变得一目了然，更加易懂。六、用户使用说明6.1 程序的使用平台：系统要求：win

17、dows2000以上操作系统；语言开发平台：WIN-TC；6.2 源代码分析：首先对程序中的函数头文件进行引入，定位；在这个程序中，与其他C+的程序一样，都是引入：#include<iostream.h>；然后开始定义里面的函数所需要的数组，其中，setviewport(240,80,400,260,1);是对总的棋盘状态数进行定位，记录。接着，进入了主函数，在主函数中，先对棋盘进行初始化，并规定了在程序输出时的情况；然后，对行列，对角线也进行了初始化；并在对这些元素初始后，对子函数进行调用； 进入子函数后，便马上对皇后放入的位置进行判断，通过语句的判断，如果没有冲突的话，则放下皇

18、后，并标记，在下一次的时候，不再放入皇后；并在主从对角线进行判断，标记；然后再通过if语句判断，如果行还没有遍历完，进入下一行；接着通过放入一个for语句进行分析，如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置；当所有工作完成后，无冲突后，就返回主函数，并通过编译后对结果进行展示。七、附录#include <stdio.h>#include <stdlib.h>#include <conio.h>#include <dos.h>#include <graphics.h>void *buff1,*buff2;typ

19、edef structint A21,B21,C21,Y8;Queen;void SetQueen(Queen *Q) /* 初始化 */ int i;for(i=0;i<21;i+)Q->Ai=0;Q->Bi=0;Q->Ci=0;for(i=0; i<8; i+)Q->Yi=-1;void QueenPic(void) /* 画皇后图象，然后存储到缓冲区 */ int size,polypoints110=9,1,11,1,20,20,1,20,9,1,polypoints210=29,1,31,1,40,20,21,20,29,1;setfillstyl

20、e(SOLID_FILL,LIGHTBLUE); /* 画淡蓝色棋格 */ setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);setfillstyle(SOLID_FILL,WHITE); /* 画白色棋格 */ setcolor(WHITE);rectangle(21,1,40,20);floodfill(30,10,WHITE);setfillstyle(SOLID_FILL,DARKGRAY);setcolor(YELLOW);drawpoly(5,polypoints1);drawpoly(5,pol

21、ypoints2);floodfill(10,10,YELLOW);floodfill(30,10,YELLOW);size=imagesize(1,1,20,20); /* 计算缓冲区大小，然后存储 */ buff1=(void *)malloc(size);buff2=(void *)malloc(size);getimage(1,1,20,20,buff1);getimage(21,1,40,20,buff2);cleardevice();void Checker(void) /* 画棋盘函数 */int i,k;for(k=0;k<8;k+)for(i=0;i<8;i+)i

22、f(k%2=0&&i%2=0|k%2!=0&&i%2!=0)setfillstyle(SOLID_FILL,LIGHTBLUE);setcolor(LIGHTBLUE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,LIGHTBLUE);elsesetfillstyle(SOLID_FILL,WHITE);setcolor(WHITE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,WHITE);void PrintQueen(Queen *t) /* 图形输出函数 */int k;char str20;static total=0;total+;setviewport(240,80,400,260,1); /* 设置窗口 */sprintf(str,"NO.%d",total);setcolor(GREEN);settextstyle(0,0,1)