八皇后课程设计（详细版）.doc-资料库

congya001-3972710-4744300845394309678.doc.pdf-第1页.png

第1页 / 共36页

congya001-3972710-4744300845394309678.doc.pdf-第2页.png

第2页 / 共36页

congya001-3972710-4744300845394309678.doc.pdf-第3页.png

第3页 / 共36页

congya001-3972710-4744300845394309678.doc.pdf-第4页.png

第4页 / 共36页

congya001-3972710-4744300845394309678.doc.pdf-第5页.png

第5页 / 共36页

congya001-3972710-4744300845394309678.doc.pdf-第6页.png

第6页 / 共36页

congya001-3972710-4744300845394309678.doc.pdf-第7页.png

第7页 / 共36页

congya001-3972710-4744300845394309678.doc.pdf-第8页.png

第8页 / 共36页

课程设计报告

摘要：八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。而本课程设计本人的目的也是通过用 c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的 92 种结构予以实现．使用回溯算法最终将其问题变得一目了然，更加易懂。关键词：八皇后 ; c++ ; 回溯法

目录第一部分课题综述...............................................................................................................................4 1.课题的来源及意义：......................................................................................................................4 2.任务要求：...................................................................................................................................... 4 3.需求分析：...................................................................................................................................... 4 第二部分课题分析...............................................................................................................................4 1.目前状况中的问题：......................................................................................................................5 2.问题分析：...................................................................................................................................... 5 第三部分概要设计和数据结构....................................................................................................... 6 1.算法描述：...................................................................................................................................... 6 2.算法流程图： ..................................................................................................................................8 第四部分详细设计...............................................................................................................................8 1.类的设计：...................................................................................................................................... 8 第五部分上机调试.............................................................................................................................12 第六部分用户使用说明................................................................................................................... 13 第七部分测试结果及其分析..........................................................................................................13 第八部分参考文献.............................................................................................................................16 第九部分附录......................................................................................................................................17

第一部分课题综述：八皇后问题 1.课题的来源及意义：八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯 1850 年提出。在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在 8*8 的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。 2.任务要求： 3.需求分析：设计程序解决八皇后问题，设计要求如下：  依次输出各种成功的放置方法；  画出棋盘的图形界面，并在其上动态地标注行走的过程；  程序能方便地移植到其他规格的棋盘上。本次课程设计中，用到的主要知识有：递归法的运用，for 语句的灵活运用，数据结构中树知识的灵活运用、数组及动态数组技术的掌握。  系统要求：win98 以上操作系统；  语言平台：vc++6.0 或以上版本；第二部分课题分析：

根据程序的设计要求，需要设计一个八皇后问题的演示程序，程序需要具备以下功能：  能够快速查找并显示八皇后的布局方式有多少种正确方法；  能够逐个查看每种布局的结果；  能够逐步演示棋子在棋盘上的的行走过程，直到出现正确的结果；  能够很方便的改变皇后个数即棋盘规格。 1.目前状况中的问题：要实现指定的功能，存在以下几个待解决的问题；根据指定的规格，即皇后个数，来画出相应规格的棋盘；能够在指定的位置摆放棋子和收回棋子；制定落子的顺序和规则，避免重复和遗漏；标记每步落子后不能落子的区域，即已有棋子的同行、同列和同一斜线上的位置。 2.问题分析：程序的功能要求具有图形化界面，根据目前状况中的问题，综合考虑，在此使用 MFC 开发工具编程。关于棋盘的绘制，因为棋盘的规格（n*n）是不确定的，显然不能根据规格的大小来确定棋盘的面积，所以我们首先划分出一个指定区域，用来绘制棋盘，这个正方形区域的边长大小为一个整型常量 board，单位为像素，这样就能轻易的计算出每个棋子格的大小，即我们自定义的单位长度，cell=board/n；在此有衍生出另外一个问题， board 不可能被所有的 n 整除，这样得到的 cell 可能会是一个无理数，在 C++语言中，处理浮点型数据时不能存储无理数，所以最好的方法是让 cell 为一个整数，这里使用一个技巧，board = board - board % n;这就将取整后的余数去掉了，在 Dialog 中，board%n 是很小的区域，不会引起视觉冲突；关于棋子的摆放，在绘制完棋盘之后，我们同样也获取了每个棋子位的坐标，落子的过程其实就是一个贴图的过程，在指定坐标的位置使用绘图函数绘出棋子，同样，取出棋子也是擦去棋子的图形；程序在算法上使用回溯算法，即从第一行起逐行放置皇后，每放置一个皇后均需要对第 1，2，…，8 列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，则将该行 i 的列位置 j 保存在数组的 queen[i]=j 变量中，然后继续在下一行寻找安全位置，若当前试探的列位置不安全，则用下一列试探；当 8 列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，修改最后一行保存的皇后位置，然后继续试探。同时根据 queen[i]的值摆放和去除棋子，queen[i]=j>0 是，在（i，j）位置摆棋，queen[i]<0 时，清除该行的棋子；关于“死区”的标记。落子规则为逐行落子，那么就不存在两个棋子

