数据结构八皇后问题.doc

目 录 一 需求分析 1 1.1 程序的功能： 1 1.2 程序的输入输出要求： 1 二 概要设计 3 2.1 程序的主要模块： 3 2.2 程序涉及： 3 三 详细设计 4 3.1 相关代码及算法 4 3.1.1 定义相关的数据类型如下： 4 3.1.2 主模块类C码算法： 4 3.1.3 画棋盘模块类C码算法 5 3.1.4 画皇后模块类C码算法： 5 3.1.5 八皇后摆法模块（递归法）： 6 3.1.6 初始化模块 7 3.1.7 输出摆放好的八皇后图形（动态演示）： 7 3.2 相关流程图 8 四 调试分析 10 五 设计体会 11 六 附录 12 七 参考文献 16 一 需求分析 1.1 程序功能： 八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出的。八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子，问有多少种不同的摆法？并找出所有的摆法。因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。本程序通过对子函数void qu(int i)的调用，将八皇后的问题关键通过数据结构的思想予以了实现。虽然题目以及演算看起来都比较复杂，繁琐，但在实际中，只要当一只皇后放入棋盘后，在横与列、斜线上没有另外一只皇后与其冲突，再对皇后的定位进行相关的判断。即可完成。如果在这个程序中，我们运用的是非递归的思想，那么将大量使用if等语句，并通过不断的判断，去推出答案，而且这种非递归的思想，大大的增加了程序的时间复杂度。如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。这个程序，我运用到了数据结构中的栈、数组，以及树和回溯的方法。特别是在对于树以及二叉树的学习，更是为八皇后的问题提供了科学的解决方案，通过对树的分析，把八皇后的问题看成了树，而在衍生第一个变化后，上面的第一层八个变化就变成了八个结点，而这八个结点再继续的衍生……，这样比较形象的将八皇后的问题简单化了。然后再通过回溯法进行设计，回溯法是设计递归过程的一个重要的方法。它的求解过程实质上是一个先序遍历一棵“状态树“的过程。在这个程序设计中，它先进行判断，棋盘上是否已经得到一个完整的布局（即棋盘是否已经摆上8个棋子），如果是，则输出布局；如果不是则依次先根遍历满足约束条件的各棵子树，流程即是： 判断该子树根的布局是否合法：如果合法的话，则先根遍历该子树；如果不合法的话，则剪去该子树的分支。 1.2 程序的输入输出要求： 用TC软件进行编译以及调试，调试正确之后，运行结果如下图： 输出结果如下图所示： 第1种情况 . . . . . . . . . . . . . . .