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

.

2014年春季学期

《C项目设计》报告

题 目： 八皇后问题 学 号： 092213112 姓 名： 刘泽中 组 名： 1 指导教师： 宋东兴 日 期： 2014.05.15

.

目 录

正 文 ····················1.问题描述 ····················2. 总体设计与分析 ·················3. 相关代码 ····················4. 调试分析 ····················5.软件使用说明书 ················总结 ·····················附录：部分原程序代码 ·············

.

3 3 3 5 9 11 11 12

.

一、 问题描述

1. 八皇后问题:

是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出：在8×8棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？ 2.解决八皇后问题的关键在于：

（1）找到合理的数据结构存放棋子的摆放位置。 （2）要有合理的冲突检查算法。采用的方法是，先把8个棋子摆在棋盘上，每行摆一个，然后去检查这种摆放是否有冲突，如果没有冲突，即找到了一种解决方案。

由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正，这就是“回溯”的思想。在8个皇后未放置完成前，每行摆放一个皇后，摆放第i个皇后和第i+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。

二、总体设计与分析

1.设计效果

画一个8*8的国际象棋盘，在棋盘某一位置上放一棋子，并让它按从左到右的方向自动运动，用户可以使用光标键调整棋子运动的方向，找出所有可能的摆放方案，将包含指定的棋子的（如3行4列）摆放方案找出并显示出来。。 2.、总体设计

程序总体分为两大块：（1）八皇后摆法的寻找； （2）棋盘及棋子的设计。

3、详细模块

（1）八皇后摆法的寻找： int chess[8][8]={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;jif(!canAttack(i,j)) //如果当前布局合法,不受前i-1行的攻击

queen(i+1,n); //递归摆放i+1行

chess[i][j] = 0; //移走第i行，j列的棋子 }

}

.

.

}

int canAttack(int i,int j){ //判断0到i-1行已摆放的棋子，对[i,j]位置是否可以攻击

for(m=0;mfor(n=0;n<8;n++){

if(chess[m][n]==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;i<8;i++){ for(int j=0;j<8;j++){ if(chess[i][j]==1){

printf(\"(%d,%d)\ } } }

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:\\\c30\\\\bgi\"); cleardevice();

}

3. void drawTable(){ //画棋盘 int i,j,size;

for(i=0;idrawBlock(i,j); //画小方块

.

.

} }

size=imagesize(50,50,50+7*W+W-1,50+7*H+H-1); //计算大小，保存到缓存区

buff1=(void *)malloc(size);

getimage(50,50,50+7*W+W-1,50+7*H+H-1,buff1); //将整个棋盘保存的缓存区

}

4. void drawBlock(int i,int j){ //参数代表小方块在棋盘上的第i行，

第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); }

5. 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);

}

6. void move(Ball *ball,int rols,int cols){ //棋子移动 switch(ball->dir){

case KEY_UP:ball->r--;;if(ball->r<0) ball->r = rols-1;break;

case KEY_DOWN:ball->r++;if(ball->r==rols) ball->r=0;break; case KEY_LEFT:ball->c--;if(ball->c<0) ball->c = 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;j<8;j++){

chess[i][j]=1; //二维数组表示8*8棋盘（0代表该位没有放棋子）

if(!canAttack(i,j))//如果当前布局可行，不受i-1行的攻击 queen(i+1); //递归摆放i+1行

chess[i][j]=0; // 移走第i行，j列的棋子 } } }

12. int canAttack(int i,int j){// 判断0到i-1行已摆放的棋子，

对[i,j]位置是否可以攻击

int m,n;

for(m=0;mif(chess[m][n]==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;i<8;i++){ //输出一组解，坐标分别保存到两个数组里 for(j=0;j<8;j++){

if(chess[i][j]==1){ fa[a++]=i; fb[b++]=j; } } }

if(fam==0){ //判断是否为全部输出，fam为1时输出全部92种解 for(i=0;i<8;i++)

if(fa[i]==xx&&fb[i]==xy){ //如果有坐标与当前棋子坐标相同时 delay(800); //延时800毫秒 clearBall(); // 清空棋子

flap++; // 计数当前棋子位置满足要求的个数 for(i=0;i<8;i++){ //画出一组解

init2(&myBall,fa[i],fb[i],W,ORGX,ORGY); drawBall(myBall);

} } }

else { // 否则全部输出92种解 delay(800); clearBall();

for(i=0;i<8;i++){

init2(&myBall,fa[i],fb[i],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 0xf09

int o=0,p=0,fam=0,flap=0;

.

.

int xx=3,xy=3,t=0,we=0; int fa[10]={0,1,2,3,4}; int fb[10]={3,1,6,2,5}; int chess[8][8]={0}; int str[20]; void outputa(); void *buff1;

void drawBlock(int i,int j);

typedef struct{ int 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;isize=imagesize(50,50,50+7*W+W-1,50+7*H+H-1); buff1=(void *)malloc(size);

getimage(50,50,50+7*W+W-1,50+7*H+H-1,buff1); }

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 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; }

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->r<0) ball->r = rols-1;break;

case KEY_DOWN:ball->r++;if(ball->r==rols) ball->r=0;break;

case KEY_LEFT:ball->c--;if(ball->c<0) ball->c = 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(); else{

for(j=0;j<8;j++){ chess[i][j]=1;

if(!canAttack(i,j)) queen(i+1); chess[i][j]=0; } } }

int canAttack(int i,int j){ int m,n;

for(m=0;mif(chess[m][n]==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;i<8;i++){ for(j=0;j<8;j++){

if(chess[i][j]==1){ fa[a++]=i; fb[b++]=j; } } }

if(fam==0){

for(i=0;i<8;i++)

.

.

if(fa[i]==xx&&fb[i]==xy){ delay(800); clearBall(); flap++;

for(i=0;i<8;i++){

init2(&myBall,fa[i],fb[i],W,ORGX,ORGY); drawBall(myBall);

} } }

else {

delay(800); clearBall();

for(i=0;i<8;i++){

init2(&myBall,fa[i],fb[i],W,ORGX,ORGY); drawBall(myBall); } } t++; a=b=0; }

void fun(Ball ball){ xx=ball.r; xy=ball.c; }

int main(){ int key; int i;

Ball myBall; Ball ball; init();

drawTable();

init2(&myBall,3,3,W,ORGX,ORGY); drawBall(myBall); settextstyle(0,0,1); textcolor(RED); gotoxy(22,2);

printf(\"Eight Queens\"); while(1){

key = bioskey(0); switch(key){

.

.

case KEY_UP: changeDir(&myBall,KEY_UP);break; case KEY_DOWN:changeDir(&myBall,KEY_DOWN);break; case KEY_LEFT:changeDir(&myBall,KEY_LEFT);break; case

KEY_RIGHT:changeDir(&myBall,KEY_RIGHT);break; case ESC:exit(0); }

if(key==ENTER) { fun(myBall); fam=0; queen(0);

gotoxy(10,25);

printf(\"total = %d\ gotoxy(30,25);

printf(\"in(%d,%d) = %d\ flap=0; t=0; }

else if(key==TAB){ fam=1;queen(0); t=0; }

else {

clearBall();

move(&myBall,ROW,COL); drawBall(myBall); } } getch();

closegraph(); return 0; }

***************************THANKS****************************

.