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

1、计算机与软件工程学院课程设计说明书课程名称：数据结构与算法-课程设计课程代 码:106014389题目：四、八、n皇后问题学生姓名 学 号 开始时间 完成时间年级/专业/班：3120120806" 523年月日年月日课程设计成绩:学习态度及平 时成绩(30)技术水平与实际 能力(20)创新(5)说明书撰写质量(45)分00)总(1指导教师签名:年 月 日八皇后问题摘要解决八皇后问题主要利用了递归法、回溯法，以及对for语句、数据结构中 树的灵活运用、和对栈及数组的掌握。编程实现了在8*8的格的国际象棋上摆放 八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或 同一

2、条斜线上面。编程实现了任意给定一个初始位置，输出八皇后问题的一个布 局。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通 能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题 和解决问题的作风和能力。关键词：递归法；回溯法；顺序栈；数组；117结论八皇后问题1需求分析42开发及运行平台53概要设计64详细设计85调试分析96测试结果106. 1遇到的问题106.2调试结果10c "d:vc64-+vc+6.0_win8myprojects123debug123.exe"请输入皇后数n：40,11,32, 03,2b,21,02, 33,1

3、press any key to continue通过这次的课程设计，让我了解了八皇后这一经典的问题。同时让我更好地掌握了栈思想以及一维 数组等等知识，以及一些书本上没有的东西,这对我以后的学习生涯以及将来步入社会起到很大的帮 助。这次课程设计虽然花了我很多时间和精力，但很值得，因为它对我能力提高起到很大帮助。这次 课程设计也提醒我以前知识的匮乏，它给我敲响了警钟，让我意识到自己基础的不扎实当然这次实 验还是有很多问题的。比如程序设计的界面不够好，一些程序并非自己所写，而是修改某些程序而成,但这些不该，在下次课程设计时不会再发生。1213附录参考文献八皇后问题1需求分析八皇后问题是一个古老而著

4、名的问题，该问题是十九世纪著名的数学家高斯1850 年提出的，并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能 有76种不同的放法，这就是有名的“八皇后”问题。在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列 或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问 题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不 能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八 皇后问题有92个解答。本次课设要求指定任一初始位置，即可输出八皇后问题的所有行列布局。拓展完成 四皇后冋题。2开

5、发及运行平台运行平台:windos98/2000以上开发平台：microsoft visual c+ 6. 0八皇后问题3概要设计3.1结构设计理念（1）从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后 的要 求），先测试当前位置（n, m）是否等于0 （未被占领）。如果是，摆放第n个皇后， 并宣布占领，接着进行递归；如果不是，测试下一个位置（n, ni+1）,但是如果当*=8, m二8时，发现此时己无法摆放时，便要进行回溯。从问题的某一种可能岀发，搜索从这 种情况能出发，继续搜索，这种不断“回溯”的寻找解的方法，称为“回溯法”。（2）使用数组实现回溯法的思想。（3）当n8时,便打

6、印出结果。3. 2类设计类定义：class类名细节（数据成员，成员函数）；类函数定义：返回类型 类名：函数名（形参表）函数体；设计类eightqueen,利用类的成员函数find求解。用数据s1.8表示顺序栈，栈的下标表示皇后所在的行号，栈的内容表示所在 列号。用aj,bi+j,ci-j三个布尔数组（初值为真）检查皇后是否在列、主对角线、 从对角线上冲突。aj=o,bhj=o,ci-j=o表示未冲突。aj=l表示j列冲突（范 围1-8） , bi+j二1表示第i+j条对角线/冲突（范围-7-7）,若ci-j=l表示第i-j 条对角线、冲突（范围2-16） o如在（1,j）上放置皇后,若满足 a

7、j&&bi+j&&ci-j,则安全。这个程序主要由4个模块组成，分别是画棋盘模块，画皇后模块，输出皇后摆法模八皇后问题块，和解决如何摆置皇后模块。这4个模块隶属于主函数模块。八皇后问题4详细设计find将实现算法：置当前行、列均为1；while (当前行号二8)检查当前行，从当前列起逐列试探，寻找安全列号：if (找到安全列)放置皇后，列号记入栈中，并将下一行当作当前行，第一列当 当前列；else退栈回溯到上一行，移去该行已放置的皇后，以该皇后所在列的下一列为当 前列；class eightqueenprivate：int a9, b17, c17;int s9

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

