八皇后课程设计实验报告_C++

1、设计任务书课题名称八皇后设计目的调研并熟悉八皇后的基本功能、数据流程与工作规程；学习八皇后相关的算法和基于vch集成环境的编程技术；通过实际编程加深对基础知识的理解，提高实践能力；学习开发资料的收集与整理，学会撰写课程设计报告。实验环境微型电子计算机（pc）;安装windows 2000以上操作系统，visual c+开发工具。任务要求利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设计要求，注意材料收集与整理；在第16周末之前完成预设计，并请指导教师审查，通过后方可进行下一步工作；本课题要求至少用三种方法解决八皇后问题，输入棋盘的阶层，然后显示共有多少种布局方案，并显示每一种方

2、案的具体情况。结束后，及时提交设计报告（含纸质稿、电子稿），要求格式规范、内容完整、结论正确，正 文字豹不少干3000字（不含代码）。工作进度计划序号起止日期工作内容1在预设计的基础上，进一步查阅资料，完善设计方案，形成书 面材料。2.7设计总体方案，构建、绘制流程框图，编写代码，上机调试。3测试程序，优化代码，增强功能，撰写设计报告。4提交软件代码、设计报告，参加答辩，根据教师反馈意见，修改、完善设计 报告指导教师（签章）：摘要：众所周知的八皇后问题是一个非常古老的问题，具体如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一 行、

3、同一列或同一对角线上，这是做出这个课题的基础。要求编写实现八皇后问题的递归解法或 非递归解法，对于任意给定的一个初始位置，输出八皇后问题的一个布局。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件 设计能力。在实践中培养独立分析问题和解 决问题的作风和能力。要求熟练运用c+信、基本算法的基础知识，独立编制一个具有中等难度的、解决实际应用问 题的应用程序。通过对题意的分析与计算，用递归法回溯法及枚举法解决八 皇后是比较适合的。 递归是一种比较简单的且比较古老的算法。回溯法是递归法的升 华，在用来求问题的所有解时， 要回溯到根，且根结点的所有子

4、树都已被搜索遍才结束。而枚举法，更是一种基础易懂简洁的方 法。把它们综合起来，就构成了今天的算法。不论用什么法做这个课题，重要的就是先搞清楚哪 个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。关键词：八皇后；递归法；回溯法；数组；枚举法 /1课题综述错误!未定义书签八皇后问题概述错误！未定义书签。 预期目标 错误！未定义书签。 八皇后问题课题要求错误！未定义书签。 面对的问题错误！未定义书签。2需求分析 错误”未定义书签涉及到的知识基础错误！未定义书签。总体方案错误！未定义书签3模块及算法设计错错错错错错错错错错错错错错错错错错错错错错错错错错错错误错!错未错定错算法描述错误凝舞签详细

5、流程图错误！未定义书签4.代码编写 错错错错错错错错错错错错错错错错错错错错错错错错错错错.错错错误错!错未错定5程序调试分集义错春籥错错错错错错错错错错错错错错错错错错错错错错错错,错错误错!错未错定错6运行与测试 错昔错错错错错错错错错错错错错错错错错错错错错错错误错!错未错定错 总结错错潘懿错1错错错错错错错错错错错错错错错错错错错错错,错错错误错!未错定错致谢需i概皤错错错错错错错错错错错错错错错错错错错错错错错错错错误错!错未错定错参考文献 义错书篇籥昔错错错错错错错错错错错错错错错错错错错错错错错错.错错误错!错未错定 指导教师评语重髓辅籍错错错错错错错错错错错错错错错错错错错错错

6、错错错误错!未错定错义错书错签1课题综述八皇后问题概述八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850提出；在8x8格的国际象棋上摆放八皇后，使其不能互相攻击，即任意两个皇后都不能处 于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了 40种不同的解，后人有人用图论的 方法解出92宗结果。虽然问题的关键在于如何判定某个皇后所在的行、歹i、斜线是否有别的皇 后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，贝例号相 同；如果同在“/斜线上的行列值之和相同；如果在对角线上，则行列号之和或

7、之差相等，逐 个纪录符合题意的情况最终得出解。（如图是八皇后问题的一个实例图）预期目标运用c+程序设计的编程思想编写代码，实现八皇后问题的所有（92种）摆放情况。要求在 dos界面上显示出每一种方式。八皇后问题课题要求编写代码，用至少三种方法解决八皇后问题。运行程序后，显现下面的参考界面：i八皇后问题 i1 方法一2 方法二3 方法三l请选择，2或3,ol退世 图1-2输出界面实例选择一个菜单后，要求输入棋盘的阶层，即n。输入后，显示共有多少种布局方案，并显示每一种方案的具体情况，如下图:77: (0,2) (1,0) (2,6) (3,4) (4,7) (5,1) (6,3) (7,5)冕7

