八皇后课程设计报告八皇后课程设计报告.doc

目录 一 绪论 1 二 需求分析 1 三 概要设计 2 四 详细设计 3 五 调试分析 4 六 用户使用说明 5 七 测试结果 5 小结 5 谢辞 6 参考文献 6 附录 6 一 绪论 八皇后问题是一个古老而著名的问题。这个问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。例如: 0 0 0 0 0 0 0 0 面对这个问题，要放在以往可能就要耗费大量的时间在纸上画来画去，这样做的耗费了大量的精力，但是效果却不佳。借助计算机就可以很高效的完成这些工作。那么，采用什么样的数据结构和算法，才能在时间和空间复杂度上完成这个问题呢？ 二 需求分析不能在同一列　不能在同一行　不能在同一个对角线上 2．本程序的目的是将八皇后中满足条件的所有的可能性统计出来, 然后将这些结果输出 3. 测试数据 输入皇后的个数8,程序会输出出可能的结果,以及统计结果. 三 概要设计 I.判断每个棋子是否满足规则的方法可以说是如出一辙。因此算法的整体思想是递规调用判断函数chess( )。从i行开始安置各行元素,当i=8时输出结果. II.具体的chess( )函数的思想是: 先在第1行放上一个皇后，然后在第2行合适的位置放上一个皇后，依次类推，如果8行都放满了，说明找到了一个解，如果第好第i行的皇后后，第i+1行找不到合适的位置，这时就回到第i行，把第i行的皇后放到下一个位置，继续尝试下一行。如此反复，知道找到所有的解。注意，这种算法找的解可能有等价的，某些解可由别的解经过旋转棋盘得到。 2. 数据类型的定义: I. char Queen[8][8] 表示棋盘.这里定义为char类型的是为了找到满足条件的棋盘时将棋子占据的位置用一个字符代替.以使输出结果美观. II. int a[8] 这个表示皇后所放置的列数 a[0]~a[7]表示第一列到第8列 III. int b[15] int c[15] 表示棋盘上的对角线左右两边一共两条 3. 主程序 Void main( ) { 初始化; Do{ 接受命令(输入皇后的的个数); 处理命令; }while(“命令”!=”退出”); } 4. 本程序只有两个模块,调用关系简单 主程序模块 判断皇后的位置是否符合规则的模块 四 详细设计 Void main( ) { //主程序 Initialization;//棋盘及其他数据的初始化 Chess(int i);//执行判断函数 }//main Void Initialization( ) { //系统初始化 Clrscr;//清屏 为棋盘初始化,全部置空; 将对角线标记数组以及列标记数组初始化置零; } Chess(int i) { for(j=0;j8;j++) /*第i个皇后在第j行*/ if ((i,j)位置为空)） /*即相应的三个数组的对应元素值为0*/ { 占用位置（i,j） /*置相应的三个数组对应的元素值为1*/  if (i7) 为i+1个皇后选择合适的位置；  else PrintResult()//输出一个解 /*如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置PrintResult() { 输出棋盘； 结果自增一； } 2.函数的调用关系图 3. 本程序的编程中使用了递规调用的思想.如果采用非递归的，大大的增加了程序的时间复杂度如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。这个程序，运用到了数据结构中，第三章的栈，第五章的数组，以及第六章的树和回溯法。特别是在第六章，对于树以及二叉树的学习，更是为八皇后的问题提供了科学的解决方案，通过对树的分析，把八皇后的问题看成了树，而在衍生第一个变化后，上面的第一层八个变化就变成了八个结点，而这八个结点再继续的衍生……，这样比较形象的将八皇后的问题简单化了。然后再通过回溯法进行设计，回溯法是设计递归过程的一个重要的方法。它的求解过程实质上是一个先序遍历一棵“状态树“的过程。在这个程序设计中，它先进行判断，