C++课程设计八皇后问题

南京理工大学紫金学院南京理工大学紫金学院 VC VC 课程设计报告课程设计报告 20112011 年年 1212 月月 课 程 VC 课程设计 系 别 计算机系 班 级 学 号 姓 名 选题名称 八皇后问题 选题难易别 B 级 起止时间 2011 11 21 2011 12 22 指导教师 朱 俊 1 程序功能介绍 答 这个程序是用于解决八皇后问题的 八皇后问题等于要求八个皇后中的任意两个不能 被放在同一行或同一列或同一斜线上 做这个课题 重要的就是先搞清楚哪个位置是合法 的放皇后的位置 哪个不能 要先判断 后放置 我的程序进入时会让使用者选择程序的 功能 选 1 将会通过使用者自己手动输入第一个皇后的坐标后获得答案 选 2 将会 让程序自动运算出固定每一个皇后后所有的排列结果 2 课程设计要求 答 1 增加函数 完成每输入一组解 暂停屏幕 显示 按任意键继续 2 完善程序 编程计算八皇后问题共有集中排列方案 3 增加输入 显示在第一个皇后确定后 共有几组排列 4 将每组解的期盼横向排列输出在屏幕上 将五个棋盘并排排列 即一次 8 行同时 输出 5 个棋盘 同样完成一组解后屏幕暂停 按任意键继续 5 求出在什么位置固定一个皇后后 解的数量最多 在什么位置固定皇后后 解的 数量最少 最多的解是多少 最少的解是多少 并将最多 最少解的皇后位置及所有的解 求出 同样 5 个一组显示 3 对课程题目的分析与注释 答 众所周知的八皇后问题是一个非常古老的问题 问题要求在一个 的棋盘上放上 个皇后 使得每一个皇后既攻击不到另外七个皇后 也不被另外七个皇后所攻击 按照 国际象棋的规则 一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋 子 因此 本课程设计的目的也是通过用 C 语言平台在一个 的棋盘上放上 个皇 后 使得每一个皇后既攻击不到另外七个皇后 也不被另外七个皇后所攻击的 92 种结构予 以实现 使用递归方法最终将其问题变得一目了然 更加易懂 首先要用到类 将程序合 理化 我编辑了一个盘棋 8 8 的类 class Board 还有个回溯法的类 class Stack 关 键的类好了 然后编辑好类的成员 然后编辑主函数利用好这些类的成员 让其运算出结 果 4 程序设计和说明 说明算法思想 设计思路 给出重要的 关键的代码 答 算法思想 关键代码 class Stack private SType data SSize int Top public Stack Top 0 Stack bool isEmpty return Top int Size return Top bool Push SType 处理压栈 bool Pop SType 处理出栈 bool StackTop SType 处理复制栈顶的数据 bool Stack Push SType d 将整数 d 压栈 栈顶加 1 if Top SSize 栈内数据已满 操作不成功 return false else data Top d Top return true bool Stack Pop SType else Top 先动栈顶 再出数据 d data Top return true bool Stack StackTop SType else d data Top 1 return true enum States used free class Board 一盘棋 8 8 private States Rows 8 DiagsLR 15 DiagsRL 15 行 左右斜线 public char board 8 8 Board Board bool isAttacked int int void Print void PlaceQueen int int void RemoveQueen int int Board Board 构造函数 初始化为空 for int i 0 i 8 i Rows i free for int j 0 j 8 j board i j for int k 0 k 15 k DiagsLR k DiagsRL k free void Board Print 显示一组排列结果 cout endl for int i 0 i 8 i for int j 0 j 8 j cout board i j cout endl bool Board isAttacked int row int col 判断是否冲突 是返回 TRUE 否则返回 FALSE int diagLR col row 7 该皇后的右倾斜线的所有位置 int diagRL row col 该皇后的左倾斜线的所有位置 if Rows row used DiagsLR diagLR used DiagsRL diagRL used return true return false void Board PlaceQueen int row int col 放皇后 int diagLR col row 7 右倾斜线 int diagRL row col 左倾斜线 board row col Q Rows row used 该行不能再放置 DiagsLR diagLR used 左倾斜线上不能再放置 DiagsRL diagRL used 右倾斜线上不能再放置 void Board RemoveQueen int row int col 移去皇后 int diagLR col row 7 int diagRL row col board row col Rows row free DiagsLR diagLR free DiagsRL diagRL free int comp char a 8 8 char b 8 8 定义比较函数 for int i 0 i 8 i for int j 0 j 8 j if a i j b i j return 1 return 0 主函数开始 int main void do while 8 kaishi char xz cout t t 请您选择程序的功能 n n n cout 如果您想通过自己输入第一个皇后的坐标获得答案 请选择 1 n cout 如果您想让程序自动运算出所有的排列结果 请选择 2 n n cout xz switch xz case 1 do char PrintBoard 100 8 8 Stack rowStack int qRow qCol col row attacked exitLoop m 0 Board myBoard cout 请输入第一个皇后的坐标 Row 行 和 Col 列 nRow qRow cout Col qCol 第一个皇后位置 myBoard PlaceQueen qRow qCol if qCol 0 col 1 else col 0 row 0 do while row 8 超界 exitLoop 0 if attacked myBoard isAttacked row col 若无皇后 条件成立 myBoard PlaceQueen row col 放皇后 rowStack Push row 皇后所在行入栈 row 0 从 0 行开始找放置点 col 列号加 1 if col qCol col 继续下一列 exitLoop 1 if exitLoop break 找到退出本层循环 else row 置一个皇后不成功 继续行循环 if col 8 static int p int i j for i 0 i 8 i for j 0 j 0 回到 0 列 int n m int m1 5 int p 0 int s 0 int i j do if n p 5 m1 n for i 0 i 8 i for p s p m1 p for j 0 j 8 j cout PrintBoard p i j cout cout endl s p 一次 8 行同时输出 5 个棋盘 p p 1 m1 m1 5 n m1 5 n cout n n flush if m1 n m1 m1 5 while m1 n cout 当皇后坐标为 qRow qCol 时的解的个数为 m t t n n n cout 选择 1 继续程序 n 选择 2 结束程序 n n n char xz2 cin xz2 switch xz2 case 1 goto kaishi break case 2 goto end break while 1 break 下面是程序自动运算所有结果的程序 case 2 int m 0 int qRow qCol int rmax rmin cmax cmin min max char zzz 1000 8 8 int compare 8 8 char news 100 8 8 int ii jj kk qq int nn for qRow 0 qRow 8 qRow for qCol 0 qCol 8 qCol Stack rowStack int col row attacked exitLoop cmp 0 Board myBoard myBoard PlaceQueen qRow qCol if qCol 0 col 1 else col 0 row 0 do while row 8 超界 exitLoop 0 if attacked myBoard isAttacked row col 若无皇后 条件成立 myBoard PlaceQueen row col 放皇后 rowStack Push row 入栈 row 0 col if col qCol col exitLoop 1 if exitLoop break 找到退出本层循环 else row 到下一行 if col 8 myBoard Print static int p int i j for i 0 i 8 i for j 0 j 0 回到 0 列 compare qRow qCol cmp cout qRow qCol cmp t n 以下是对坐标和解的数目的输出 int n m int m1 5 int p 0 int s 0 int i j do if n p 5 m1 n for i 0 i 8 i for p s p m1 p for j 0 j 8 j cout zzz p i j cout cout endl s p 一次 8 行同时输出 5 个棋盘 p p 1 m1 m1 5 n m1 5 n cout n n flush if m1 n m1 m1 5 while m1 n cout 程序自动求出了所有的答案的个数为 m 8 种 n 程序自动排除重复 的答案后的个数为 92 种 n nn sizeof zzz sizeof char 64 for ii 0 ii 100 ii for qq 0 qq nn qq if comp news ii zzz qq for jj 0 jj 8 jj for kk 0 kk 8 kk news ii jj kk zzz qq jj kk 接下来是进行比较大小 min max compare 0 0 rmax rmin cmax cmin 0 初始化过程记录大小值的行列号 for qRow 0 qRow 8 qRow for qCol 0 qColmax max compare qRow qCol rmax qRow cmax qCol if compare qRow qCol min min compare qRow qCol rmin qRow cmin qCol cout n n cout 在 rmax cmax 固定一个皇后的数目最多 个数为 max n cout 在 rmin cmin 固定一个皇后的数目最少 个数为 min n cout n n n cout 选择 1 继续程序 n 选择 2 结束程 序 n n n char xz2 cin xz2 switch xz2 case 1 goto kaishi break case 2 goto end break while 8 end return 0 5 课程设计中遇到的问题及解决方法 答 当用 printf 输出时 出现了一些错误 几经调试后 发现原来是缺少了 stdio h 这样一个头 文件 添加了头文件后 还出现了一些问题 逻辑错误导致程序死循环或不循环或循环一小部 分 但是编译时却没有错误 就是没有正确的输出答案 一开始我也不知道是怎么回事 通过和 同学的交流 发现是逻辑错误 经过改正后 程序终于可以运行了 冲突 包括列 行 两条 对角线 列 规定每一列放一个皇后 就不会造成列上的冲突 行 当第 i 行被某个皇后 占据时 该行所有空格就都不能放置其他皇后 对角线 对角线有两个方向 在同一对角 线上的所有点都不能有冲突 6 课程设计中所增加的功能模块 选做 答 操作更人性化了 7 课程设计结果 答 初始界面 选择 1 后的程序通过使用者自己手动输入第一个皇后的坐标后获得答案 选择 2 后程序自动运算出固定每一个皇后后所有的排列结果 8 还存在的不足之处 答 就是它只能运行一次自动求出结果后 不能重复的自动输出 输出不够美观 程序不 够简洁 9 对课程设计的感想和心得体会 答 通过了这几个星期的程序设计 我从中得到了许多的经验以及软件设计的一些新的思 路 从这个八皇后问题设计以及分析中 本人从中理解到了数据结构对于计算机软件设计 的重要性 它的使用 可以改变一个软件的运行周期 也可以将软件的思路从繁化简 并 且都能够通过