八皇后问题地解决完整文档

1、实用文档淮阴工学院数据结构课程设计报告设计题目：八 皇 后2021 年 6 月 25 日设计任务书课题名称八皇后1.用C+语言平台将一个8夫8的棋盘上放上8个皇后,使得每一个皇后既设计 目的2.攻击不到另外七个皇后,也不被另外七个皇后所攻击的92种结构予以实现.通过这次课程设计,提升自己的编程水平,熟悉C+的编程坏境,为以后的程序开发打下根底.文案大全实用文档实验 环境D 系统要求： win98以上操作系统；2) 语言平台：tc+或vc+6.0；3) 执行文件：八皇后.exe任务 要求试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法,并给出所有的解.工作进度方案厅P起止日期工作

2、内容12021.6.232021.6.24查阅相关内容22021.6.242021.6.25编写代码及实习报告32021.6.252021.6.26完善课程设计报告42021.6.262021.6.27辩论指导教师(签章)：2021 年 6 月 30 日文案大全实用文档摘要:八皇后问题要求在一个8*8的棋盘上放上8个皇后,使得每一个皇后既攻击不 到另外七个皇后,也不被另外七个皇后所攻击.根据国际象棋的规那么,一个皇后可以 攻击与之处在同一行或同一列或同一斜线上的其他任何棋子.因此,八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上.而本课程设计本人的目的也是通过用 C+

3、语言平台将一个8*8的棋盘上放上8个皇 后,使得每一个皇后既攻击不到另外七个皇后,也不被另外七个皇后所攻击的92种结构予以实现.使用递归方法最终将其问题变得一目了然,更加易懂.关键词：八皇后；C+ ;递归法文案大全实用文档目 录1 .课题综述1.1.1 课题的来源及意义 11.2 面对的问题12 .需求分析1.2. 1涉及到的知识13. 2软硬件的需求14. 3功能需求25. 概要设计 2.6. 详细设计和实现2.4. 1算法描述及详细流程图 24.1.1 算法描述34.1.2 算法流程图 35 .代码编写及详细注释4.6 .程序调试7.6 . 1调试过程、步骤及遇到的问题 77 .运行与测试

4、.7.7.1 运行演示7总 结9.致 谢1Q参考文献11文案大全实用文档1.课题综述1. 1课题的来源及意义八皇后问题是一个古老而著名的问题,该问题是十九世纪著名的数学家高斯1850年提出的.在国际象棋中,皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同 一列或同一斜线正斜线或反斜线上时,它就能把对方棋子吃掉.所以高斯提出 了一个问题：在8*8的格的国际象棋上摆放八个皇后,使其不能相互攻击,即任意 两个皇后都不能处于同一列、同一行、或同一条斜线上面,问共有多少种解法.到了现代,随着计算机技术的飞速开展,这一古老而有趣的数学游戏问题也自 然而然的被搬到了计算机上.运用所学计算机知识来试着解

5、决这个问题是个锻炼和 提升我自己编程水平和独立解决问题水平的好时机,可以使我增强信心,为我以后 的编程开个好头,故我选择了这个有趣的课题.1. 2面对的问题1 解决冲突问题：这个问题包括了行,歹两条对角线；歹|：规定每一列放一个皇后,不会造成列上的冲突；行：当第I行被某个皇后占领后,那么同一行上的所有空格都不能再放皇后,要 把以I为下标的标记置为被占领状态；2使用数据结构的知识,用递归法解决问题.2 .需求分析2. 1涉及到的知识本次课程设计中,用到的主要知识有：递归法的运用,for语句的灵活运用,数 据结构中树知识的灵活运用、栈及数组的掌握.2. 2软硬件的需求文案大全实用文档1系统要求：w

