八皇后问题数据结构课程设计报告

《八皇后问题数据结构课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计报告八皇后问题设计任务书课题名称八皇后设计目的1.调研并熟悉八皇后的基本功能、数据流程与工作规程；2.学习八皇后相关的算法和基于VC++集成环境的编程技术；3.通过实际编程加深对基础知识的理解，提高实践能力；4.学习开发资料的收集与整理，学会撰写课程设计报告。实验环境1.微型电子计算机（PC）；2.安装Windows2000以上操作系统，VisualC++6.0开发工具。任务要求1.利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设计要求，注意材料收集与整理；2.在第16周末之前完成预设计，并请指

2、导教师审查，通过后方可进行下一步工作；3.本课题要求至少用三种方法解决八皇后问题，输入棋盘的阶层，然后显示共有多少种布局方案，并显示每一种方案的具体情况。4.结束后，及时提交设计报告（含纸质稿、电子稿），要求格式规范、内容完整、结论正确，正文字数不少于3000字（不含代码）。工作进度计划序号起止日期工作内容12009.06.7~2009.06.7在预设计的基础上，进一步查阅资料，完善设计方案，形成书面材料。22009.06.7~2009.06.10设计总体方案，构建、绘制流程框图，编写代码，上机调试。32009.06.11~2

3、009.06.12测试程序，优化代码，增强功能，撰写设计报告。42009.06.12~2009.06.13提交软件代码、设计报告，参加答辩，根据教师反馈意见，修改、完善设计报告。指导教师（签章）：年月日摘要：众所周知的八皇后问题是一个非常古老的问题，具体如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。要求编写实现八皇后问题的递归解法或非递归解法，对于任意给定的一个初始位置，输出八皇后问题的一个布局。本次设计旨在学习

4、各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。要求熟练运用C++语言、基本算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过对题意的分析与计算，用递归法回溯法及枚举法解决八皇后是比较适合的。递归是一种比较简单的且比较古老的算法。回溯法是递归法的升华，在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而枚举法，更是一种基础易懂简洁的方法。把它们综合起来，就构成了今天的算法。不论用什么

5、法做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。关键词：八皇后；递归法；回溯法；数组；枚举法…….目录1课题综述…………………………………………………………………………………1.1八皇后问题概述1.2预期目标1.3八皇后问题课题要求1.4面对的问题2需求分析…………………………………………………………………………………2.1涉及到的知识基础2.2总体方案3模块及算法设计……………………………………………………………………………………3.1算法描述3.2．详细流程图4.代码编写……………

6、……………………………………………………………5程序调试分析……………………………………………………………………………………6运行与测试……………………………………………………………………………………总结…………………………………………………………………………1课题综述1.1八皇后问题概述八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850提出；在8×8格的国际象棋上摆放八皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象

7、棋杂志上不同的作者发表了40种不同的解，后人有人用图论的方法解出92宗结果。虽然问题的关键在于如何判定某个皇后所在的行、列、斜线是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在“/”斜线上的行列值之和相同；如果在对角线上，则行列号之和或之差相等，逐个纪录符合题意的情况,最终得出解。(如图1-1，是八皇后问题的一个实例图)图1-1八皇后棋盘实例1.2预期目标运用C++程序设计的编程思想编写代码，实现八皇后问题的所有（92种）摆放情况。要求在DOS界面上显示出每一种方式。1

8、.3八皇后问题课题要求编写代码，用至少三种方法解决八皇后问题。运行程序后，显现下面的参考界面：八皇后问题============1．方法一2．方法二3．方法三请选择（1、2或3，0：退出）：图1-2输出界面实例选择一个菜单后，要求输入棋盘的阶层，即N。输入后，显示共有多少种布