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

数据结构课程设计报告数据结构课程设计报告 八八皇皇后后问问题题 设计任务书 课题 名称 八皇后 设计 目的 1 调研并熟悉八皇后的基本功能 数据流程与工作规程 2 学习八皇后相关的算法和基于 VC 集成环境的编程技术 3 通过实际编程加深对基础知识的理解 提高实践能力 4 学习开发资料的收集与整理 学会撰写课程设计报告 实验 环境 1 微型电子计算机 PC 2 安装 Windows 2000 以上操作系统 Visual C 6 0 开发工具 任务 要求 1 利用课余时间去图书馆或上网查阅课题相关资料 深入理解课题含义及 设计要求 注意材料收集与整理 2 在第 16 周末之前完成预设计 并请指导教师审查 通过后方可进行下一 步工作 3 本课题要求至少用三种方法解决八皇后问题 输入棋盘的阶层 然后显 示共有多少种布局方案 并显示每一种方案的具体情况 4 结束后 及时提交设计报告 含纸质稿 电子稿 要求格式规范 内 容完整 结论正确 正文字数不少于 3000 字 不含代码 工作进度计划 序号起止日期工 作 内 容 12009 06 7 2009 06 7 在预设计的基础上 进一步查阅资料 完善设计方 案 形成书面材料 2 2009 06 7 2009 06 10 设计总体方案 构建 绘制流程框图 编写代码 上机调试 3 2009 06 11 2009 06 1 2 测试程序 优化代码 增强功能 撰写设计报告 4 2009 06 12 2009 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 提出 在 8 8 格的国际象棋上摆放八皇后 使其不能互相攻击 即任 意两个皇后都不能处于同一行 同一列或同一斜线上 问有多少种摆法 高斯 认为有 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 语句 n 1 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的问题 设法将 它分解成规模较小的问题 然后从这些小问题的解方便地构造出大问题的解 并且这些规模较小的问题也能采用同样的分解和综合方法 分解成规模更小的 问题 并从这些更小问题的解构造出规模较大问题的解 3 1 23 1 2 回溯法 回溯算法也叫试探法 它是一种系统地搜索问题的解的方法 按选优条件 向前搜索 以达到目标 但当探索到某一步时 发现原先选择并不优或达不到 目标 就退回一步重新选择 这种走不通就退回再走的技术为回溯法 而满足 回溯条件的某个状态的点称为 回溯点 可用回溯法求解的问题P 通常要能表达为 对于已知的由n元组 x1 x2 xn 组成的一个状态空间E x1 x2 xn xi 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的所有解 树T类似于检索树 它可以这样构造 设Si中的元素可排成xi 1 xi 2 xi mi 1 Si mi i 1 2 n 从根开始 让T的第I层的每一个结点都有mi个儿子 这 mi个儿子到它们的双亲的边 按从左到右的次序 分别带权xi 1 1 xi 1 2 xi 1 mi i 0 1 2 n 1 照这种构造方式 E中的一个n元组 x1 x2 xn 对应于T中的一个叶子结点 T的根到这个叶子结点的路径上 依次的n条边的权分别为x1 x2 xn 反之亦然 另外 对于任意的 0 i n 1 E中n元组 x1 x2 xn 的一个前缀I元组 x1 x2 xi 对 应于T中的一个非叶子结点 T的根到这个非叶子结点的路径上依次的I条边的权 分别为x1 x2 xi 反之亦然 特别 E中的任意一个n元组的空前缀 对应于T的根 因而 在E中寻找问题P的一个解等价于在T中搜索一个叶子结点 要求从T 的根到该叶子结点的路径上依次的n条边相应带的n个权x1 x2 xn满足约 束集D的全部约束 在T中搜索所要求的叶子结点 很自然的一种方式是从根出 发 按深度优先的策略逐步深入 即依次搜索满足约束条件的前缀1元组 x1i 前缀2元组 x1 x2 前缀I元组 x1 x2 xi 直到i n为止 在回溯法中 上述引入的树被称为问题P的状态空间树 树T上任意一个结 点被称为问题P的状态结点 树T上的任意一个叶子结点被称为问题P的一个解状 态结点 树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个 回答状态结点 它对应于问题P的一个解 3 1 33 1 3 穷举法 顾名思义 穷举法就是通过把需要解决问题的所有可能情况逐一试验来找 出符合条件的解的方法 对于许多毫无规律的问题而言 穷举法用时间上的牺 牲换来了解的全面性保证 尤其是随着计算机运算速度的飞速发展 穷举法的 形象已经不再是最低等和原始的无奈之举 比如经常有黑客在几乎没有任何已 知信息的情况下利用穷举法来破译密码 足见这种方法还是有其适用的领域的 可是 在实际生活中 只有很少的一些问题是真正意义上的 毫无规律 其 余的大多数仍有内在规律可循 对于这些问题 使用穷举法在效率上就显得比 较低下 而在一些对速度要求较高的区域和规模较大的问题上 效率的低下往 往是致命的 3 23 2 详细流程图 详细流程图 数据初始化 从当前点当前方 向开始 判断能 否向前走 结束程序 向前走一步 入栈 是否已到达目 标位置 输出结果 新位置作为 当前点 方向数加 1 方向数是否 超界 退回一步 退栈 是否已经回 到起点 能 否 否 否是 是 是 否 图 3 3 解决八皇后问题的基本流程图 4 4 代码编写代码编写 八皇后问题是在限制条件下的排序问题 include 数据流输入 输出 include 参数化输入 输出 include 定义杂项函数及内存分配函数 include 定义输入 输出函数 方法一 递归法 static 避免命名有冲突 棋盘初始化时 空格的地方为 放置皇后的地方为 static char Queen 8 8 static int a 8 数组a i a i 表示第i个皇后放置的列 i的范围 8 static int b 15 主对角线数组 static int c 15 从对角线数组 根据程序的运行 去决定主从对角线是 否放入皇后 static int iQueenNum 0 记录总的棋盘状态数 static int iNum 1 void iQueen int i 参数i代表行 void measure1 int iLine 横行 int iColumn 纵行 for iLine 0 iLine 8 iLine a iLine 0 列标记初始化 表示无列冲突 for iColumn 0 iColumn 8 iColumn Queen iLine iColumn for iLine 0 iLine 15 iLine 主 从对角线标记初始化 表示 没有冲突 b iLine c iLine 0 iQueen 0 void iQueen int i i为当前处理的行 int iColumn for iColumn 0 iColumn 8 iColumn if a iColumn 0 放皇后 a iColumn 1 标记 下一次该列上不能放皇后 b i iColumn 7 1 标记 下一次该主对角线上不能放皇 后 c i iColumn 1 标记 下一次该从对角线上不能放皇 后 if i 7 iQueen i 1 如果行还没有遍历 沿着某条搜索路线 依次对树中每个结点均做一次且仅做一次访问 完 进入下一行 else 否则输出 int iLine 输出棋盘状态 int iColumn cout 递归法 皇后摆放方式的第 iNum 种情况为 endl for iLine 0 iLine 8 iLine for iColumn 0 iColumn 8 iColumn cout setw 2 Queen iLine iColumn cout endl cout iNum for iLine 0 iLine 8 iLine for iColumn 0 iColumn 8 iColumn if Queen iLine iColumn cout iLine 1 iColumn 1 cout nul 从程序里调用pause命令 一 个结果一个结果地看 iNum cout endl 如果前次的皇后放置导致后面的放置无论如何都不能满足要求 则回溯 重新标记 Queen i iColumn a iColumn 0 b i iColumn 7 0 c i iColumn 0 if ends 方法二 运用类 自定义一个类 CQueen class cQueen int aQueen 8 可以在类外访问的私有成员 默认 int sum public 只能被该类的成员函数所访问的公有成员 cQueen 构造函数 确保每个对象正确地初始化 int judge int x int y void show void step cQueen cQueen 通过构造函数对aQueen 1 8 初始化 sum 0 for int i 0 i 8 i aQueen i 0 int cQueen judge int x int y 判断皇后摆放位置是否有冲突 如果没有 冲突 则返回 如果有冲突 则返回 for int i 0 i x i if aQueen i y aQueen i x i y aQueen i x i y return 0 return 1 void cQueen step 一步一步进行查找摆放 int x 0 y 0 标记皇后所在键盘位置 x代表列 y代表行 相当于坐标 while aQueen 0 8 while y 8 if judge x y 调用类函数judge x y 如果 aQueen 1 8 都已经标记 则执行该语句 aQueen x y 摆放皇后 x 进行下一列时 y 0 y进行重置 else 否则 进入下一行 y 当执行到最后一行时 继续执行下一 个if语句 if y 8 else if aQueen 0 7 y aQueen x else aQueen 0 8 if x 8 最后一列 show x y从至结束 大循环结束 if aQueen x 7 y aQueen x else y aQueen x void cQueen show 输出棋盘状态 cout 非递归法 皇后摆放方式的第 sum 种情况 endl for int i 0 i 8 i 输出八皇后的各种状态 有皇后的位置用 表示 没有皇后的位置用 表示 for int j 0 j aQueen i j cout setw 2 cout setw 2 for j j 8 j cout setw 2 cout endl cout sum for int k 0 k 8 k cout k 1 aQueen k 1 cout endl endl system pause 从程序里调用pause命令 一个结果一个结果地看 void measure2 cQueen a a step 方法三 穷举法 使用优化后的穷举法 用递归实现N层穷举 每调用一次穷举函数则穷举一列 const int LINE 8 const定义整新型常量LINE和ROW 8 8的棋盘 const int ROW 8 void queen int row int rec row为当前穷举的列 rec 记录已穷举的 信息 rec 3 2代表 3 2 已放下棋子 bool isqueen int i int rec int row 判断当前i是否与已放下的棋子能 相互攻击 void printqueen int rec 输出符合条件的棋子摆放方式 void measure3 int rec 9 0 记录穷举信息数组 queen 1 rec 执行八皇后 system pause void queen int row int rec 八皇后函数 int tmprec ROW 1 0 向下一列穷举传递信息时使用tmprec 不丢失rec的记录 for int i 1 i row i tmprec i rec i 复制数组 if row ROW 不是最后一列时 第ROW列即为最后一列 for i 1 i ROW i if isqueen i rec row i与已放下的棋子不能相互攻击时 tmprec row i queen row 1 tmprec 继续穷举下一列 else 最后一列时 for i 1 i ROW i if isqueen i rec row i与已放下的棋子不能相互攻击时 tmprec row i printqueen tmprec 输出符合条件的棋子摆放方式 bool isqueen int i int rec int row 判断当前i是否与已放下的棋子能 相互攻击 row i 即是此次穷举出来的棋子的坐标 if row 1 return 1 第一列 for int j 1 j row j if rec j i rec j i row j rec j i row j 如果 有棋子在 同一直线 有棋子在同一斜线 return 0 return 1 void printqueen int rec 输出符合条件的棋子摆放方式 char q LINE 1 ROW 1 0 static int num 1 记录已输出符合条件的棋盘数量 for int i 1 i LINE i for int j 1 j ROW j if rec i j q i j else q i j 将一维记录转换成LINE ROW的矩阵 方便打印 cout 穷举法 皇后摆放方式第 num 种情况 endl 输 出数量 for i 1 i ROW i for int j 1 j ROW j cout setw 2 q i j cout endl cout num for i 1 i ROW i for int j 1 j ROW j if rec i j cout i j cout endl endl num system pause void menu 输出界面 cout t endl cout t endl cout t endl cout t 八皇后问题 endl cout t endl cout t 1 方法一 递归法 endl cout t 2 方法二 运用类 endl cout t 3 方法三 穷举法 endl cout t 0 后退 endl cout t endl cout t 请选择 1 2 或者0 endl cout t endl cout t endl int main 主函数 for menu cout endl cout number switch number case 1 measure1 break case 2 measure2 break case 3 measure3 break case 0 return 0 default cout 抱歉 没有该选项 请重新作出选择 endl return 0 5 5 程序调试分析程序调试分析 1 运行时有些函数的头文件未定义 导致无法进行编译 而且在调试时有 些头文件的使用范畴弄混淆了 2 开始编第一种方法 递归回溯 时 for与if的循环嵌套未能很好掌握 导致几次调试都出现比较严重的错误 且在运用该方法时 未能将八皇后问题 的具体思路搞清 没有考虑 如果前次的皇后放置导致后面的放置无论如何都 不能满足要求 的问题 3 在统计方法的个数时 未将累加的那个整型变量进行初始化 导致无法 显示 八皇后摆放的是 第X种情况 也无法统计出八皇后的排列方式是否一 定是92种情况 4 在第三种方法 穷举 编译时 开始我把二维数组定义成整型 但其后在 输出棋盘格式时 更本无法调试成功 出现了类型之间的冲突 因为在输出时 我又给那二维数组付成了字符型 5 未用setw 函数时 显示的结果相当难看 所定义的标志符都紧靠在一 起 多加了一个换行符后 各种情况的间距增大 阅读时舒服多了 6 如果将92种情形全部打印 则前面的几十种情况将无法显示出 要想看 到前面的状态 必须添加一个控制语句 使其能一个一个的输出 6 6 运行与测试运