1、 1 数据结构课程设计 选题：选题： 八皇后问题八皇后问题 姓姓 名：名： 学学 号：号： 指导老师：指导老师： 2 目 录 一.选题概述-3 二.设计要求与分析-3 三.数据结构与定义-4 1.结构体定义 2.函数定义 3.函数之间的定义 四.程序段与分析-5 五.完整程序代码及运行结果截图-7 六.心得体会-10 七.参考文献-10 3 一选题概述：一选题概述： 在实际应用中， 有相当一类问题需要找出它的解集合，或者要求找出 某些约束条件下的最优解。 求解时经常使用一种称为回溯的方法来解 决。所谓回溯就是走回头路， 该方法是在一定的约束条件下试探地搜 索前进，若前进中受阻，则回头另择通路继
2、续搜索。为了能够沿着原 路逆序回退，需用栈来保存曾经到达的每一个状态，栈顶的状态即为 回退的第一站， 因此回溯法均可利用栈来实现。而解决八皇后问题就 是利用回溯法和栈来实现的。 二设计要求与分析二设计要求与分析 八皇后问题是在 8x8 的国际象棋棋盘上，安放 8 个皇后，要求没 有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上 的皇后占据棋盘上的同一行、同一列或同一条对角线。 八皇后在棋盘上分布的各种可能的格局，其数目非常大，约等于 232 种，但是，可以将一些明显不满足问题要求的格局排除掉。由于 任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第 i 个 皇后放置在第 i
3、行上。这样在放置第 i 个皇后时，只要考虑它与前 i 一 1 个皇后处于不同列和不同对角线位置上即可。 因此， 其算法基本 思想如下： 从第1 行起逐行放置皇后， 每放置一个皇后均需要依次对第 1， 2，8 列进行试探，并尽可能取小的列数。若当前试探的列位置 4 是安全的，即不与已放置的其他皇后冲突， 则将该行的列位置保存在 栈中，然后继续在下一行上寻找安全位置； 若当前试探的列位置不安 全， 则用下一列进行试探， 当 8 列位置试探完毕都未找到安全位置时， 就退栈回溯到上一行，修改栈顶保存的皇后位置，然后继续试探。 该算法抽象描述如下： （1)置当前行当前列均为 1; （2）while(当前行号8) （3） 检查当前行，从当前列起逐列试探，寻找安全列号； （4）if（找到安全列号） （5）放置皇后，将列号记入栈中，并将下一行置成当前行， 第 1 列置为当前列； （6）else （7）退栈回溯到上一行，移去该行已放置的皇后，以该皇后 所在列的下一列作为 当前列； （8） 结束程序。 三三数据结构与定义数据结构与定义 1.结构体定义结构体定义 typedef struct int colMaxSize; /coli存放第 i 个皇后的列号 int top; /栈顶指针
