八皇后课程设计报告

PAGE目录TOC\o"1-1"\h\z\u一绪论 1二需求分析 1三概要设计 2四详细设计 3五调试分析 4六用户使用说明 5七测试结果 5小结 5谢辞 6参考文献 6附录 6PAGE2一绪论八皇后问题是一个古老而著名的问题。这个问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。例如:00000000面对这个问题，要放在以往可能就要耗费大量的时间在纸上画来画去，这样做的耗费了大量的精力，但是效果却不佳。借助计算机就可以很高效的完成这些工作。那么，采用什么样的数据结构和算法，才能在时间和空间复杂度上完成这个问题呢？二需求分析1．问题说明：在8X8的方格棋盘上安置8枚棋子（皇后），棋盘的合法布局：对于任何两个棋子必须满足三个约束条件eq\o\ac(○,1)不能在同一列eq\o\ac(○,2)不能在同一行eq\o\ac(○,3)不能在同一个对角线上2．本程序的目的是将八皇后中满足条件的所有的可能性统计出来,然后将这些结果输出3.测试数据输入皇后的个数8,程序会输出出可能的结果,以及统计结果.三概要设计1.算法思想:算法集中在如何解决棋子之间的冲突问题。I.判断每个棋子是否满足规则的方法可以说是如出一辙。因此算法的整体思想是递规调用判断函数chess()。从i行开始安置各行元素,当i>=8时输出结果.II.具体的chess()函数的思想是:先在第1行放上一个皇后，然后在第2行合适的位置放上一个皇后，依次类推，如果8行都放满了，说明找到了一个解，如果第好第i行的皇后后，第i+1行找不到合适的位置，这时就回到第i行，把第i行的皇后放到下一个位置，继续尝试下一行。如此反复，知道找到所有的解。注意，这种算法找的解可能有等价的，某些解可由别的解经过旋转棋盘得到。2.数据类型的定义:I.charQueen[8][8]II.inta[8]这个表示皇后所放置的列数a[0]~a[7]表示第一列到第8列III.intb[15]intc[15]表示棋盘上的对角线左右两边一共两条3.主程序 Voidmain(){初始化; Do{ 接受命令(输入皇后的的个数); 处理命令; }while(“命令”!=”退出”); }4.本程序只有两个模块,调用关系简单 主程序模块 判断皇后的位置是否符合规则的模块四详细设计1.主程序以及其他伪码算法Voidmain(){ //主程序 Initialization;//棋盘及其他数据的初始化 Chess(inti);//执行判断函数}//mainVoidInitialization(){ //系统初始化 Clrscr;//清屏 为棋盘初始化,全部置空; 将对角线标记数组以及列标记数组初始化置零;}Chess(inti){for(j=0;j<8;j++)/*第i个皇后在第j行*/

if((i,j)位置为空)）/*即相应的三个数组的对应元素值为0*/

{占用位置（i,j）/*置相应的三个数组对应的元素值为1*/

if(i<7)

为i+1个皇后选择合适的位置；

elsePrintResult()//输出一个解/*如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置*/}}PrintResult(){输出棋盘；结果自增一；}2.函数的调用关系图MMInitializationChessChessPrintResult3.本程序的编程中使用了递规调用的思想.如果采用非递归的方法，使用大量的判断语句这样无疑大大的增加了程序的时间复杂度,而且代码比较拖沓不精练。如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。这个程序，运用到了数据结构中，第三章的栈，第五章的数组，以及第六章的树和回溯法。特别是在第六章，对于树以及二叉树的学习，更是为八皇后的问题提供了科学的解决方案，通过对树的分析，把八皇后的问题看成了树，而在衍生第一个变化后，上面的第一层八个变化就变成了八个结点，而这八个结点再继续的衍生……，这样比较形象的将八皇后的问题简单化了。然后再通过回溯法进行设计，回溯法是设计递归过程的一个重要的方法。它的求解过程实质上是一个先序遍历一棵“状态树“的过程。在这个程序设计中，它先进行判断，棋盘上是否已经得到一个完整的布局（即棋盘是否已经摆上8个棋子），如果是，则输出布局；如果不是则依次先根遍历满足约束条件的各棵子树，流程即是：判断该子树根的布局是否合法合法的话，则先根遍历该子树不合法的话，则剪去该子树的分支。五调试分析1.程序看起来比较简单其实当中是数据结构的编程思想隐藏在其中。经过数据结构的学习后可以说拓宽了我们的编程视野。不想以前学习C＋＋那样面对题目的时候力不从心。2．调试：经过编译连接执行以后程序可以正常的显示出92中八皇后可能的结果。六测试结果在测试结果的得到92种可能情况，并且可以正确地输出。七用户使用说明1．本程序的运行环境为DOS操作系统，运行可执行文件queen.exe2．本程序的源代码运行在VC＋＋6.0以上的语言平台小结随着时间的推移，一周的课程设计就要结束了。这次的数据结构的课程设计中，可以具体地说选择编写八皇后的程序的过程中，让我的编程眼界大开。可以说八皇后是一道古老但是相当经典的题目，所以研究它会让你受益颇深。一道寻常的题目用了不寻常的方法也就变得不寻常，同样，解决八皇后问题的方法有很多，就看你选择什么方法了。这里可能使用到大一学习的C＋＋用穷举的方法作题目，但是这样虽然也可以完成要求但是这样的时间复杂度很高。采用回朔的方法就可以节约很时间，这正是数据结构中树的妙用。这是真正感受到了数据结构在整个编写程序过程中的重要性。可以说在很大程度上改变了我们的编程思想，再这个过程中，也感受到程序设计是不能仅仅满足于有思路，更重要得是多多编写，让好的思想变成一个可以运行的程序，并且不断的完善和更新算法才能时刻保持领先。有句话说得好，好的程序员是写出来得。我想，虽然这次的课程设计结束了，但是我们的编程道路才刚刚迈开，在本次的课程设计中，本想作出可视化的动态演示八皇后，但是不是很顺利，最近也看了很多关于VC＋＋MFC编程的书籍，也很顺利的编写出了几个简单的可视化程序，如小型记事本，简易计算器，但是可能还是没有掌握到它精髓所在。但是我不会放弃，我会继续坚持学习下去，尽快让我的八皇后算法在可视化的动态界面下奔腾起来。呵呵，乐观，冷静相信我会不断的前进。谢辞呵呵，谈到谢辞这里当然要感谢我们的尹燕老师，可以说每次我不知所措的时候，总是可以从她身上看到那种编程人的乐观，积极，冷静，可以说她教给我们的不仅仅是编程，更是一种编程人应该具备的品质和思想。还要感谢帮助过我得学长，网友。相信有他们的支持，我一定会继续