8、7种状态78: (0,7) (1,1) (2,4) (3,2) (4,0) (5,6) (6,3) (7,5)第阳种状态拘*（ g*l *1*a* * * r 图13输出样式实例面对的问题需要用三种方法解决八皇后问题，在这里需要查阅大量资料并多加练习，才能成 功编写程序。主要要解决下面的问题：冲突：包括列、行、两条对角线；列：规定每一列放一个皇后，就不会造成列上的冲突；行：当第i行被某个皇后占据时，该行所 有空格就都不能放置其他皇后；对角线：对角线有两个方向，在同一对角线上的所有点都不能 有冲突。2需求分析涉及到的知识基础在本次的课程设计中，用到的知识点主要有：类、函数、选择结构里的条件语句、

9、循环结构里 的while语句以及for循环语句、控制语句里的break语句、以及字符串函数的运用等等，并 且应用到递归、回溯及穷举等比较经典的算法。类类定义类就是用户自定义的数据类型。类定义的一般形式如下：class类名（细节；（数据成员，成员函数）；类函数定义类成员函数类的成员函数通常在类外定义，一般形式如下返回类型 类名:函数名（形参表）函数体；）双冒号：:是域运算符，主要用于类的成员函数的定义。函数函数的定义定义函数需要指明：函数执行结果返回值的类型、函数名、形式参数（简称形参） 和函数体。一般形式为：数据类型 函数名（行参表）（语句序列；return合适类型数值）数据类型规定了函数返回

10、值类型。党执行函数体中的语句后，通常会产生一个结果，这就 是函 数的返回值，它可以是任何有效的类型。若函数执行后不返回值，数据类型习惯用void来表 示。如果在函数定义时没有数据类型出现，则默认为函数返回值为整型值（int）。函数调用调用一个函数之前必须对该函数进行说明。函数调用由函数名和函数调用运算符（）组 成，（）内有。个或多个逗号分隔的参数（称为实参）。每一个参数是一个表达式，且参数的个数 与参数的类型要与被调函数定义的参数（称为形参）个数和类型匹配。当被调函数执行时，首 先计算实参表达式，并将结果值传送给行参，然后执行函数体，返回的返回值被传送到调用 函数。如果函数调用后有返回值，调用

11、表达是可以用在表达式中，而无参函数的调用是一个单独的 语句。选择结构用if语句实现选择结构设计if语句的基本形式可分为两种：（1） if俵达式）语句其执行过程是，首先计算表达式的值，若不为0，条件判断为真，则执行（）后面的语句，否则，if语句中止执行，即不执行（）后面的语句。（2）计（表达式）语句1else语句2其执行过程是，首先计算表达式的值，若不为0，条件判断为真，则执行 （）后面的语句，否则执行语句2。if语句嵌套if语句中的任何一个子句可以是任意可执行语句，当然也可以是一条if语句，这种情况称为if语句嵌套。当出现if语句的嵌套时，不管书写格式如何，else格式都将与它前面 最靠近的未

12、曾配对的if语句相配对，构成一条完整的if语句。它的格式为：if （表达式1）语句1;else if （表达式2） 语句2 ；else if （表达式n） 语句n ；else 语句 n + 1 ；while 和 do-while 语句while语句用来实现“当型”循环结构，即先判断表达式，然后判断循环条件是否成立。其 一般形式为：do的“ezx vc ebiif 8 qe o谙旬；00000000oooaooo0000000a 00000 000000 .0000000图22棋盘中的八皇后位置显示3模块及算法设计算法描述递归法递归是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重

13、入现像.递归算法一般用于解决三类问题：（1） 数据的定义是按递归定义的。（fibo nacci函数）（2） 问题解法按递归算法实现。（回溯）（3） 数据的结构形式是按递归定义的。（树的遍历，图的搜索）能采用递归描述的算法通常有这样的特征：为求解规模为n的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解， 并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小 问题的解构造出规模较大问题的解。回溯法回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。按选优条件向前搜索，以达到目 标。但当探索到某一步时，发现原先选择并不优或达不到目标

14、，就退回一步重新选择，这种走 不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。可用回溯法求解的问题p,通常要能表达为：对于已知的由n元组（x1, x2,，xn）组成的一 个状态空间e=（x1, x2,，xn）冈 si , i=1, 2,，n,给定关于n元组中的一个分量的一 个约束集d,要求e中满足d的全部约束条件的所有n元组。其中si是分量xi的定义域,且|si|有限，i=1，2，n。我们称e中满足d的全部约束条件的任一 n元组为问题p的一个 解。回溯法首先将问题p的n元组的状态空间e表示成一棵高为n的带权有序树t，把在e中求问 题p的所有解转化为在t中搜索问题p的所

