文档介绍：数据结构课程设计报告
八皇后问题
设计任务书
课题
名称
八皇后
设计
目的
调研并熟悉八皇后的基本功能、数据流程与工作规程;
学习八皇后相关的算法和基于VC++集成环境的编程技术;
通过实际编程加深对基础知识的理解,提高实践能力;
学习开发资料的收集与整理,学会撰写课程设计报告。
实验
环境
微型电子计算机(PC);
安装Windows 2000以上操作系统,Visual C++。
任务
要求
利用课余时间去图书馆或上网查阅课题相关资料,深入理解课题含义及设计要求,注意材料收集与整理;
在第16周末之前完成预设计,并请指导教师审查,通过后方可进行下一步工作;
本课题要求至少用三种方法解决八皇后问题,输入棋盘的阶层,然后显示共有多少种布局方案,并显示每一种方案的具体情况。
结束后,及时提交设计报告(含纸质稿、电子稿),要求格式规范、内容完整、结论正确,正文字数不少于3000字(不含代码)。
工作进度计划
序号
起止日期
工作内容
1
~
在预设计的基础上,进一步查阅资料,完善设计方案,形成书面材料。
2
. 7~
设计总体方案,构建、绘制流程框图,编写代码,上机调试。
3
~
测试程序,优化代码,增强功能,撰写设计报告。
4
~
提交软件代码、设计报告,参加答辩,根据教师反馈意见,修改、完善设计报告。
指导教师(签章):

2013 年 5 月 15 日
摘要:
众所周知的八皇后问题是一个非常古老的问题,具体如下:在8*8的国际象棋棋盘上放置了八个皇后,要求没有一个皇后能吃掉另一个皇后,即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。要求编写实现八皇后问题的递归解法或非递归解法,对于任意给定的一个初始位置,输出八皇后问题的一个布局。本次设计旨在学习各种算法,训练对基础知识和基本方法的综合运用及变通能力,增强对算法的理解能力,提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。
要求熟练运用C++语言、基本算法的基础知识,独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过对题意的分析与计算,用递归法回溯法及枚举法解决八皇后是比较适合的。递归是一种比较简单的且比较古老的算法。回溯法是递归法的升华,在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而枚举法,更是一种基础易懂简洁的方法。把它们综合起来,就构成了今天的算法。不论用什么法做这个课题,重要的就是先搞清楚哪个位置是合法的放皇后的位置,哪个不能,要先判断,后放置。
关键词:八皇后;递归法;回溯法;数组…….
1 课题综述
八皇后问题概述
八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850提出;在8×8格的国际象棋上摆放八皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后人有人用图论的方法解出92宗结果。虽然问题的关键在于如何判定某个皇后所在的行、列、斜线是否有别的皇后;可以从矩阵的特点上找到规律,如果在同一行,则行号相同;如果在同一列上,则列号相同;如果同在“/”斜线上的行列值之和相同;如果在对角线上,则行列号之和或之差相等,逐个纪录符合题意的情况,最终得出解。(如图1-1,是八皇后问题的一个实例图)
图1-1八皇后棋盘实例
预期目标
运用C++程序设计的编程思想编写代码,实现八皇后问题的所有(92种)摆放情况。要求在DOS界面上显示出每一种方式。
1
面对的问题
需要用三种方法解决八皇后问题,在这里需要查阅大量资料并多加练习,才能成功编写程序。主要要解决下面的问题:
冲突:包括列、行、两条对角线;
列:规定每一列放一个皇后,就不会造成列上的冲突;
行:当第i行被某个皇后占据时,该行所有空格就都不能放置其他皇后;
对角线:对角线有两个方向,在同一对角线上的所有点都不能有冲突。
2 需求分析
涉及到的知识基础
类
类定义
类函数定义
函数
函数的定义

选择结构
用if语句实现选择结构设计
if语句嵌套
while和do-while语句
循环结构
2