9、况都输出时，前面的儿十种情况无法看到，要想让摆放皇后的图形和所在具体的位 置一起输出，就得修改程序让使她们一个一个地输出，这样显然比较麻烦。倘若有一种 既能把八皇后的所在位置和把皇后所有情况连续输出，我感觉就应该算是一个完美的程 序了，这还需要我一致的探索发掘下去才行。八皇后问题6测试结果6. 1遇到的问题1）运行时有些函数的头文件未定义，导致无法进行编译；而且在调试时有些头文件 的使用范畴弄混淆了；2）如果将92种情形全部打印，则前面的几十种情况将无法显示出，要想看到前面 的状态，必须添加一个控制语句，使其能一个一个的输岀。6. 2调试结果八皇后问题结果如图1所示:' -d:vc6+

10、vc+6.0_win8myprojectsquestionqueendebugquestionqueen.exe" x列号72631485/解 83行号:12345678洌号：1173168524 解 84112345678洌号：73825164/解 85彳丁号12345678列号:74258136/解 86/二 o 仃冇：12345678列号：74286135/解 87行号：12345678列号：75316824 解 88行号212345678列号:82417536/解 89彳亍号：12345678列号：82531746/解 90行号：12345678列号：83162574 解 9

11、1厶二o 仃f12345678列号：84136275/解 92pressany key tocontinuer叟狗拼音输入法全：vni v八皇后问题四皇后问题结果如图2所示:i£3 "d:vc6+vc+6.0_win8myprojects123debug123.exe"请输入皇后数n：40, 11,3 2, 03, 20, 21,0 2, 33, 1pressany key tocontinue八皇后问题7结论通过这次的课程设计，让我了解了八皇后这一经典的问题。同时让我更好地掌握了 栈思想以及一维数组等等知识，以及一些书本上没有的东西，这对我以后的学习生涯以 及将

12、来步入社会起到很大的帮助。这次课程设计虽然花了我很多时间和精力，但很值得, 因为它对我能力提高起到很大帮助。这次课程设计也提醒我以前知识的匮乏，它给我敲 响了警钟，让我意识到自己基础的不扎实当然这次实验述是有很多问题的。比如程序设 计的界面不够好，一些程序并非自己所写，而是修改某些程序而成，但这些不该，在下次 课程设计时不会再发生。八皇后问题参考文献1 苏仕华，数据结构课程设计，机械工业出版社2 王红梅，数据结构（c+版）第2版，清华大学出版社3 杨秀金，数据结构（c+版），人民邮电出版社八皇后问题源程序清单如下：头文件queen, h#i nc1ude<iostream>usin

13、g namespace std;class eightqueenprivate:int a，b17, c17;/定义棋盘大小int s9;public:void print ();void movequeen(int, int);void find() ; ;/定义成员函数void eightqueen:print() int k;static int num二0;cout«zzn 行号： 12345678n"cout<<，z 列号："；for(k=l;k<=8;k+) cout. width(4);cout<<sk;num二num+

14、1;cout«zz 解，«num«endl;void eightqueen:movequeen(int i, int j)aj=l;bi+j=l;ci-j+9=l;/输出一个解的成员函数 print ()； void eightqueen:find() int i,j;for(i二2;i=16;i+) i f(i >=2&& i <=9)ai-1=true:bi=true;ci=true; i=l;j=l;while(i>=l)/当i=0吋终止循环八皇后问题while(j<=8) if qj&&bi+j&am

15、p;&ci-j+9) break;/在当前行 1 上找安全位置j+;if(j<=8) aj二false;/找到安全位置i, jbi+j二false;ci-j+9二false;si = j；皇后位置j入栈if (i=8) print();/找到一个解,输出解 movequeen(i, j);/移去位置(i, j)上的皇后i； j=si ;movequeen(i, j); j+;elsei+;j二1;/准备放置下一个皇后elsei; if (i>=l)j=si ;movequeen(i, j) ; j+;源文件queen, cpp#inelude "queen. hv

16、oid main()eightqueen game; game. find();四、八、n皇后问题#include<iostream. h>#include<stdlib. h>void quoe n(int i, int n, int * col, int * md, int * sd, int *q) for (int j二o;jn;j+)if(!colj&&!mdn+i-j-l&&!sdi+j) colj=mdn+i-j-l=sdi+j=l;qi二j;int time二0;if(i=n-l)for(int k二0;kn;k+)八皇后问题cout«k<<z，, /<<qk<<，/“；cout<<endl;el se queen(i+1, n, colsd, q);colj二mdn+i