数据结构课程设计-四、八、N皇后问题

1、1计算机与软件工程学院课程设计说明书课 程 名 称: 数据结构与算法-课程设计 课 程 代 码: 106014389 题 目: 四、八、N 皇后问题 年级/专业/班: 学 生 姓 名: 学 号: 312012080611523 开 始 时 间: 年 月 日完 成 时 间: 年 月 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日八皇后问题2摘摘 要要 解决八皇后问题主要利用了递归法、回溯法,以及对 for 语句、数据结构中树的灵活运用、和对栈及数组的掌握。编程实现了在 8*8 的格的国际象棋上摆放八个

2、皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面。编程实现了任意给定一个初始位置，输出八皇后问题的一个布局。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。关键词：关键词：递归法; 回溯法; 顺序栈；数组； 八皇后问题3目目 录录 1 需求分析需求分析.62 开发及运行平台开发及运行平台.73 概要设计概要设计.84 详细设计详细设计.105 调试分析调试分析.116 测试结果测试结果.126.16.1 遇到的问题遇到的问题.126.26.2 调试结果

3、调试结果.12.137 结论结论.14通过这次的课程设计，让我了解了八皇后这一经典的问题。同时让我更好地掌握了栈思想以及一维通过这次的课程设计，让我了解了八皇后这一经典的问题。同时让我更好地掌握了栈思想以及一维数组等等知识数组等等知识, ,以及一些书本上没有的东西，这对我以后的学习生涯以及将来步入社会起到很大的以及一些书本上没有的东西，这对我以后的学习生涯以及将来步入社会起到很大的帮助。这次课程设计虽然花了我很多时间和精力，但很值得帮助。这次课程设计虽然花了我很多时间和精力，但很值得, ,因为它对我能力提高起到很大帮助。因为它对我能力提高起到很大帮助。这次课程设计也提醒我以前知识的匮乏这次课程

4、设计也提醒我以前知识的匮乏, ,它给我敲响了警钟它给我敲响了警钟, ,让我意识到自己基础的不扎实让我意识到自己基础的不扎实. .当然这当然这次实验还是有很多问题的。比如程序设计的界面不够好，一些程序并非自己所写次实验还是有很多问题的。比如程序设计的界面不够好，一些程序并非自己所写, ,而是修改某些程而是修改某些程序而成序而成, ,但这些不该但这些不该, ,在下次课程设计时不会再发生。在下次课程设计时不会再发生。.14参考文献参考文献.15附附 录录.16八皇后问题41 需求分析八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯 1850年提出的,并作了部分解答。高斯在棋盘上放下

5、了八个互不攻击的皇后，他还认为可能有 76 种不同的放法，这就是有名的“八皇后”问题。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在 8*8 的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有 92 个解答。本次课设要求指定任一初始位置，即可输出八皇后问题的所有行列布局。拓展完成四皇后问题。八皇后问题52 开发及运行平台运行平台：Windos98/2000 以上开发平台：Microso

6、ft Visual C+ 6.0八皇后问题63 概要设计3.13.1 结构设计理念结构设计理念（1）从 n 列开始摆放第 n 个皇后（因为这样便可以符合每一竖列一个皇后 的要求），先测试当前位置（n，m）是否等于 0（未被占领）。如果是，摆放第 n 个皇后，并宣布占领，接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当n8 时，便打印出结果。3.23.2 类设计类设计类定义：class 类名细节（数据成员，成员函数）；类函数定义：返回类型 类名：函数名（形参表）函数体；设计类 eightqueen，利用类的成员函数 Find 求解。用数据 s1.8表示顺序栈，栈的下标表示皇后所在

7、的行号，栈的内容表示所在列号。用 aj,bi+j,ci-j三个布尔数组（初值为真）检查皇后是否在列、主对角线、从对角线上冲突。aj=0,bi+j=0,ci-j=0 表示未冲突。aj=1 表示 j 列冲突（范围 1-8），bi+j=1 表示第 i+j 条对角线冲突（范围-7-7），若 ci-j=1 表示第i-j 条对角线冲突（范围 2-16）。如在（i，j）上放置皇后，若满足 aj&bi+j&ci-j,则安全。八皇后问题7这个程序主要由 4 个模块组成，分别是画棋盘模块，画皇后模块，输出皇后摆法模块，和解决如何摆置皇后模块。这 4 个模块隶属于主函数模块。输出当前布局开始开始放第

8、一行的皇后检查是否放满未放满放置新皇后检测是否冲突不冲突，继续放下一行皇后冲突，移走刚才放置的皇后放满八皇后问题84 详细设计Find 将实现算法：置当前行、列均为 1；While（当前行号=8）检查当前行，从当前列起逐列试探，寻找安全列号：If（找到安全列）放置皇后，列号记入栈中，并将下一行当作当前行，第一列当当前列；else退栈回溯到上一行，移去该行已放置的皇后，以该皇后所在列的下一列为当前列；Class eightqueenPrivate：Int a9,b17,c17;int s9;Public:Void print();/输出结果Void find();/求一个解八皇后问题95 调试分

9、析在完整程序调试时由于太急于求成导致程序进行循环时出现无法运行的问题，逻辑错误导致程序死循环或不循环或循环一小部分，后经细心改正后才把调试工作做完。做程序真的不是三两下就能完美的做好的，正应了那句话“心急吃不了热豆腐啊”。 但对于这个程序我由于 c+语言学的不到位以至于有些掺杂了 c 语言的有关算法，要是都用 c+来编写就再好不过了。 在编写代码时，我希望能随机选择一数 X(192)后，能输出该种情况所对应的八个皇后的摆放方式和每个皇后所在的位置，但想了好久，就是无法实现。而且，当 92种情况都输出时，前面的几十种情况无法看到，要想让摆放皇后的图形和所在具体的位置一起输出，就得修改程序让使她们

10、一个一个地输出，这样显然比较麻烦。倘若有一种既能把八皇后的所在位置和把皇后所有情况连续输出，我感觉就应该算是一个完美的程序了，这还需要我一致的探索发掘下去才行。 八皇后问题106 测试结果6.16.1 遇到的问题遇到的问题1）运行时有些函数的头文件未定义，导致无法进行编译；而且在调试时有些头文件的使用范畴弄混淆了；2）如果将 92 种情形全部打印，则前面的几十种情况将无法显示出，要想看到前面的状态，必须添加一个控制语句，使其能一个一个的输出。6.26.2 调试结果调试结果八皇后问题结果如图 1 所示：图 1八皇后问题11四皇后问题结果如图 2 所示：图 2八皇后问题127 结论通过这次的课程设

11、计，让我了解了八皇后这一经典的问题。同时让我更好地掌握了栈思想以及一维数组等等知识,以及一些书本上没有的东西，这对我以后的学习生涯以及将来步入社会起到很大的帮助。这次课程设计虽然花了我很多时间和精力，但很值得,因为它对我能力提高起到很大帮助。这次课程设计也提醒我以前知识的匮乏,它给我敲响了警钟,让我意识到自己基础的不扎实.当然这次实验还是有很多问题的。比如程序设计的界面不够好，一些程序并非自己所写,而是修改某些程序而成,但这些不该,在下次课程设计时不会再发生。八皇后问题13参考文献1苏仕华，数据结构课程设计，机械工业出版社2王红梅，数据结构（C+版）第 2 版，清华大学出版社3杨秀金，数据结构

12、（C+版），人民邮电出版社八皇后问题14附附 录录源程序清单如下：头文件 queen.h#includeusing namespace std;class eightqueenprivate:int a9,b17,c17;/定义棋盘大小int s9;public:void print();void movequeen(int,int);void find();/定义成员函数void eightqueen:print()int k;static int num=0;coutn 行号： 1 2 3 4 5 6 7 8n;cout列号：;for(k=1;k=8;k+)cout.width(4);co

13、utsk;num=num+1;cout/解numendl;void eightqueen:movequeen(int i,int j)aj=1;bi+j=1;ci-j+9=1;/输出一个解的成员函数 print（）；void eightqueen:find()int i,j;for(i=2;i=2&i=1)/当 i=0 时终止循环八皇后问题15while(j=8)if(aj&bi+j&ci-j+9)break;/在当前行 1 上找安全位置j+;if(j=1)j=si;movequeen(i,j);j+;源文件 queen.cpp#include queen.hvoid

14、main()eightqueen game;game.find();四、八、四、八、N N 皇后问题皇后问题#include#includevoid Queen(int i,int n,int *col,int *md,int *sd,int *q) for(int j=0;jn;j+) if(!colj&!mdn+i-j-1&!sdi+j) colj=mdn+i-j-1=sdi+j=1; qi=j;int time=0; if(i=n-1)for(int k=0;kn;k+)八皇后问题16 coutk, qk ; coutendl; else Queen(i+1,n,col,md,sd,q); colj=mdn+i-j-1=s