数据结构课程设计-四、八、N皇后问题.doc

1 计算机与软件工程学院 课程设计说明书 课 程 名 称 数据结构与算法 课程设计 课 程 代 码 106014389 题 目 四 八 N 皇后问题 年级 专业 班 学 生 姓 名 学 号 312012080611523 开 始 时 间 年 月 日 完 成 时 间 年 月 日 课程设计成绩 学习态度及平 时成绩 30 技术水平与实际 能力 20 创新 5 说明书撰写质量 45 总 分 100 指导教师签名 年 月 日 八皇后问题 2 摘摘 要要 解决八皇后问题主要利用了递归法 回溯法 以及对 for 语句 数据结构中 树的灵活运用 和对栈及数组的掌握 编程实现了在 8 8 的格的国际象棋上摆放 八个皇后 使其不能相互攻击 即任意两个皇后都不能处于同一列 同一行 或 同一条斜线上面 编程实现了任意给定一个初始位置 输出八皇后问题的一个布 局 本次设计旨在学习各种算法 训练对基础知识和基本方法的综合运用及变通 能力 增强对算法的理解能力 提高软件设计能力 在实践中培养独立分析问题 和解决问题的作风和能力 关键词 关键词 递归法 回溯法 顺序栈 数组 八皇后问题 3 目目 录录 1 需求分析需求分析 6 2 开发及运行平台开发及运行平台 7 3 概要设计概要设计 8 4 详细设计详细设计 10 5 调试分析调试分析 11 6 测试结果测试结果 12 6 16 1 遇到的问题遇到的问题 12 6 26 2 调试结果调试结果 12 13 7 结论结论 14 通过这次的课程设计 让我了解了八皇后这一经典的问题 同时让我更好地掌握了栈思想以及一维通过这次的课程设计 让我了解了八皇后这一经典的问题 同时让我更好地掌握了栈思想以及一维 数组等等知识数组等等知识 以及一些书本上没有的东西 这对我以后的学习生涯以及将来步入社会起到很大的以及一些书本上没有的东西 这对我以后的学习生涯以及将来步入社会起到很大的 帮助 这次课程设计虽然花了我很多时间和精力 但很值得帮助 这次课程设计虽然花了我很多时间和精力 但很值得 因为它对我能力提高起到很大帮助 因为它对我能力提高起到很大帮助 这次课程设计也提醒我以前知识的匮乏这次课程设计也提醒我以前知识的匮乏 它给我敲响了警钟它给我敲响了警钟 让我意识到自己基础的不扎实让我意识到自己基础的不扎实 当然这当然这 次实验还是有很多问题的 比如程序设计的界面不够好 一些程序并非自己所写次实验还是有很多问题的 比如程序设计的界面不够好 一些程序并非自己所写 而是修改某些程而是修改某些程 序而成序而成 但这些不该但这些不该 在下次课程设计时不会再发生 在下次课程设计时不会再发生 14 参考文献参考文献 15 附附 录录 16 八皇后问题 4 1 需求分析 八皇后问题是一个古老而著名的问题 该问题是十九世纪著名的数学家高斯 1850 年提出的 并作了部分解答 高斯在棋盘上放下了八个互不攻击的皇后 他还认为可能 有 76 种不同的放法 这就是有名的 八皇后 问题 在国际象棋中 皇后是最有权利的一个棋子 只要别的棋子在它的同一行或同一 列或同一斜线 正斜线或反斜线 上时 它就能把对方棋子吃掉 所以高斯提出了一 个问题 在 8 8 的格的国际象棋上摆放八个皇后 使其不能相互攻击 即任意两个皇 后都不能处于同一列 同一行 或同一条斜线上面 问共有多少种解法 现在我们已 经知道八皇后问题有 92 个解答 本次课设要求指定任一初始位置 即可输出八皇后问题的所有行列布局 拓展完 成四皇后问题 八皇后问题 5 2 开发及运行平台 运行平台 Windos98 2000 以上 开发平台 Microsoft Visual C 6 0 八皇后问题 6 3 概要设计 3 13 1 结构设计理念结构设计理念 1 从 n 列开始摆放第 n 个皇后 因为这样便可以符合每一竖列一个皇后 的要 求 先测试当前位置 n m 是否等于 0 未被占领 如果是 摆放第 n 个皇后 并宣布占领 接着进行递归 如果不是 测试下一个位置 n m 1 但是如果当 n8 时 便打印出结果 3 23 2 类设计类设计 类定义 class 类名 细节 数据成员 成员函数 类函数定义 返回类型 类名 函数名 形参表 函数体 设计类 eightqueen 利用类的成员函数 Find 求解 用数据 s 1 8 表示顺序栈 栈的下标表示皇后所在的行号 栈的内容表示所在 列号 用 a j b i j c i j 三个布尔数组 初值为真 检查皇后是否在列 主对角线 从对角线上冲突 a j 0 b i j 0 c i j 0 表示未冲突 a j 1 表示 j 列冲突 范 围 1 8 b i j 1 表示第 i j 条对角线 冲突 范围 7 7 若 c i j 1 表示第 i j 条对角线 冲突 范围 2 16 如在 i j 上放置皇后 若满足 a j int s 9 Public Void print 输出结果 Void find 求一个解 八皇后问题 9 5 调试分析 在完整程序调试时由于太急于求成导致程序进行循环时出现无法运行的问题 逻 辑错误导致程序死循环或不循环或循环一小部分 后经细心改正后才把调试工作做完 做程序真的不是三两下就能完美的做好的 正应了那句话 心急吃不了热豆腐啊 但对于这个程序我由于 c 语言学的不到位以至于有些掺杂了 c 语言的有关算法 要是都用 c 来编写就再好不过了 在编写代码时 我希望能随机选择一数 X 1 92 后 能输出该种情况所对应的八 个皇后的摆放方式和每个皇后所在的位置 但想了好久 就是无法实现 而且 当 92 种情况都输出时 前面的几十种情况无法看到 要想让摆放皇后的图形和所在具体的 位置一起输出 就得修改程序让使她们一个一个地输出 这样显然比较麻烦 倘若有 一种既能把八皇后的所在位置和把皇后所有情况连续输出 我感觉就应该算是一个完 美的程序了 这还需要我一致的探索发掘下去才行 八皇后问题 10 6 测试结果 6 16 1 遇到的问题遇到的问题 1 运行时有些函数的头文件未定义 导致无法进行编译 而且在调试时有些头文 件的使用范畴弄混淆了 2 如果将 92 种情形全部打印 则前面的几十种情况将无法显示出 要想看到前面 的状态 必须添加一个控制语句 使其能一个一个的输出 6 26 2 调试结果调试结果 八皇后问题结果如图 1 所示 图 1 八皇后问题 11 四皇后问题结果如图 2 所示 图 2 八皇后问题 12 7 结论 通过这次的课程设计 让我了解了八皇后这一经典的问题 同时让我更好地掌握了 栈思想以及一维数组等等知识 以及一些书本上没有的东西 这对我以后的学习生涯以 及将来步入社会起到很大的帮助 这次课程设计虽然花了我很多时间和精力 但很值 得 因为它对我能力提高起到很大帮助 这次课程设计也提醒我以前知识的匮乏 它给 我敲响了警钟 让我意识到自己基础的不扎实 当然这次实验还是有很多问题的 比如 程序设计的界面不够好 一些程序并非自己所写 而是修改某些程序而成 但这些不该 在下次课程设计时不会再发生 八皇后问题 13 参考文献 1 苏仕华 数据结构课程设计 机械工业出版社 2 王红梅 数据结构 C 版 第 2 版 清华大学出版社 3 杨秀金 数据结构 C 版 人民邮电出版社 八皇后问题 14 附附 录录 源程序清单如下 头文件 queen h include using namespace std class eightqueen private int a 9 b 17 c 17 定义棋盘大小 int s 9 public void print void movequeen int int void find 定义成员函数 void eightqueen print int k static int num 0 cout n 行号 1 2 3 4 5 6 7 8 n cout 列号 for k 1 k 8 k cout width 4 cout s k num num 1 cout 解 num endl void eightqueen movequeen int i int j a j 1 b i j 1 c i j 9 1 输出一个解的成员函数 print void eightqueen find int i j for i 2 i 2 在当前行 1 上找安全位置 j if j 1 j s i movequeen i j j 源文件 queen cpp include queen h void main eightqueen game game find 四 八 四 八 N N 皇后问题皇后问题 include include void Queen int i int n int col int md int sd int q for int j 0 j n j if col j q i j int time 0 if i n 1 for int k 0 k n k 八皇后问题 16 cout k q k cout endl else Queen i 1 n col md sd q col j md n i j 1 sd i j 0 q