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

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

2 2009.06. 72009.06.10 设计总体方案，构建、绘制流程框图，编写代码， 上机调试 3 2009.06.112009.06.1 2 测试程序，优化代码，增强功能，撰写设计报告 4 2009.06.122009.06.1 3 提交软件代码、设计报告，参加答辩，根据教师反 馈意见，修改、完善设计报告 指导教师（签章）： 年 月 日 摘要： 众所周知的八皇后问题是一个非常古老的问题，具体如下：在 8*8 的国际象棋 棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不 处于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础要求编写实 现八皇后问题的递归解法或非递归解法，对于任意给定的一个初始位置，输出八皇后 问题的一个布局本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运 用及变通能力，增强对算法的理解能力，提高软件设计能力在实践中培养独立分析 问题和解决问题的作风和能力 要求熟练运用 C+语言、基本算法的基础知识，独立编制一个具有中等难度的、 解决实际应用问题的应用程序通过对题意的分析与计算，用递归法回溯法及枚举法 解决八皇后是比较适合的。

递归是一种比较简单的且比较古老的算法回溯法是递归 法的升华，在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索 遍才结束而枚举法，更是一种基础易懂简洁的方法把它们综合起来，就构成了今 天的算法不论用什么法做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后 的位置，哪个不能，要先判断，后放置 关键词：八皇后；递归法；回溯法；数组；枚举法. 目目 录录 1 1 课题综述课题综述 1.11.1 八皇后问题概述八皇后问题概述- 1.21.2 预期目标预期目标- 1.31.3 八皇后问题课题要求八皇后问题课题要求- 1.41.4 面对的问题面对的问题- 2 2 需求分析需求分析 2.12.1 涉及到的知识基础涉及到的知识基础- 2.22.2 总体方案总体方案- 3 3 模块及算法设模块及算法设 计计 3.13.1 算法描述算法描述- 3.23.2详细流程图详细流程图- 4.4.代码编写代码编写 5 5 程序调试分程序调试分 析析 6 6 运行与测运行与测 试试 总总 结结 1 1 课题综述课题综述 1.11.1 八皇后问题概述八皇后问题概述 八皇后问题是一个古老而著名的问题该问题是十九世纪著名的数学家高 斯 1850 提出；在 88 格的国际象棋上摆放八皇后，使其不能互相攻击，即任 意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯 认为有 76 种方案1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的 解，后人有人用图论的方法解出 92 宗结果虽然问题的关键在于如何判定某个 皇后所在的行、列、斜线是否有别的皇后；可以从矩阵的特点上找到规律，如 果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在“/”斜线 上的行列值之和相同；如果在对角线上，则行列号之和或之差相等，逐个纪录 符合题意的情况,最终得出解如图 1-1，是八皇后问题的一个实例图) 图 1-1 八皇后棋盘实例 1.21.2 预期目标预期目标 运用 C+程序设计的编程思想编写代码，实现八皇后问题的所有（92 种） 摆放情况要求在 DOS 界面上显示出每一种方式 1.31.3 八皇后问题课题要求八皇后问题课题要求 编写代码，用至少三种方法解决八皇后问题运行程序后，显现下面的参 考界面： 八皇后问题 = 1方法一 2方法二 3方法三 请选择（请选择（1 1、2 2 或或 3 3，0 0：退出）：退出）： 图 1-2 输出界面实例 选择一个菜单后，要求输入棋盘的阶层，即 N输入后，显示共有多少种布局 方案，并显示每一种方案的具体情况，如下图： 77:77: (0,2)(0,2) (1,0)(1,0) (2,6)(2,6) (3,4)(3,4) (4,7)(4,7) (5,1)(5,1) (6,3)(6,3) (7,5)(7,5) 78:78: (0,7)(0,7) (1,1)(1,1) (2,4)(2,4) (3,2)(3,2) (4,0)(4,0) (5,6)(5,6) (6,3)(6,3) (7,5)(7,5) 图 1-3 输出样式实例 1.41.4 面对的问题面对的问题 需要用三种方法解决八皇后问题，在这里需要查阅大量资料并多加练习，才 能成功编写程序。

主要要解决下面的问题： 冲突：包括列、行、两条对角线； 1. 列：规定每一列放一个皇后，就不会造成列上的冲突； 2. 行：当第 i 行被某个皇后占据时，该行所有空格就都不能放置其他皇后； 3. 对角线：对角线有两个方向，在同一对角线上的所有点都不能有冲突 2 2 需求分析需求分析 2.12.1 涉及到的知识基础涉及到的知识基础 在本次的课程设计中，用到的知识点主要有：类、函数、选择结构里的条 件语句、循环结构里的 while 语句以及 for 循环语句、控制语句里的 break 语 句、以及字符串函数的运用等等,并且应用到递归、回溯及穷举等比较经典的 算法 2.1.12.1.1 类类 2.1.1.12.1.1.1 类定义 类就是用户自定义的数据类型 类定义的一般形式如下： class 类名 细节；(数据成员，成员函数) ; 2.1.1.22.1.1.2 类函数定义 类成员函数类的成员函数通常在类外定义，一般形式如下: 返回类型 类名:函数名(形参表) 函数体; 双冒号: : : :是域运算符，主要用于类的成员函数的定义 2.1.22.1.2 函数 2.1.2.12.1.2.1 函数的定义 定义函数需要指明：函数执行结果返回值的类型、函数名、形式参数(简称 形参)和函数体。

