[所有分类]八皇后问题课程设计论文.doc

合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第 二 学期 课程 数据结构与算法 课程设计名称 八皇后问题 学生姓名 殷伟峰 学号 0804012010 专业班级 08计科(2) 指导教师 王昆仑、张贯虹 2010 年 06 月 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．?使用回溯算法最终将其问题变得一目了然，更加易懂。 关键词： 八皇后 ; c++ ; 回溯法 目录 第一部分 课题综述 2 1.课题的来源及意义： 2 2.任务要求： 2 3.需求分析： 2 第二部分 课题分析 2 1.目前状况中的问题： 3 2.问题分析： 3 第三部分 概要设计和数据结构 4 1.算法描述： 4 2.算法流程图： 6 第四部分 详细设计 6 1.类的设计： 6 第五部分 上机调试 10 第六部分 用户使用说明 11 第七部分 测试结果及其分析 11 第八部分 参考文献 14 第九部分 附录 15  第一部分 课题综述：八皇后问题 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是很小的区域，不会引起视觉冲突； 关于棋子的摆放，在绘制完棋盘之后，我们同样也获取了每个棋子位的坐标，落子的过程其实就是一个贴图的过程，在指定坐标的位置使用绘图函数绘出棋子，同样，取出棋子也是擦去棋子的图形； 程序在算法上使用回溯算法，即从第一行起逐行放置皇后，每放置一个