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

《数据结构课程设计-四、八、N皇后问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、等等知识,以及一些书本上没有的东西，这对我以后的学习生涯以及将来步入社会起到很大的帮助。这次课程设计虽然花了我很多时间和精力，但很值得,因为它对我能力提高起到很大帮助。这次课程设计也提醒我以前知识的匮乏,它给我敲响了警钟,让我意识到自己基础的不扎实.当然这次实验还是有很多问题的。比如程序设计的界面不够好，一些程序并非自己所写,而是修改某些程序而成,但这些不该,在下次课程设计时不会再发生。14参考文献15附录164八皇后问题1需求分析八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。高斯在棋盘

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

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

6、n>8时，便打印出结果。3.2类设计类定义：class类名{细节（数据成员，成员函数）；}类函数定义：返回类型类名：：函数名（形参表）{函数体；}设计类eightqueen，利用类的成员函数Find求解。用数据s[1...8]表示顺序栈，栈的下标表示皇后所在的行号，栈的内容表示所在列号。用a[j],b[i+j],c[i-j]三个布尔数组（初值为真）检查皇后是否在列、主对角线、从对角线上冲突。a[j]=0,b[i+j]=0,c[i-j]=0表示未冲突。a[j]=1表示j列冲突（范围1-8），b[i+j]=1表示第i+j条对角线↗冲突（范围-7

7、-7），若c[i-j]=1表示第i-j条对角线↖冲突（范围2-16）。如在（i，j）上放置皇后，若满足a[j]&&b[i+j]&&c[i-j],则安全。17八皇后问题这个程序主要由4个模块组成，分别是画棋盘模块，画皇后模块，输出皇后摆法模块，和解决如何摆置皇后模块。这4个模块隶属于主函数模块。输出当前布局开始开始放第一行的皇后检查是否放满未放满放置新皇后检测是否冲突不冲突，继续放下一行皇后冲突，移走刚才放置的皇后放满17八皇后问题4详细设计Find将实现算法：置当前行、列均为1；While（当前行号<=8）{检查当前行，从当前列起逐列试探，

8、寻找安全列号：If（找到安全列）{放置皇后，列号记入栈中，并将下一行当作当前行，第一列当当前列；}else{退栈回溯到上一行，移去该行已放置的皇后，以该皇后所在列的下一列为当前列