八皇后问题.pdf

数据结构课程设计报告八皇后问题班级：*姓名：*学号：*八皇后问题1、问题分析八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高 斯1850 提出；在 8X的国际象棋上摆放八皇后，使其不能互相攻击，即任意 两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认 为有 76 种方案。1854 年在柏林的象棋杂志上不同的作者发表了解，后人有人用图论的方法解出 92 宗结果。八皇后问题是在 8*8 的国际象棋棋盘上，安放 8 个皇后，要求没有一个皇 后能够 吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的 同一行、同一列或同一条对角线。八皇后在棋盘上分布的各种可能的格局，其数非常大，但是可以将一些明 显不满足问题要求的格局排除掉。由于任何两个皇后不能同行，即每一行只能 放置一个皇后，因此将第 i 个皇后放置在第 i 行。这样在放置第 i 个皇后时，只 要考虑它与前i-1 个皇后处于不同列和不同对角线位置上即可。2、算法描述40 种不同的从第一行起逐行放置皇后，每放置一个皇后均需要依次对第1, 23 列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已经放置的其他皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列位置不安全，则用下一列去试探，当 8 列位置试探完 毕都未找到安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置，然 后继续试探。该算法抽象的描述如下：(1)置当前行当前列均为 1;(2)While (当前行号 v = 8);(3)检查当前行，从当前列起逐列试探，寻找安全列号；(4)if (找到安全列号)(5)放置皇后，将列号放入栈中，并将下一行置为当前行，第 1 列置为当 前列；(6)else(7)退栈回溯到上一行，移去该行已经放置的皇后，已该皇后所在列的下一列作为当前列；(8)2. 1 算法求精要对上述抽象算法进行逐步求精，就需要确定相应的存储结构和有关的数据类型。当前行和列分别用 i 和 j 表示；用数组 s1昧示顺序栈，栈空间的下 标值表示皇后所在的行号，栈的内容是皇后所在的列号。例如，若皇后放在位 置(i,j)上，则将j 压入栈中，即 si=j。为了便于检查皇后之间是否冲突，我们 增加三个布尔数组(初始值为真)，将与检查有关的信息事先保存起来。定义 如下：int a9,b17,c17;int s9;其中，aj为真时(1),表示第 j 列上无皇后。位于同一条“/方向的对角线上的诸方格，其 行、列坐标之和 i+j 是相等的，这种方向的对角线有 15 条，其行、列坐标之和 分别为 216,因此用 b21 浙记该方向的诸对角线上有无皇后，bk为真时 表示该方向的第 k条对角线上无皇后。行、列坐标之差 i-j 相等的诸方格在同一 条“/方向的对角线上，该类对角线有 15 条，其行、列坐标之差分别是-7乙 因此 C 语言数组下标是从 0 开始的，所以用 c216B 记这种方向的诸对角线上 有无皇后，ck为真时表示该方向的第 k 条对角线上无皇后。这样，bi+j和 ci- j+9的真假就分别表示了通过位置(i, j)的两条对角线上有无皇后。因此，位置(i,j)的安全”性可用逻辑表达式aj&bi+j&ci-j+9来表示。在位置(i,j)上放置皇后后，相当于将 aj, bi+j和 ci-j+9置为 假；移去(i,j)上的皇后相当于将 aj, bi+j和 ci-j+9置为真。2. 2 算法扩充在上面的算法中，仅求出了八皇后问题的一个解，要求出所有满足约束条件的解，就要对上述算法进行扩充和修改。要解决这个问题，关键在于以下两 个问题：(1)如何从问题的一个解出发求出下一个解：(2)如何确定所有的问题解都已求出。因此，我们可对上述算法进行修改，使其求得一个解后，算法并不终止， 而是输出这个解，然后退栈回溯，继续寻找下一个解；一旦当前行是第仍需要退栈回溯时，算法终止。3、算法实现/求八皇后问题所有解的源程序清单#include#define true 11 行又#define false 0int a9,b17,c17;/ 声明全局变量int s9;void main()void print(),movequeen(),eightqueen();/ 函数声明eightqueen();/ 调用求命新 l 皇后 I、可题/*/*打印输出一个解的函数*/*/void print()int k;printf(n行号:1 2 3 4 5 6 7 8n);printf(列号：);for(k=1;k=8;k+)printf(%4d,sk);printf(n);/*/*移去位置（i, j）上的皇后函数*/*/void movequeen(int i,int j)aj=1;bi+j=1;ci-j+9=1;/ 在此位置插入eightqueen()函数void eightqueen()int i,j;for(i=2;i=2 & i=1)(/当 i=0 时终止循环 while(j=8)(/在当前行 i 上寻找安全位置 if(aj& bi+j & ci-j+9) break;j+;if(j=1) /栈不空，移去皇后j=si;movequeen(i,j);/ 移去皇后j+;4、程序运行测试编译运行上述程序，即可求得八皇后问题的所有（注：仅列出部分解，共 92 个解）92 个解: