c语言八皇后问题程序设计.docx

2014年春季学期C项目设计报告题 目：八皇后问题学 号：092213112姓 名：刘泽中组 名：1指导教师：宋东兴日 期：2014.05.15目 录正 文31.问题描述32. 总体设计与分析33. 相关代码54. 调试分析95.软件使用说明书11总结11附录：部分原程序代码12一、 问题描述1. 八皇后问题:是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出：在88棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？2.解决八皇后问题的关键在于：（1）找到合理的数据结构存放棋子的摆放位置。（2）要有合理的冲突检查算法。采用的方法是，先把8个棋子摆在棋盘上，每行摆一个，然后去检查这种摆放是否有冲突，如果没有冲突，即找到了一种解决方案。由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正，这就是“回溯”的思想。在8个皇后未放置完成前，每行摆放一个皇后，摆放第i个皇后和第i+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。二、总体设计与分析1.设计效果 画一个8*8的国际象棋盘，在棋盘某一位置上放一棋子，并让它按从左到右的方向自动运动，用户可以使用光标键调整棋子运动的方向，找出所有可能的摆放方案，将包含指定的棋子的（如3行4列）摆放方案找出并显示出来。2.、总体设计程序总体分为两大块：（1）八皇后摆法的寻找； （2）棋盘及棋子的设计。3、详细模块 （1）八皇后摆法的寻找： int chess88=0; /二维数组表示8*8棋盘,全部清0,（0代表该位没有放棋子）void queen(int i,int n) /i表示从第i行起为后续棋子选择合适位置，n代表n*n棋盘 if(i=n) output(n); /输出棋盘当前布局; else for(j=0;jn;j+) /每行可能有n个摆放位置 chessij = 1; /在第i行，j列上放一棋子 if(!canAttack(i,j) /如果当前布局合法,不受前i-1行的攻击 queen(i+1,n); /递归摆放i+1行 chessij = 0; /移走第i行，j列的棋子 int canAttack(int i,int j) /判断0到i-1行已摆放的棋子，对i,j位置是否可以攻击 for(m=0;mi;m+) for(n=0;n8;n+) if(chessmn=1) if(m=i|n=j) return 1; if(m+n=i+j | m-n=i-j) return 1; return 0;void output() /输出一组解，即打印出8个皇后的坐标 for(int i=0;i8;i+) for(int j=0;j8;j+) if(chessij=1) printf(%d,%d),i,j); printf(“n”);int main() queen(0,8); return 0;（2）棋盘及棋子的设计： void drawBlock(int i,int j) /棋盘的设计（每一个小方块） int x0,y0,x1,y1; x0=ORGX+j*W; y0=ORGY+i*H; x1=x0+W-1; y1=y0+H-1; setcolor(WHITE); rectangle(x0,y0,x1,y1); setfillstyle(1,LIGHTGRAY); floodfill(x0+1,y0+1,WHITE); setcolor(WHITE); line(x0,y0,x1,y0); line(x0,y0,x0,y1); setcolor(BLACK); line(x1,y0,x1,y1); line(x0,y1,x1,y1);void drawBall(Ball ball) /棋子的设计int x0,y0; x0=ball.startX+ball.c*ball.w+ball.w/2; y0=ball.startY+ball.r*ball.h+ball.h/2; setcolor(RED); setfillstyle(1,RED); fillellipse(x0,y0,10,10);4.程序设计思路：先设计程序，找到八皇后的摆放位置，方法是：先把8个棋子摆在棋盘上，每行摆一个，然后去检查这种摆放是否有冲突，如果没有冲突，即找到了一种解决方案。采用递归方法和“回溯”思想，找到8*8棋盘上的各种摆法，并把它打印显示出来，共92种。然后用TC进行图形编程，画出精美的棋盘，设计好棋子，从显示棋盘，显示棋子，上下左右移动棋子，一步一步，减少错误率。最后，将棋盘棋子和八皇后摆放的代码结合一起，做出可以使用光标键调整棋子运动方向，找出所有可能的摆放方案，将包含指定的棋子的（如3行4列）摆放方案找出并显示出来的效果。整个大程序看起来很复杂，但是把其分成二大块，最后再合成，便显得很容易多了。 三、相关代码 1. typedef struct /定义一个棋子数据结构 int r,c; /棋子在棋盘上的的行，列坐标 int h,w; /棋子所在方块的高度和宽度 int startX,startY; /棋盘在屏幕的起始坐标，画棋子定位所用 enum Direction dir;Ball; 2. void init() /初始化 int gdriver,gmode; gdriver = DETECT; initgraph(&gdriver,&gmode,c:tc30bgi); cleardevice();3. void drawTable() /画棋盘 int i,j,size; for(i=0;iROW;i+) for(j=0;jdir)case KEY_UP:ball-r-;if(ball-rr = rols-1;break;case KEY_DOWN:ball-r+;if(ball-r=rols) ball-r=0;break;case KEY_LEFT:ball-c-;if(ball-cc = cols-1;break;case KEY_RIGHT:ball-c+;if(ball-c=cols) ball-c=0;break; 7. void init2(Ball*ball,int r,int c,int size,int x0,int y0) /初始化一个棋子 ball-r=r;ball-c=c; ball-h=ball-w=size; ball-startX=x0;ball-startY=y0;8. void clearBall() /将缓存区的棋盘拿出来 putimage(50,50,buff1,COPY_PUT);9. void changeDir(Ball *ball,enum Direction dir) /运动方向 ball-dir=dir;10. void fun(Ball ball) /当前棋子的坐标 xx=ball.r; xy=ball.c;11. void queen(int i) / i表示从第i行起为后续棋子选择合适位置 int j; if(i=8) outputa(); else for(j=0;j8;j+) chessij=1; /二维数组表示8*8棋盘（0代表该位没有放棋子） if(!canAttack(i,j)/如果当前布局可行，不受i-1行的攻击 queen(i+1); /递归摆放i+1行 chessij=0; / 移走第i行，j列的棋子 12. int canAttack(int i,int j)/ 判断0到i-1行已摆放的棋子，对i,j位置是否可以攻击int m,n; for(m=0;mi;m+) for(n=0;n8;n+) if(chessmn=1) if(m=i|n=j) return 1; if(m+n=i+j|m-n=i-j) return 1; return 0;13. void outputa() Ball myBall; int i,j,a=0,b=0; for(i=0;i8;i+) /输出一组解，坐标分别保存到两个数组里 for(j=0;j8;j+) if(chessij=1) faa+=i; fbb+=j; if(fam=0) /判断是否为全部输出，fam为1时输出全部92种解 for(i=0;i8;i+) if(fai=xx&fbi=xy) /如果有坐标与当前棋子坐标相同时 delay(800); /延时800毫秒 clearBall(); / 清空棋子 flap+; / 计数当前棋子位置满足要求的个数 for(i=0;i8;i+) /画出一组解init2(&myBall,fai,fbi,W,ORGX,ORGY);drawBall(myBall); else / 否则全部输出92种解 delay(800); clearBall(); for(i=0;i8;i+) init2(&myBall,fai,fbi,W,ORGX,ORGY); drawBall(myBall); t+; /计数器，用来计算总共多少组解a=b=0;四、调试分析1. 程序初始界面：2. 随机移动到某点：3.按ENTER键，寻找包含当前棋子的解：4.按TAB键，显示全部92种解：五：软件说明书及设计总结1. 软件说明：用户运行程序，可自由移动棋子，当按ENTER键时，可显示包含当前用户选择棋子位所有八皇后的解，当显示完毕后，下方会输出八皇后解的总数以及当前坐标位置的解的个数。当按下TAB键时，屏幕以800毫秒的延时显示全部92种八皇后的解。当用户按ESC键时，退出本程序。2. 总结：本程序虽然能显示所有摆法，但是还是有很多不足的地方，比如不能够多姿多彩的显示，由于自己本身编程能力问题，以及时间问题，许多细节并不是处理的很好，使得程序的功能并不是很丰富，界面也不是很美观，但是本程序也有其优点：简洁、明了，易于操作，并且可以把所有的解一目了然的输出直观的显示出来。在实际操作过程中对犯的一些错误还会有意外的收获，对老师上课所讲的一些函数的应用更有了深刻的理解，这次实训是老师给了范例程序，经过自己的改写，基本实现了要求，以后会尽量自己动手去查资料等等。 六、附录：部分程序代码*START*#include #include #include #include #include bios.h#define ROW 8#define COL 8#define W 40#define H 40#define ORGX 50#define ORGY 50#define KEY_UP 0x4800#define KEY_DOWN 0x5000#define KEY_LEFT 0x4b00#define KEY_RIGHT 0x4d00#define ESC 0x11b#define ENTER 0x1c0d#define TAB 0xf09int o=0,p=0,fam=0,flap=0;int xx=3,xy=3,t=0,we=0;int fa10=0,1,2,3,4;int fb10=3,1,6,2,5;int chess88=0;int str20;void outputa();void *buff1;void drawBlock(int i,int j);typedef structint r,c;int h,w;int startX,startY;enum Direction dir;Ball;void init() int gdriver,gmode; gdriver = DETECT; initgraph(&gdriver,&gmode, ); cleardevice();void drawTable() int i,j,size; for(i=0;iROW;i+) for(j=0;jr=r;ball-c=c;ball-h=ball-w=size;ball-startX=x0;ball-startY=y0;void drawBall(Ball ball)int x0,y0; x0=ball.startX+ball.c*ball.w+ball.w/2;y0=ball.startY+ball.r*ball.h+ball.h/2;setcolor(RED);setfillstyle(1,RED);fillellipse(x0,y0,10,10);void changeDir(Ball *ball,enum Direction dir) ball-dir=dir;void move(Ball *ball,int rols,int cols)switch(ball-dir)case KEY_UP:ball-r-;if(ball-rr = rols-1;break;case KEY_DOWN:ball-r+;if(ball-r=rols) ball-r=0;break;case KEY_LEFT:ball-c-;if(ball-cc = cols-1;break;case KEY_RIGHT:ball-c+;if(ball-c=cols) ball-c=0;break; void clearBall() putimage(50,50,buff1,COPY_PUT);void queen(int i)int j;if(i=8)outputa();elsefor(j=0;j8;j+)chessij=1;if(!canAttack(i,j) queen(i+1);chessij=0;int canAttack(int i,int j)int m,n;for(m=0;mi;m+)for(n=0;n8;n+)if(chessmn=1)if(m=i|n=j) return 1;if(m+n=i+j|m-n=i-j) return 1; return 0;void outputa()Ball myBall;int i,j,a=0,b=0;for(i=0;i8;i+)for(j=0;j8;j+)if(chessij=1) faa+=i; fbb+=j;if(fam=0) for(i=0;i8;i+) if(fai=xx&fbi=xy) delay(800); clearBall(); flap+; for(i=0;i8;i+)init2(&myBall,fai,fbi,W,ORGX,ORGY);drawBall(myBall); else delay(800); clearBall(); for(i=0;i8;i+) init2(&myBall,fai,fbi,W,ORGX,ORGY); drawBall(myBall); t+;a=b=0;void fun(Ball ball)xx=ball.r;xy=ball.c;int main()int key;