6、in98以上操作系统；2语言平台：tc+或vc+6.0;2 . 3功能需求当运行程序时,在屏幕上显示每一种方法八个皇后的相对位置,要用比拟直观 的界面显示.3 .概要设计本课件学生是用循环递归循环来实现的,分别一一测试了每一种摆法,并把它 拥有的92种变化表现出来.在这个程序中,我的主要思路以及思想是这样的：1解决冲突问题：这个问题包括了行,歹I,两条对角线；歹I：规定每一列放一个皇后,不会造成列上的冲突；行：当第I行被某个皇后占领后,那么同一行上的所有空格都不能再放皇后,要 把以I为下标的标记置为被占领状态；对角线：对角线有两个方向.在这我把这两条对角线称为：主对角线和从对角 线.在同一对角

7、线上的所有点设下标为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.1 1算法描述及详细流程图文案大全实用文档4.1.2 算法描述A、数据初始化.B、从n列开始摆放第n个皇后由于这样便可以符合每一竖列一个皇后的要 求,先测试当前位置n, m是否等于0 未被占领.如果是,摆放第n个皇后

8、, 并宣布占领记得姚横列竖列斜列一起设置,接着进行递归；如果不是,测试下一 个位置n, m+1,但是如果当n<=8, m=8时,发现此时已无法摆放时,便要进行 回溯.从问题的某一种可能出发,搜索从这种情况能出发,继续搜索,这种不断回溯的寻找解的方法,称为 回溯法.C、使用数组实现回溯法的思想.D、当n>8时,便打印出结果.E、输出函数我使用printf输出,运行形式为：第 m种方法为：* * * * * * * *4.1.3 算法流程图开始卜从n箱摆放第工七皇后门数据初始化:文案大全实用文档5 .代码编写及详细注释#include <conio.h>#include &

9、lt;math.h>#include <stdlib.h>#include <stdio.h>#include <iostream.h>#define QUEENS 8int iCount = 0; /!记录解的序号的全局变量int SiteQUEENS; /!记录皇后在各行上的放置位置的全局数组文案大全实用文档void Queen(int n); /!递归求解的函数.void Output();/! 输出一个解.int IsValid(int n);/!判断第n个皇后放上去之后,是否有冲突.void main() /*Main: 主 函 数.*/ s

10、ystem("title 叶青递归算法八皇后问题");cout<<""<<"八皇后的解法："<<endl;cout<<" "<<""<<endl;Queen(0); /! 从第0行开始递归试探.getch();/! 按任意键返回.void Queen(int n) /*Queen: 递归放置第 n个皇后,程序的核心!*/ int i;if(n = QUEENS) /!参数n从0开始,等于8时便试出了一个解,将它输出并 回溯.