15、有解。树t类似于检索 树，它可以这样构造： 设si中的元素可排成xi，设2)，xi(mi-1)，|si| =mi，i=1，2，n。从 根开始， 让t的第i层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲 的边，按从左到右的次 序，分别带权xi+1，xi+1(2)，xi+1(mi)，i=0，1，2，n-1。照这种构造方 式，e中的一个n元组(x1，x2，xn)对应于t中的一个叶子结点，t的根到这个叶舌尊点 的路径上依次的n条边的权分别为x1，x2，xn，反之亦然。另外，对于任意的ow i- 1i1 e中n元组(x1，x2，xn)的一个前缀i元组(x1，x2，xi)对应于t中的一个非叶子 结

16、点，t的根到这个非叶子结点的路径上依次的i条边的权分别为x1, x2,，xi，反之亦然。 特别，e中的任意一个n元组的空前缀0，对应于t的根。因而，在e中寻找问题p的一个解等价于在t中搜索一个叶子结点，要求从t的根到该叶子结 点的路径上依次的n条边相应带的n个权xi, x2,，xn满足约束集d的全部约束。在t中 搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次 搜索满足约束条件的前缀1元组(xli)、前缀2元组(xi, x2)、，前缀i元组(xi, x2,，xi),，直到i=n为止。在回溯法中，上述引 入的树被称为问题p的状态空间树；树t上任意一个结点被称为问

17、题p的状态结点；树t上的 任意一个叶子结点被称为问题p的一个解状态结点；树t上满足约束集d的全部约束的任意一 个叶子结点被称为问题p的一个回答状态结点，它对应于问题p的一个解。穷举法顾名思义，穷举法就是通过把需要解决问题的所有可能情况逐一试验来找出符合条件 的解的方法，对于许多毫无规律的问题而言，穷举法用时间上的牺牲换来了解的全面性保 证，尤其是随着计算机运算速度的飞速发展，穷举法的形象已经不再是最低等和原始的无奈 之举，比如经常有黑客在几乎没有任何已知信息的情况下利用穷举法来破译密码，足见这种方 法还是有其适用的领域的。可是，在实际生活中，只有很少的一些问题是真正意义上的“毫无 规律”，其余

18、的大多数仍有内在规律可循，对于这些问题，使用穷举法在效率上就显得比较 低下，而在一些对速度要求较高的区域和规模较大的问题上，效率的低下往往是致命的。详细流程图图33解决八皇后问题的基本流程图4代码编写八皇后问题是在限制条件下的排序问题include。法一：递归法ii nendl;2方法二：运用类3方法三：穷举法0 ,后退请选择 2,或者0）：v niejnoa皇后问题1 .方法一（递归回溯）iiii2 .莫法二（圣城冬 l方法三穷举法）请选择2或3, 0：退出:ii清从3中选择一1嘤：.飞、探营会计代诗debug v 1星后代希c=3 i世* m * 0x x * 关 * bi：s,2”6.s

19、oc9-4、?0： 工评（2,23,5）4,35，6，7,48,6 （穷举递归法）皇后摆放万式第91种情兄:e x .*. * x * *头 * x * q * ，* m * * * x x c x x x * x m 关g 头 * 0 *x兴力学递归法）皇后摆放方式第92种情.兄:v2： (1评)(2,4)04务3)清接化瓦暹维续二卜、制呈s计wcsadebugl，呈o诵亦h请选择g 2或缶0；退出九然这次实验还是有很多问题的。比如程序设计的界面不够好，一些程序并非自己所写，而 是修改某些程序而成，但这些不该，在下次课程设计时不会再发生.在编写代码时，我希望能随机选择一数x (192)后，能

20、输出该种情况所对应的八个皇后的摆放方式和每个皇后所在的位置，但想了好久，就是无法实现。而且，当92种 情况都输出时，前面的几十种情况无法看到，要想让摆放皇后的图形和所在具体的位置一 起输出，就得修改程序让使她们一个一个地输出，这样显然比较麻烦。针对八皇后这个课题，也许表层只局限于对八个皇后的摆放，但还可以对更多的情况进行 探讨分析，比如九皇后，十皇后等等。在报告正文中已经多次提到关于n皇后的设计方 法，但只是一带而过，有些问题很难通过一个报告设计就轻而易举的得到解决，还需要花 费更多的时间。也许随着皇后个数的增多，程序运行的时间将变得很长，我们能否将运行 的时间缩短呢致谢课程设计终于告一段落了，一周的努力过后，也算是颇有收获，很多以前不清楚、不熟悉 的内容都在这一周的努力中得到了锻炼，感谢老师给予的大量帮助及指导，感谢同学们的 帮助，才让我顺利完成了这次的课程设计！通过他们们的帮助，我深刻体会到：做程序设 计需要团队共同努力，共同贡献自己的力量，才能编写出一段好的程序，谢谢你们！ 在此，由衷的感谢淮阴工学院、计算机工程系提供的实践机会，实验室人员提供的实验环 境，让我可以在不断地调试中完善程序；感谢指导教师王晓燕、戴俊峰的辛勤指导，让我 认识这个课题、熟悉这个课题并且最后完成这个课题；感谢同组同学的互帮互助，提供 那么多经典程序供我参考并且指出了许多我的编程过程中出现的问题；感