八皇后问题的解决完整文档.doc

淮阴工学院 数据结构课程设计报告数据结构课程设计报告 设计题目设计题目： 八 皇 后 系（院）系（院）: 计 算 机 工 程 系 专专 业：业： 信 息 安 全 班班 级：级： 信 息 1 0 6 学生姓名学生姓名: : 叶 青 学学 号号: 1061303127 指导教师指导教师: 张亚红 寇海洲 胡荣林 夏森 学年学期学年学期: 2007 2008 学年 第 2 学期 2008年 6 月 25 日 设计任务书设计任务书 课题课题 名称名称 八 皇 后 设计设计 目的目的 1.用 c+语言平台将一个的棋盘上放上个皇后，使得每一个皇后既 攻击不到另外七个皇后，也不被另外七个皇后所攻击的 92 种结构予以实 现 2. 通过这次课程设计,提高自己的编程能力,熟悉 c+的编程坏境,为以后的程 序开发打下基础. 实验实验 环境环境 1） 系统要求：win98以上操作系统； 2） 语言平台：tc+或vc+6.0； 3） 执行文件：八皇后.exe 任务任务 要求要求 试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法， 并给出所有的解。 工作进度计划工作进度计划 序号序号起止日期起止日期工工 作作 内内 容容 12008.6.232008.6.24查阅相关内容 22008.6.242008.6.25编写代码及实习报告 32008.6.252008.6.26完善课程设计报告 42008.6.262008.6.27答辩 指导教师（签章）：指导教师（签章）： 2008 年年 6 月月 30 日日 摘要： 八皇后问题要求在一个的棋盘上放上个皇后，使得每一个皇后既攻击不 到另外七个皇后，也不被另外七个皇后所攻击按照国际象棋的规则，一个皇后可以 攻击与之处在同一行或同一列或同一斜线上的其他任何棋子因此，八皇后问题等于 要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c+语言平台将一个的棋盘上放上个皇后， 使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予 以实现 使用递归方法最终将其问题变得一目了然，更加易懂。 关键词： 八皇后 ; c+ ; 递归法 目目 录录 1. 课题综述课题综述.1 1. 1 课题的来源及意义 .1 1. 2 面对的问题.1 2. 需求分析需求分析.1 2. 1 涉及到的知识.1 2. 2 软硬件的需求.1 2. 3 功能需求.2 3. 概要设计概要设计.2 4. 详细设计和实现详细设计和实现.2 4. 1 算法描述及详细流程图.2 4.1.1 算法描述.3 4.1.2 算法流程图.3 5. 代码编写及详细注释代码编写及详细注释.4 6. 程序调试程序调试.7 6. 1 调试过程、步骤及遇到的问题 .7 7. 运行与测试运行与测试.7 7.1 运行演示.7 总总 结结.9 致致 谢谢.10 参考文献参考文献.11 . . 1 1. 课题综述课题综述 1. 1 课题的来源及意义课题的来源及意义 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯 1850 年提出的。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同 一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出 了一个问题：在 8*8 的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意 两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。 到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自 然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和 提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后 的编程开个好头，故我选择了这个有趣的课题。 1. 2 面对的问题面对的问题 1） 解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第 I 行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要 把以 I 为下标的标记置为被占领状态； 2） 使用数据结构的知识，用递归法解决问题。 2. 需求分析需求分析 2. 1 涉及到的知识涉及到的知识 本次课程设计中，用到的主要知识有：递归法的运用，for 语句的灵活运用，数 据结构中树知识的灵活运用、栈及数组的掌握。 2. 2 软硬件的需求软硬件的需求 2 1）系统要求：win98 以上操作系统； 2) 语言平台：tc+或 vc+6.0； 2. 3 功能需求功能需求 当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比较直观 的界面显示。 3. 概要设计概要设计 本课件学生是用循环递归循环来实现的，分别一一测试了每一种摆法，并把它 拥有的 92 种变化表现出来。在这个程序中，我的主要思路以及思想是这样的： 1）解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第 I 行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要 把以 I 为下标的标记置为被占领状态； 对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角 线。在同一对角线上的所有点（设下标为(i,j)） ，要么(i+j)是常数，要么(i-j)是常数。 因此，当第 I 个皇后占领了第 J 列后，要同时把以(i+j)、(i-j)为下标的标记置为被占 领状态。 2）数据结构的实现 而对于数据结构的实现，学生则是着重于: 数组 aI：a I表示第 I 个皇后放置的列；I 的范围：1.8; 对角线数组：bj(主对角线),cj（从对角线） ，根据程序的运行，去决定主从对 角线是否放入皇后； 4. 详细设计和实现详细设计和实现 4. 1 算法描述及详细流程图算法描述及详细流程图 3 4.1.1 算法描述算法描述 A、 数据初始化。 B、 从 n 列开始摆放第 n 个皇后（因为这样便可以符合每一竖列一个皇后的要 求） ，先测试当前位置（n，m）是否等于 0（未被占领） 。如果是，摆放第 n 个皇后， 并宣布占领（记得姚横列竖列斜列一起设置） ，接着进行递归；如果不是，测试下一 个位置（n，m+1） ，但是如果当 n8 时，便打印出结果。 E、输出函数我使用 printf 输出，运行形式为：第 m 种方法为：* * * * * * * * 4.1.2 算法流程图算法流程图 4 5. 代码编写及详细注释代码编写及详细注释 #include #include #include #include #include #define QUEENS 8 int iCount = 0; /!记录解的序号的全局变量。 int SiteQUEENS; /!记录皇后在各行上的放置位置的全局数组。 5 void Queen(int n); /!递归求解的函数。 void Output();/!输出一个解。 int IsValid(int n); /!判断第 n 个皇后放上去之后，是否有冲突。 void main() /*-Main：主函数。- -*/ system(title 叶青-递归算法八皇后问题 ); cout 八皇后的解法：endl; cout -endl; Queen(0); /!从第 0 行开始递归试探。 getch();/!按任意键返回。 void Queen(int n) /*-Queen：递归放置第 n 个皇后，程序 的核心!-*/ int i; if(n = QUEENS) /!参数 n 从 0 开始，等于 8 时便试出了一个解，将它输出并 回溯。 Output(); return; for(i = 1 ; i = QUEENS ; i+) /!n 还没到 8，在第 n 行的各个行上依次试 探。 6 Siten = i; /!在该行的第 i 行上放置皇后。 if(IsValid(n) /!如果放置没有冲突，就开始下一行的试探。 Queen(n + 1); int IsValid(int n) /*-IsValid：判断第 n 个皇后放上去之后，是否合法， 即是否无冲突。-*/ int i; for(i = 0 ; i n ; i+) /!将第 n 个皇后的位置依次于前面 n1 个皇后的 位置比较。 if(Sitei = Siten) /!两个皇后在同一列上，返回 0。 return 0; if(abs(Sitei - Siten) = (n - i) /!两个皇后在同一对角线上，返回 0。 return 0; return 1; /!没有冲突，返回 1。 void Output()/*-Output：输出一个解，即一种没有冲突的放置方 案。-*/ int i; printf(No.%-5d , +iCount); /!输出序号。 7 for(i = 0 ; i QUEENS ; i+)/!依次输出各个行上的皇后的位置，即所在的 列数。 printf(%d , Sitei); printf(n); 6. 程序调试程序调试 6. 1 调试过程、步骤及遇到的问题调试过程、步骤及遇到的问题 在完整程序调试时遇到几个小问题，后经细心改正后才把调试工作做完。 例如:当用 printf 输出时,出现了一些错误,几经调试后,发现原来是缺少了 stdio.h 这样一个头文件,添加了头文件后, 还出现了一些问题,逻辑错误导致程序死循环或不 循环或循环一小部分,但是编译时却没有错误,就是没有正确的输出答案,一开始我也 不知道是怎么回事,通过和同学的交流,发现是逻辑错误,经过改正后,程序终于可以运 行了. 7. 运行与测试运行与测试 7.1 运行演示运行演示 8 9 总 结 通过了 19 周这个星期的程序设计，我从中得到了许多的经验以及软件设计的一 些新的思路；从这个八皇后问题设计以及分析中，本人从中理解到了数据结构对于计 算机软件设计的重要性，它的使用，可以改变一个软件的运行周期，也可以将软件的 思路从繁化简，并且都能够通过数据结构的相关引导，将本身以前编程思想进行扩充， 发展；这也是在这次课程设计中我所掌握得到的。 但由于我的基本知识还不是那么扎实，也缺乏对软件设计的经验，在这过程中也 出现了一些问题，如，八皇后在变成初期由于没真正体会到数据结构中“树”在里面的 运用，将程序往大一时 c 语言的方向发展，不自觉的采用了非递归的算法，结果大大 增加了程序的复杂程度。并且也让整个程序的时间复杂度变得更大；在后来学生对数 据结构的第六章进行了比较深入的研读，才发现了数据结构树的实际运用的空间是相 当的大，并且，通过了重温树的回溯，以及二叉树的遍历，最终将程序进行了一次较 大的改造。并且通过思考，再将以前的数组知识加以运用才最终解决了这个问题，整 个程序的算法的可看性也有了相当的改进。 课程设计随着时间的推移，也即将结束了，但这个学期数据结构的学习还是具有 相当大的意义，它从一个程度上改变了我们的编程思想，如何将一个程序快速而又准 备的进行编写，进行编译，都成为了我们思考的重点，也通过这一个学期的学习，我 们将数据结构的思想带入到了我们以后的编程学习中去。在这个阶段，我也明白了， 好的思想，不能提留于字面上的认知，还需要的是平时多练多写一些相关的程序，并 且通过修改，加入新的算法去尝试改变自己的一些编程思想。保持更新算法的速度， 这才是关键。 课程设计已经接近尾声了，但它给我的不只是程序设计上的满足，更重要的是对 自己编程思想的一次更新，以及对算法的一个全新的认识！ 我觉得还可以考虑开发 N 皇后问题,在主界面中添加一个 int 型的变量,程序一开 始要求输入一个数(确定是几皇后问题),输入后按下 enter 后,输出各种解.主程序与八 皇后的求解大体相同. 10 致 谢 在这次课程设计中,我遇到了不少问题,包括程序上的和课程设计的撰写上的,同学 曾给过我许多帮助,在此我表示对他们的忠心感谢。同时，指导老师和实验人员给了我 很多上机的机会，给了我一个做课程设计的很好的条件，我才能够顺利的完成，在此， 我仅以文字的形式表示忠心感谢，感谢他们这么多天对我的帮助。 11 参考文献 1 苏仕华,数据结构课程设计.-北京:机械工业出版社,2005.5 2 于永彦,赵建洋.课程设计指导书.淮安：江苏淮阴工学院 计算机工程系,2006 3 刘振安,刘燕君，孙忱. C+语言课程设计.北京：高等教育出版社,2003 4 陈志泊, 张海燕, 王春玲. Visual C+程序设计. 中国铁道出版社 ,2005 5 吕凤哲,C+语言程序设计（第二版）.北京：电子工业出版社,2005 6 殷人昆，陶永雷等.数据结构（用面向对象方法与 C+ ）.北京:清华大学出版社， 1999 7 严蔚敏，吴伟民，数据结构北京：清华大学出版社，1997 8 李春葆.数据结构考研指导.北京:清华大学出版社,2002 9 陈慧南数据结构C+语言描述北京：人民邮电出版社，200503 12 指导教师评语指导教师评语 学号1061303127姓名叶 青班级信 息 106 选题 名称 八 皇 后 序号评价内容 权重 （%） 得分