11、 Output(); return; for(i = 1 ; i <= QUEENS ; i+) /!n还没到8,在第n行的各个行上依次试探.文案大全实用文档 Siten = i; /!if(IsValid(n) /!Queen(n + 1); int IsValid(int n) /*即是否无冲突.*/ int i;for(i = 0 ; i < n ; i+) /!位置比拟. if(Sitei = Siten) /!return 0;if(abs(Sitei - Siten) = (n - i) /!0oreturn 0; return 1; /!没有冲突,返回1void Ou

12、tput()/*Output案.*/int i;printf("No.%-5d", +iCount); /!在该行的第i行上放置皇后.如果放置没有冲突,就开始下一行的试探.IsValid :判断第n个皇后放上去之后,是否合法,将第n个皇后的位置依次于前面n-1个皇后的两个皇后在同一列上,返回0两个皇后在同一对角线上,返回:输出一个解,即一种没有冲突的放置方输出序号文案大全实用文档for(i = 0 ; i < QUEENS ; i+)/!依次输出各个行上的皇后的位置,即所在的列数.printf("%d " , Sitei);printf("

13、;n");6 .程序调试6.1 调试过程、步骤及遇到的问题在完整程序调试时遇到几个小问题,后经细心改正后才把调试工作做完.例如:当用printf输出时,出现了一些错误,几经调试后,发现原来是缺少了 stdio.h 这样一个头文件,添加了头文件后,还出现了一些问题,逻辑错误导致程序死循环或 不循环或循环一小局部,但是编译时却没有错误,就是没有正确的输出答案,一开始我 也不知道是怎么回事,通过和同学的交流,发现是逻辑错误,经过改正后,程序终于可以 运行了.7 .运行与测试7.1 运行演示文案大全实用文档文案大全实用文档通过了 19周这个星期的程序设计,我从中得到了许多的经验以及软件设计的

14、一 些新的思路；从这个八皇后问题设计以及分析中,本人从中理解到了数据结构对于计 算机软件设计的重要性,它的使用,可以改变一个软件的运行周期,也可以将软件的 思路从繁化简,并且都能够通过数据结构的相关引导,将本身以前编程思想进行扩充, 开展；这也是在这次课程设计中我所掌握得到的.但由于我的根本知识还不是那么扎实, 也缺乏对软件设计的经验,在这过程中也 出现了一些问题,如,八皇后在变成初期由于没真正体会到数据结构中树在里面的运用,将程序往大一时c语言的方向开展,不自觉的采用了非递归的算法,结果大大 增加了程序的复杂程度.并且也让整个程序的时间复杂度变得更大；在后来学生对数 据结构的第六章进行了比拟

15、深入的研读, 才发现了数据结构树的实际运用的空间是相 当的大,并且,通过了重温树的回溯,以及二叉树的遍历,最终将程序进行了一次较 大的改造.并且通过思考,再将以前的数组知识加以运用才最终解决了这个问题,整 个程序的算法的可看性也有了相当的改良.课程设计随着时间的推移,也即将结束了,但这个学期数据结构的学习还是具有 相当大的意义,它从一个程度上改变了我们的编程思想,如何将一个程序快速而又准 备的进行编写,进行编译,都成为了我们思考的重点,也通过这一个学期的学习,我 们将数据结构的思想带入到了我们以后的编程学习中去.在这个阶段,我也明白了, 好的思想,不能提留于字面上的认知,还需要的是平时多练多写

16、一些相关的程序,并 且通过修改,参加新的算法去尝试改变自己的一些编程思想.保持更新算法的速度, 这才是关键.课程设计已经接近尾声了,但它给我的不只是程序设计上的满足,更重要的是对 自己编程思想的一次更新,以及对算法的一个全新的熟悉！我觉得还可以考虑开发N皇后问题,在主界面中添加一个int型的变量,程序一开 始要求输入一个数确定是几皇后问题,输入后按下enter后,输出各种解.主程序与八 皇后的求解大体相同.文案大全实用文档在这次课程设计中,我遇到了不少问题,包括程序上的和课程设计的撰写上的,同学 曾给过我许多帮助,在此我表示对他们的忠心感谢.同时,指导老师和实验人员给了我 很多上机的时机,给了

17、我一个做课程设计的很好的条件, 我才能够顺利的完成,在此, 我仅以文字的形式表示忠心感谢,感谢他们这么多天对我的帮助.文案大全实用文档参考文献1苏仕华,数据结构课程设计.-北京:机械工业出版社,2005.52于永彦,赵建洋.课程设计指导书.淮安：江苏淮阴工学院 计算机工程系,20063刘振安,刘燕君,孙忱.C+语言课程设计.北京：高等教育出版社,20034陈志泊,张海燕,王春玲.Visual C+程序设计.中国铁道出版社,20055吕凤哲,C+语言程序设计第二版.北京：电子工业出版社,20056殷人昆,陶永雷等.数据结构用面向对象方法与C+ .北京：清华大学出版社, 19997严蔚敏,吴伟民,数据结构.北京：清华大学出版社,19978李春葆.数据结构一考研指导.北京:清华大学出版社,20029陈慧南.数据结构一C+胡言描述.北京：人民邮电出版社,2005. 03文案大全实用文档指导教师评语学号1061303127姓名叶青班级信息106选题 名称八 皇 后序号评价内