八皇后问题课程设计报告.docx
- 文档编号:13804164
- 上传时间:2023-06-17
- 格式:DOCX
- 页数:14
- 大小:254.76KB
八皇后问题课程设计报告.docx
《八皇后问题课程设计报告.docx》由会员分享,可在线阅读,更多相关《八皇后问题课程设计报告.docx(14页珍藏版)》请在冰点文库上搜索。
八皇后问题课程设计报告
课程设计题目:
名称:
八皇后问题内容:
设计程序完成如下要求:
在8×8的国际象棋棋盘上,放置8个皇后,使得这8个棋子不能互相被对方吃掉。
要求:
(1)依次输出各种成功的放置方法。
(2)最好能画出棋盘的图形形式,并在其上动态地标注行走的过程。
(3)程序能方便地移植到其他规格的棋盘上。
一、问题分析和任务定义
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。
该问题是十九世纪著名的数学家高斯1850年提出:
在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,根据国际象棋的规定,皇后可以攻击与它在同一行、同一列或者同一斜线上的棋子,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
在8!
=40320种排列中共有92种解决方案。
本程序需要解决的问题有:
1、建立合适的数据类型表示皇后在棋盘上所处的位置。
2、成功的输出全部正确的放置方法。
3、画出棋盘形式,在上面动态的标注其行走的过程。
二、数据结构的选择和概要设计
1、为了简单易行的表示皇后在棋盘所处的位置,在此建立一个整型数组queen[i]来表
示,若queen[3]=2则表示皇后处在8×8棋盘的第三行和第二列。
2、表示好皇后以后,设计judge()和check()函数来检测第一个皇后的同列和同斜线上有没有其他皇后(程序以行为基础,逐行试探每列和斜线上是否有皇后)。
然后设计输出函数show()和print()分别输出正确解法的排列形式和棋盘摆放形式。
在输出棋盘的步骤中,设计一个递归函数go()实现棋盘的输出。
3、程序的流程图如下图所示:
图1程序流程图
三、详细设计和编码
1、首先定义整型数组queen[i]表示皇后的位置,i的取值由0到7表示八个皇后。
然后定义一个整型变量count来统计所有正确解法的个数。
2、因为每行只能摆放一个皇后,所以在皇后不在同一行的基础上,设计检测函数检测皇后的同列和同斜线上是否存在其他皇后。
检测是否同列的时候,定义两个变量i和j表示
两个皇后所在的行数,则用queen[i]和queen[j]表示它们所在的列数,通过验证queen[i]和
queen[j]是否相等确定两个皇后是否处于同一列上。
检测同斜线的时候,用到了求绝对值的函数abs()函数,用abs(p[j]-p[i])==j-i是否相等来验证任意两个皇后是否在同一斜线上。
intjudge(int*p,intj)//检测皇后是否在同列或者同一斜线上
{inti;
//皇后在同一列上的情况
//皇后在同一斜线上的情况
for(i=0;i {if(p[j]==p[i])return0; if(abs(p[j]-p[i])==j-i)return0; } return1; } intcheck(intqueen[],inti)//检测棋盘布局是否合法 {intj,k; for(j=0;j<=i;j++) {for(k=0;k<=i;k++) {if(j! =k&&(queen[j]==queen[k]||abs(queen[j]-queen[k])==abs(j-k)))//皇后不在同一行且在同一列或者同一斜线时 {return0;} }} return1; } show()函数输出排列形式, for循环条件语句筛选可行方 3、设计输出函数输出八皇后问题的正确解法,首先编写 为了方便,将正确解法的判定条件编写在输出函数中,用多个 案,执行之后输出所有正确方法的排列形式和正确解法的个数。 然后编写print()函数输出棋盘形式,按行扫描,用for循环条件语句判定条件之后,皇后输出“Q”,非皇后位置输出 +”,在递归函数go()中调用print()函数可以完整的输出所有正确解法的棋盘形式。 voidshow(intqueen[]) {inti=0,j=0,amount=0; if(judge(queen,j))if(judge(queen,j))if(judge(queen,j))if(judge(queen,j))if(judge(queen,j))if(judge(queen,j)) for(queen[0]=0;queen[0]<8;j=0,queen[j]++)//按行开始逐行试探每一列上的皇后位置是否合法 for(queen[++j]=0;queen[j]<8;j=1,queen[j]++) for(queen[++j]=0;queen[j]<8;j=2,queen[j]++) for(queen[++j]=0;queen[j]<8;j=3,queen[j]++) for(queen[++j]=0;queen[j]<8;j=4,queen[j]++) for(queen[++j]=0;queen[j]<8;j=5,queen[j]++) for(queen[++j]=0;queen[j]<8;j=6,queen[j]++) {for(i=0;i<8;i++) printf("%d",queen[i]); //统计所有正确解法的个数 //输出正确解法的排列形式 ++amount; printf("\n");} printf("\nthereis%danswer\n",amount); //输出皇后在棋盘上的摆放形式 voidprint(intqueen[]){ inti,j; for(i=0;i<8;i++) {for(j=0;j {printf("+");} printf("Q");//输出Q表示皇后 for(j=7;j>queen[i];j--)//皇后后面输出"+" {printf("+");}; } printf("pressanykeytoshownextanswer: "); getchar();//接收字符 } 4、编写程序主函数,在main()中调用各个功能函数实现八皇后问题的要求,其中运用getchar()函数接收字符,设置按任意键继续的功能。 5、注: 本次课程设计主要运用VisualC++6.0的编译环境,无法使用清屏函数,在turboc的编译环境中,使用clrscr()清屏函数可以实现动态的输出皇后在棋盘上的摆放形式。 详细代码如下: printf("\n"); clrscr(); } 四、上机调试 本次课程设计中遇到了许多的困难,产生了不少的问题。 1、刚开始使用结构体表示皇后的位置,构造了较多的变量,程序设计中产生了许多的错误,判断同斜线情况不太方便,算法性能也不少很好。 后来想到运用数组来表示皇后的位置,不但数据结构简单,而且较容易的表示处皇后的位置,容易分析皇后同列、同斜线的情 况(用到abs()函数),所以建立整型数组来表示皇后在棋盘上的位置。 2、动态输出棋盘摆放形式的时候,自动输出的速度太快,无法观察清楚,后来只好运用getchar()函数接受一个空的字符手动控制棋盘的输出。 五、测试结果及其分析程序运行结果如下各图所示: 分析: 本次课程设计完成之后,仍觉得有些不足之处,例如无法让电脑自动输出动态 的摆放皇后过程,必须手动操作完成。 算法的时间复杂度也不是很好。 各函数的时间复杂度如下: intjudge(int*p,intj)intcheck(intqueen[],inti)voidshow(intqueen[])voidprint(intqueen[]) 时间复杂度为O(n) 时间复杂度为O(n2)时间复杂度为O(n9)时间复杂度为O(n2) voidgo(intqueen[],inti) 时间复杂度为O(n) 图2程序运行结果部分截图 (1) 图3程序运行结果部分截图 (2) 图4程序运行结果部分截图(3) 图5程序运行结构部分截图(4) 六、用户使用说明 执行.exe程序按照提示,按回车输出两种结果。 七、参考文献 【1】王昆仑李红.数据结构与算法.中国铁道出版社.2007年6月第一版.【2】何钦铭颜晖.C语言程序设计.高等教育出版社.2008年4月第一版. 八、附录 #include #include #include intcount=0;//定义一个整型变量count来统计正确解法的个数 intqueen[8];//定义数组表示皇后所处的位置(queen[3]=2表示皇后在第三行和第二列上) //检测皇后是否在同列或者同一斜线上 //皇后在同一列上的情况 }return1; } intcheck(intqueen[],inti)//检测棋盘布局是否合法 { intj,k; for(j=0;j<=i;j++) { for(k=0;k<=i;k++) {if(j! =k&&(queen[j]==queen[k]||abs(queen[j]-queen[k])==abs(j-k)))//皇后不在同一行且在同一列或者同一斜线时 {return0;} } } return1; } voidshow(intqueen[]) { inti=0,j=0,amount=0; for(queen[0]=0;queen[0]<8;j=0,queen[j]++)//按行开始逐行试探每一列上的皇后位置是否合法 for(queen[++j]=0;queen[j]<8;j=1,queen[j]++) if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=2,queen[j]++) if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=3,queen[j]++) if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=4,queen[j]++) if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=5,queen[j]++) if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=6,queen[j]++) if(judge(queen,j)) for(queen[++j]=0;queen[j]<8;queen[j]++) if(judge(queen,j)) {for(i=0;i<8;i++) printf("%d",queen[i]); //输出正确解法的排列形式 ++amount;//统计所有正确解法的个数printf("\n");} printf("\nthereis%danswer\n",amount); } voidprint(intqueen[])//输出皇后在棋盘上的摆放形式 { inti,j; for(i=0;i<8;i++) { for(j=0;j { printf("+"); } printf("Q");//输出Q表示皇后 for(j=7;j>queen[i];j--)//皇后后面输出"+"{ printf("+"); }; printf("\n"); } printf("pressanykeytoshownextanswer: ");getchar();//接收字符 } voidgo(intqueen[],inti)//递归函数 { if(i>=8) //一个棋盘上摆满8个皇后时 { count++; //统计一次方法 print(queen); //输出一个正确的解法 }else { intj; for(j=0;j<8;j++) { queen[i]=j;if(check(queen,i)){ go(queen,i+1); //函数递归 } } voidmain()//程序主函数 { printf("pressanykeytoshowtheanswer: \n"); getchar();show(queen); printf("pressanykeytoshowthechessboard: \n");//输出正确解法的棋盘形式getchar(); go(queen,0);//从第一个皇后开始递归操作 printf("thereis%danswer",count); printf("\n");getchar();
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 皇后 问题 课程设计 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)