一般形式为： 数据类型 函数名（行参表） 语句序列； Return 合适类型数值 2.1.2.22.1.2.2 2.1.2.32.1.2.3 函数调用 调用一个函数之前必须对该函数进行说明 函数调用由函数名和函数调用运算符( )组成，( )内有 0 个或多个逗号分 隔的参数(称为实参)每一个参数是一个表达式，且参数的个数与参数的类型 要与被调函数定义的参数(称为形参)个数和类型匹配 当被调函数执行时，首先计算实参表达式，并将结果值传送给行参，然后 执行函数体，返回的返回值被传送到调用函数 如果函数调用后有返回值，调用表达是可以用在表达式中，而无参函数的 调用是一个单独的语句 2.1.32.1.3 选择结构选择结构 2.1.3.12.1.3.1 用 if 语句实现选择结构设计 if 语句的基本形式可分为两种： （1） if (表达式) 语句 其执行过程是，首先计算表达式的值，若不为 0，条件判断为真，则执行( )后 面的语句，否则，if 语句中止执行，即不执行( )后面的语句 （2） if(表达式) 语句 1 else 语句 2 其执行过程是，首先计算表达式的值，若不为 0，条件判断为真，则执行( )后 面的语句，否则执行语句 2。

2.1.3.22.1.3.2 if 语句嵌套 if 语句中的任何一个子句可以是任意可执行语句，当然也可以是一条 if 语句，这种情况称为 if 语句嵌套当出现 if 语句的嵌套时，不管书写格式如 何，else 格式都将与它前面最靠近的未曾配对的 if 语句相配对，构成一条完 整的 if 语句它的格式为： if(表达式 1) 语句 1； else if （表达式 2） 语句 2； else if （表达式 n） 语句 n； else 语句 n1； 2.1.3.32.1.3.3 while 和 do-while 语句 while 语句用来实现“当型”循环结构，即先判断表达式，然后判断循环 条件是否成立其一般形式为： do 语句；/循环体 while（条件表达式）； 其中要注意的是 while 后面的括号理是表达式而不是语句，表达式是没有 分号的；而 do-while 中最后结束时要有分号 2.1.42.1.4 循环结构 2.1.4.12.1.4.1 for 语句 这种循环语句不仅用于循环次数已知的情况，还能用于循环次数预先不能 确定只给出循环结束条件的情况下 for 语句的一般形式： for (表达式 1；表达式 2；表达式 3) 语句；/循环体 其执行的过程有以下几个步骤： 求解表达式 1； 求解表达式 2，若其值为真，则执行 for 语句中指定的循环体语句，然后 执行下面的第 3)步。

若为假，则结束循环； 求解表达式 3； 转回上面第 2）步继续执行； 循环结束，执行 for 语句后面的其他语句 2.1.4.22.1.4.2 Break 语句 该语句被限定使用在任一种循环语句和 switch 语句中，但 break 语句仅仅 退出包含该 break 语句的那层循环，即 break 语句不能使程序控制退出一层以 上的循环 2.1.52.1.5 字符串处理函数字符串处理函数 字符比较函数 strcmp 格式：strcmp(字符串 1，字符串 2) 它的功能是，比较字符串 1 和字符串 2 如果字符串 1 小于字符串 2，该函数返回一个负整数值；如果字符串 1 等于字 符串 2，该函数返回 0；如果字符串 1 大于字符串 2，该函数返回一个正整数值 2.22.2 总体方案总体方案 显然问题的键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后； 可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上， 则列号相同；如果同在斜线上的行列值之和相同；如果同在/斜线上的行列值 之差相同；如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列 号之差的绝对值相同。

下图是一个范例(图 2-1 是八皇后排列方式在 vs6.0 中的 结果显示，图 2-2 是棋盘中八皇后位置显示) 将把皇后问题用三种方法表示出来,三种方法用 switch 语句连接. 图 2-1 “1”作为皇后 图 2-2 棋盘中的八皇后位置显示 3 3 模块及算法设计模块及算法设计 3.13.1 算法描述算法描述 3.1.13.1.1 递归法 递归是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的 重入现像. 递归算法一般用于解决三类问题： (1)数据的定义是按递归定义的Fibonacci函数) (2)问题解法按递归算法实现回溯) (3)数据的结构形式是按递归定义的树的遍历，图的搜索) 能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将 它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解， 并且这些规模较小的问题也能采。