数据结构课程设计八皇后问题.pdf

目 录 1、课程设计的目的1 2、课程设计的要求1 3、课程设计的内容1 3.1 设计的内容1 3.2 算法思路1 3.2.1 算法的内容1 3.2.2 算法中函数的流程图1 3.3 程序调试与测试以及结果的分析3 3.3.1 详细设计3 3.3.2 遇到的问题及解决方法6 3.3.3 算法的时空分6 3.3.4 结果分析6 3.3.5 算法的改进6 3.3.6 程序使用说明6 3.3.7 测试结果7 4、总结10 5、参考文献10 6、附录11 1 八皇后问题 1、课程设计的目的（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；2、课程设计的要求（1）设计的课题能够体现数据结构和算法的算法分析、设计、算法实现。（2）根据自己对数据结构和算法的基本概念、原理和机制的理解，自拟题目和设计内容，选题尽可能结合实际的应用。3、课程设计的内容 3.1 设计的内容 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯 1850 年提出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有 76 种不同的放法，这就是有名的“八皇后”问题。在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8 的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有 92个解答。我要设计的程序就是怎样把 92 种解答直观清晰的让大家了解和认识。3.2 算法思想 3.2.1 算法的内容（1）解数组 a，ai表示第 i 个皇后放置的列，范围为 18。（2）行冲突标记数组 b，bj=0 表示第 j 行空闲，bj=1 表示第 j 行被占领，范围为 18。（3）对角线冲突标记数组 c、d。ci-j=0 表示第（i-j）条对角线空闲，ci-j=1 表示第（i-j）条对角线被占领，范围-77。di+j=0 表示第（i+j）条对角线空闲，di+j=1 表示第（i+j）条对角线被占领，范围 216。（4）抽象数据类型的定义 Print()/打印每一列皇后的放置的行数以及以矩阵形式形象的显示皇后的放置位置 JudgeQueen1()/递归寻找摆放皇后位子 void main()/主函数调用 3.2.2 算法中函数的流程图(1)数据初始化。(2)从 n 列开始摆放第 n 个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当 2 前位置（n，m）是否等于 0（未被占领）。如果是，摆放第 n个皇后，并宣布占领（记得姚横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当 n8时，便打印出结果。其算法流程图如下：N Y Y N 开始 数据初始化 1 2 从 n 列开始摆放第 n 个皇后 开始 从第 n 列开始摆放第 n 个皇后 摆放皇后，并 宣布占领 测试下个位置 m=m+1 当前位置（n，m）是否被占领 n=n+1 摆放皇后，并 宣布占领 当前位置（n，m）是否被占领 n=n+1 摆放皇后，并 宣布占领 当前位置（n，m）是否被占领 0打印 结果 进行回溯 n=8&m=8 3 3.3程序调试与测试以及结果的分析 3.3.1详细设计/定义数组 int a8；/表示第 i 个皇后放置的列，范围为 18。int b8；/表示第 j 行空闲，bj=1 表示第 j 行被占领，范围为 18 int c30；/表示第（i-j）条对角线空闲，ci-j=1 表示第（i-j）条对角线被占领，范围-77 int d30；/表示第（i+j）条对角线空闲，di+j=1 表示第（i+j）条对角线被占领，范围216。/位置标明法打印 void print1()X+;couttNo.X:;/每一行皇后放置的列数的第 X 种情况 for(k=1;k9;k+)cout ak;coutn;/矩阵表示法打印 void print2()int t,n;Y+;couttNo.Y: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(int i)4 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 个皇后没有摆完，递归摆放下一皇后 else print1();/完成任务，打印结果 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=j;bj=1;ci+j=1;di-j=1;if(i8)PlaceQueen2(i+1);else print2();/打印结果 bj=0;/回溯 ci+j=0;di-j=0;e+;/调用主函数 void main()5 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)coutnt 查 询 菜 单n;coutnt*;coutnt*No.1-每一行皇后放置的列数的情况 *;coutnt*No.2-视图矩阵形式显示皇后的位置 *;coutnt*No.0-退 出 *;coutnt*;coutchoice;switch(choice)case 1:coutnt 每一行皇后放置的列数的情况nn;PlaceQueen1(1);/从第 1 个皇后开始放置 break;case 2:coutnt 使用回车查看下一种情况nn;PlaceQueen2(1);/从第 1 个皇后开始放置 break;case 0:ch=n;break;default:coutntt 菜单选择错误，请重新输入!n;6 3.3.2遇到的问题及解决方法(1)由于对八个皇后放置的位置不能一次确定，而且前一个皇后的放置位置直接影响着后面的放置位置，使程序调试时要花费不少时间。(2)本程序有些代码重复出现，显得程序的有些代码看起来很杂乱。但其中最主要的问题是逻辑错误导致程序死循环或不循环或循环一小部分,但是编译时却没有错误,就是没有正确的输出答案。比如说，在 void print2()中有 for(t;t9;t+)，如果赋 t=1，则在视图显示法中会出现排序紊乱。类似的还有出现死循环的问题，后在同学们的帮助下，经细心改正后才把调试工作做完。(3).这里在编写回溯算法时候需要特别注意以下几点：回溯循环的结束在于第一个皇后被回溯。当找到一个解时，需要复制整个棋盘，不然接下来的回溯将破坏已经找到的解。找到一个解后，需要在当前皇后的基础上回溯。回溯一个皇后时，要对当前的列数进行重置。一般在编写完核心代码后，需要编写一定的测试代码进行单元测试。否则的话，后面出现的错误的程序代码问题是好难修正的！3.3.3 算法的时空分析 该算法的运行时间和和皇后的放置方法成正比，在最好情况下的时间和空间复杂度均为O（1），在最差情况下均为 O（n*n），平均情况在它们之间。3.3.4 程序模块构架 本程序模块划分比较合理，且利用指数组存储棋盘，操作方便。至于整体的系统架构，为了简单起见，这样的系统可以分成两个模块，第一个模块是负责模拟问题、提供算法，而另外一个模块则致力于窗口演示，是一个窗体应用程序 3.3.5算法的改进 这道题可以用非递归循环也可以用递归循环的方法来做，这里我选用了比较有效率的后者进行分析，其方法是分别一一测试每一种皇后摆法，直到得出正确的答案即所谓的回溯法。另附录附上非递归方法及其说明。3.3.6 程序使用说明（1）本程序的运行环境为 windows 操作系统（2）进入演示程序后即显示文本方式的用户界面（3）进入界面后，就会提示输入字符串的输入形式，在八皇后求解程序中，只要你选择输出解的格式，选择 1 则显示为每一列皇后的放置的行数，选择 2 则显示的是以矩阵形式形象的显示皇后的放置位置，选择 3 则退出程序的调试。在调试结果中，1 的位置也就表示了该皇后应该所在的位置，0 代表了空位置。7 3.3.7 测试结果 递归算法 初步运行界面 8 位置标明每一行皇后放置的列数 9 10 非递归算法 11 4、总结 通过这次的课程设计，我从中得到了许多经验和软件设计的一些新思路；从这个八皇后问题设计以及分析中，本人从中理解到了数据结构对于软件设计的重要性，它的使用，可以改变软件的运行周期，思路从繁化简，并且都能够通过其相关引导，将本身以前编程思想进行扩充，发展.这也是在这次课程设计中我所掌握得到的。但在这次的课设中也遇了一些问题，如，八皇后在变成初期由于没真正体会到“树”在里面的运用,不自觉的采用了非递归的算法，结果大大增加了程序的复杂程度。并且也让整个程序的时间复杂度变得更大；在重温了树的回溯，以及二叉树的遍历后，最终将程序进行了一次较大的改造。并且通过思考，再将以前的数组知识加以运用才最终解决了这个问题，整个程序的算法的可看性也有了较大的改进。5、参考文献 1.宁正元,王秀丽算法与数据结构清华大学出版社.2.马石安,魏文平.面向对象程序设计.清华大学出版社.3.谭浩强.C 程序设计.清华大学出版社.4.苏仕华,数据结构课程设计.机械工业出版社.5.严蔚敏,吴伟民,数据结构清华大学出版社.12 6、附录：(代码)（1）递归算法#include#include using namespace std;int a8;/表示第 i 个皇后放置的列，范围为 18。int b8;/表示第 j 行空闲，bj=1 表示第 j 行被占领，范围为 18 int c30;/表示第（i-j）条对角线空闲，ci-j=1 表示第（i-j）条对角线被占领，范围-77 int d30;/表示第（i+j）条对角线空闲，di+j=1 表示第（i+j）条对角线被占领，范围 216。int X;int k;int Y;/位置标明法打印 void print1()X+;couttNo.X:;/每一行皇后放置的列数的第 X 种情况 for(k=1;k9;k+)cout ak;coutn;/矩阵表示法打印 void print2()int t,n;Y+;couttNo.Y:nt;/矩阵形式的第 Y 种情况 for(k=1;k9;k+)n=ak;for(t=1;tn;t+)cout0;cout1;t+;for(t;t9;t+)cout0;coutnt;coutn;13/回溯递归法摆放皇后 void PlaceQueen1(int 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 个皇后没有摆完，递归摆放下一皇后 else print1();/完成任务，打印结果 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=j;bj=1;ci+j=1;di-j=1;if(i8)PlaceQueen2(i+1);else print2();/打印结果 bj=0;/回溯 ci+j=0;di-j=0;e+;14 /调用主函数 void main()char ch;int choice;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)coutnt 查 询 菜 单n;coutnt*;coutnt*No.1-每一行皇后放置的列数的情况 *;coutnt*No.2-视图矩阵形式显示皇后的位置 *;coutnt*No.0-退 出 *;coutnt*;coutchoice;switch(choice)case 1:coutnt 每一行皇后放置的列数的情况nn;PlaceQueen1(1);/从第 1 个皇后开始放置 break;case 2:coutnt 使用回车查看下一种情况nn;PlaceQueen2(1);/从第 1 个皇后开始放置 break;case 0:ch=n;break;default:coutntt 菜单选择错误，请重新输入!n;（2）非递归算法 15#include#include using namespace std;const int MAXSIZE=8;/棋盘大小 int chessMAXSIZEMAXSIZE=0;/棋盘/*定义栈结点，表示一个皇后的位置*/struct Node int row;/*行*/int col;/*列*/bool isMarked;/*是否标记biao ji*/;/*进行皇后问题处理 *返回找到的答案个数 */int Solve()/定义解答树堆栈dui zhan stack stack;/互斥标志，表示同一列及对角线上是否有皇后 int colMAXSIZE=0,md2*MAXSIZE-1=0,sd2*MAXSIZE-1=0;int str,stc,i,j;/解决方案个数 int scount=0;Node topNode;/初始化chu shi hua栈 for(i=0;i MAXSIZE;i+)topNode.row=0;topNode.col=MAXSIZE-1-i;topNode.isMarked=false;stack.push(topNode);/以行为单位开始回溯 while(!stack.empty()topNode=stack.top();/栈顶元素 str=topNode.row;/行 stc=topNode.col;/列 if(topNode.isMarked=false)16 /如果栈顶元素的位置wei zhi并没有确立 if(colstc|mdstr-stc+MAXSIZE-1|sdstr+stc)/如果同一列或同一对角线上已有皇后，则退回*/stack.pop();else /占据这个位置，设置列、对角线上的互斥标志 colstc=1;mdstr-stc+MAXSIZE-1=1;sdstr+stc=1;/标记biao ji栈顶元素的 isMarked 值 topNode.isMarked=true;stack.pop();stack.push(topNode);chessstrstc=1;/标记棋盘对应位置 if(str=MAXSIZE-1)/如果此时已经到达最后一行,则表示此种布局方法是成功的,输出相关信息 coutA solution is:endl;for(i=0;iMAXSIZE;+i)for(j=0;jMAXSIZE;+j)if(chessij=1)cout(i+1,j+1);coutendl;scount+;/解决方案数增 else /如果此时没有到达最后一行,则继续进栈并初始化 for(i=0;i MAXSIZE;i+)topNode.row=str+1;topNode.col=MAXSIZE-1-i;topNode.isMarked=false;stack.push(topNode);17 else /如果栈顶元素位置已确立,则栈顶元素出栈，初始化互斥标志,准备继续寻找其它的方法 colstc=0;mdstr-stc+MAXSIZE-1=0;sdstr+stc=0;chessstrstc=0;stack.pop();return scount;int main()int scount=0;scount=Solve();coutscountsulotions found.endl;system(pause);return 0;