同行的情况，我们只需要考虑是否同列和是否在同一斜线；观察落子点的坐标，同一列的任意两个位置坐标（i1,j1）、（i2,j2），有 j1 =j2 ，可以设置布尔型数组 mk[n]来存储标记信息，当 mk[j]=true 时 j 列为 “死区”；在棋盘中的斜线，有左上右下和右上左下两种，各有 2n-1 条，其中在同一左上右下斜线上的两点（i1,j1）、（i2,j2），有这样的特征，i1-i2=j1-j2，即 i1+j1=i2+j2，可以设置标记数组 lk[2n-1]，lk[i+j]=true 表示该点所在坐上右下斜线为“死区”；同理，右上左下的斜线上的两点坐标有关系：i1-j1=i2-j2，可以设置数组 rk[2n-1] 来标记，当 lk[n+i-j]=true 时，表示当前点所在右上左下斜线为“死区”。第三部分概要设计和数据结构：根据问题分析提供的解决方案，实现棋盘绘制和棋子摆放清除功能，可以选择的存储结构为线性存储结构，逻辑结构为图形结构，并构造一种新的数据结构 QueenPanel，定义在这个数据结构上的功能有，按提供的规格绘制棋盘，按指定的位置绘制棋子和清除棋子。实现主窗口和棋子摆放规则，可以选用线性存数结构和图形逻辑结构构造一个新的数据结构，定义在其上的功能为根据回溯法的规则改变*queen 中皇后位置，并将其传递给 QueenPanel 的对象，使其按要求实现棋子的摆放，直到出现正确的放置方法。 1.算法描述： A、数据初始化。 B、从 i 行开始摆放第 i 个皇后（因为这样便可以符合每一横行只有一个皇后的要求），先测试当前位置（i，j）是否等于 false（未被占领）。如果是，摆放第 1 个皇后，并宣布占领（竖列、斜列一起设置 mk[j]=true、rk[n+i-j]=true、 lk[i+j]=true），记录该皇后的位置 queen[i]=j，并摆放棋子，接着进行递归；如果不是，测试下一个位置（i，j+1），但是如果当 i<=8，m=8 时，发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不断“回溯”的寻找解的方法，称为“回溯法”。 C、使用数组实现回溯法的思想。 D、当 i=8，j>=8 时，结束。如图 1 所示，从第 1 行开始，先将棋子摆在位置（1,1）上，然后依次每行的纵坐标为 3，5，2，4，在第 5 行之后，由图 2 可以看出，已经没有地方可以继续落子了，这个时候，就要开始回溯了，由图 3 的树形就够可以看出，下面会取回第五行的棋子，并重新摆在 8 位置；依次下去，知道摆满 8 个棋子；图 3 显示的是一次完整的走棋过程，得到一种正确的放置方法：（1，1）,（2，5）, （3，8）,（4，6）,（5，3）,（6，7）,（7，2）,（8，4）。

图 1 棋子摆放顺序示意图图 2 当前棋盘状态图图 3 棋子摆放的树形示意图

2.算法流程图：详细设计： 1.类的设计： class QueenPanel : public CStatic { // Construction public: QueenPanel(); 图 4 算法流程图第四部分

资料库

八皇后课程设计（详细版）.doc

相关推荐

开发技术

热门标签

最新资料