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