《数据结构课程设计-八皇后问题》由会员分享，可在线阅读，更多相关《数据结构课程设计-八皇后问题（19页珍藏版）》请在金锄头文库上搜索。
1、1、课程设计的目的12、课程设计的要求13、课程设计的内容13.1 设计的内容13.2 算法思路13.2.1 算法的内容13.2.2 算法中函数的流程图13.3 程序调试与测试以及结果的分析33.3.1 详细设计33.3.2 遇到的问题及解决方法63.3.3 算法的时空分63.3.4 结果分析63.3.5 算法的改进63.3.6 程序使用说明63.3.7 测试结果74、总结105、参考文献106、附录11八皇后问题1、课程设计的目的(1) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；(2) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；(3)
2、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；(4) 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科 学的工作方法和作风；2、课程设计的要求(1) 设计的课题能够体现数据结构和算法的算法分析、设计、算法实现。(2) 根据自己对数据结构和算法的基本概念、原理和机制的理解，自拟题目和设计内容， 选题尽可能结合实际的应用。3、课程设计的内容3.1 设计的内容八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850 年提 出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76 种不 同的放法，这就是有名的“八皇后”问题。
3、在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同 一斜线(正斜线或反斜线)上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在 8*8 的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一 列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有 92 个解答。我要设计的程序就是怎样把92 种解答直观清晰的让大家了解和认识。3.2 算法思想3.2.1 算法的内容(1) 解数组a, ai表示第i个皇后放置的列，范围为18。(2) 行冲突标记数组 b， bj=0 表示第 j 行空闲， bj=1 表示第 j 行被占领，范围为
4、18。(3) 对角线冲突标记数组c、do ci-j=O表示第(i-j)条对角线空闲，ci-j=1表示第(i-j) 条对角线被占领，范围-77。di+j=O表示第(i+j)条对角线空闲，di+j=1表示第(i+j) 条对角线被占领，范围 216。(4) 抽象数据类型的定义Print() /打印每一列皇后的放置的行数以及以矩阵形式形象的显示皇后的放置位置JudgeQueen1() /递归寻找摆放皇后位子void main()/主函数调用3.2.2 算法中函数的流程图(1) 数据初始化。(2) 从n列开始摆放第n个皇后(因为这样便可以符合每一竖列一个皇后的要求)，先测试当前位置（n, m）是否等于0
5、 （未被占领）。如果是，摆放第n个皇后，并宣布占领（记得姚 横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置n，m+1）,但是如果 当 n8 时，便打印出结果。其算法流程图如下：开开始台数据初始化从W 列列开始摆放第nn个皇皇后n=nH=n+13.3程序调试与测试以及结果的分析3.3.1 详细设计/定义数组int a8； /表示第i个皇后放置的列，范围为18。int b8； /表示第j行空闲，bj=1表示第j行被占领，范围为18int c30； /表示第(i-j)条对角线空闲，ci-j=1表示第(i-j)条对角线 被占领，范围-77int d30； 表示第(i+j)条对角线空闲，
6、di+j=1表示第(i+j)条对角 线被占领，范围 216。/位置标明法打印void print1()X+;coutvvtNo.vvXvv:; 每一行皇后放置的列数的第X种情况 for (k=1;k9;k+)cout ak;coutn;/矩阵表示法打印void print2() int t,n;Y+;coutvvtNo.vvYvv: nt; 矩阵形式的第 Y 种情况 for (k=1;k9;k+)n=ak; for(t=1;tn;t+) cout0 ;cout1 ;t+; for(t;t9;t+) cout0 ;coutnt;coutn;/回溯递归法摆放皇后void PlaceQueen1(i
7、nt i) int j;for (j=1;j9;j+) /每个皇后都有 8 种可能位置if (bj=0) &(ci+j=0)& (di-j=0) /判断位置是否冲突 ai=j;/摆放皇后bj=1;宣布占领第J行ci+j=1;/占领两个对角线di-j=1;if (i8)PlaceQueen1(i+1); /8 个皇后没有摆完，递归摆放下一皇后 elseprint1(); /完成任务，打印结果bj=0;/回溯ci+j=0; di-j=0;void PlaceQueen2(int i)int j ,e=1;for (j=1;j9;j+)if (bj=0) &(ci+j=0)& (di-j=0) ai
8、=j;bj=1;ci+j=1;di-j=1;if (i8)PlaceQueen2(i+1);elseprint2(); /打印结果 bj=0;/回溯ci+j=0; di-j=0; e+;/调用主函数 void main() coutnnt* Welcome to EightQueen inquiries software problems *nn; for( k=0;k24;k+) /数据初始化 bk=0; ck=0; dk=0;ch=y;while(ch=y|ch=Y)coutvvnt 查 询 菜单 n;coutnt* coutnt* coutchoice;switch(choice)cas
9、e 1:coutvvnt每一行皇后放置的列数的情况nn;PlaceQueen1(1);/从第 1 个皇后开始放置break;case 2:coutvvnt使用回车查看下一种情况nn;PlaceQueen2(1);/从第 1 个皇后开始放置break;case 0:ch=n;break;default:coutvvntt菜单选择错误，请重新输入!n;3.3.2 遇到的问题及解决方法(1) 由于对八个皇后放置的位置不能一次确定，而且前一个皇后的放置位置直接影响着后 面的放置位置，使程序调试时要花费不少时间。(2) 本程序有些代码重复出现，显得程序的有些代码看起来很杂乱。但其中最主要的问题 是逻辑错
10、误导致程序死循环或不循环或循环一小部分,但是编译时却没有错误,就是没有正确 的输出答案。比如说，在void print2()中有for(t;tv9;t+)，如果赋t=l,则在视图显示法中 会出现排序紊乱。类似的还有出现死循环的问题，后在同学们的帮助下，经细心改正后才把 调试工作做完。(3) . 这里在编写回溯算法时候需要特别注意以下几点： 回溯循环的结束在于第一个皇后被回溯。 当找到一个解时，需要复制整个棋盘，不然接下来的回溯将破坏已经找到的解。 找到一个解后，需要在当前皇后的基础上回溯。 回溯一个皇后时，要对当前的列数进行重置。 一般在编写完核心代码后，需要编写一定的测试代码进行单元测试。否
11、则的话，后面出现的 错误的程序代码问题是好难修正的！3.3.3 算法的时空分析该算法的运行时间和和皇后的放置方法成正比，在最好情况下的时间和空间复杂度均为O(1)，在最差情况下均为O (n*n),平均情况在它们之间。3.3.4 程序模块构架本程序模块划分比较合理，且利用指数组存储棋盘，操作方便。至于整体的系统架构， 为了简单起见，这样的系统可以分成两个模块，第一个模块是负责模拟问题、提供算法，而 另外一个模块则致力于窗口演示，是一个窗体应用程序3.3.5 算法的改进这道题可以用非递归循环也可以用递归循环的方法来做，这里我选用了比较有效率的后者进行分析，其方法是分别一一测试每一种皇后摆法，直到得
12、出正确的答案即所谓的回溯法。 另附录附上非递归方法及其说明。3.3.6 程序使用说明( 1 ) 本程序的运行环境为 windows 操作系统(2) 进入演示程序后即显示文本方式的用户界面(3) 进入界面后，就会提示输入字符串的输入形式，在八皇后求解程序中，只要你选择输 出解的格式，选择1 则显示为每一列皇后的放置的行数，选择2 则显示的是以矩阵形式形 象的显示皇后的放置位置，选择3 则退出程序的调试。在调试结果中， 1 的位置也就表示了 该皇后应该所在的位置， 0 代表了空位置。3.3.7 测试结果递归算法初步运行界面8?7772878878557588每一行皇后放置的列数的惰况No.l：Ho-2：No .3：Nq f4;No .5：Ho .6:No.7：No.S：Hq.9：No.10
