合肥学院
计算机科学与技术系
课程设计报告
2009 ～2010 学年第 二 学期
课程
        数据结构与算法
课程设计名称
八皇后问题
学生姓名
殷伟峰
学号
0804012010
专业班级
08计科(2)
指导教师
王昆仑、张贯虹
2010  年 06 月

摘要：
八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。
而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现． 使用回溯算法最终将其问题变得一目了然，更加易懂。
关键词：  八皇后 ;  c++  ;  回溯法 


  第一部分                   
课题综述：八皇后问题
1.课题的来源及意义：
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出。
在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。
到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。
2.任务要求：
设计程序解决八皇后问题，设计要求如下：
⏹ 依次输出各种成功的放置方法；
⏹ 画出棋盘的图形界面，并在其上动态地标注行走的过程；
⏹ 程序能方便地移植到其他规格的棋盘上。
3.需求分析：
本次课程设计中，用到的主要知识有：递归法的运用，for语句的灵活运用，数据结构中树知识的灵活运用、数组及动态数组技术的掌握。
系统要求：win98以上操作系统；
语言平台：vc++6.0或以上版本；
第二部分
课题分析 ：
根据程序的设计要求，需要设计一个八皇后问题的演示程序，程序需要具备以下功能：
⏹ 能够快速查并显示八皇后的布局方式有多少种正确方法；
⏹ 能够逐个查看每种布局的结果；
⏹ 能够逐步演示棋子在棋盘上的的行走过程，直到出现正确的结果；
⏹ 能够很方便的改变皇后个数即棋盘规格。
1.目前状况中的问题：
要实现指定的功能，存在以下几个待解决的问题；
根据指定的规格，即皇后个数，来画出相应规格的棋盘；
能够在指定的位置摆放棋子和收回棋子；
制定落子的顺序和规则，避免重复和遗漏；
标记每步落子后不能落子的区域，即已有棋子的同行、同列和同一斜线上的位置。
数据结构与算法论文
2.问题分析：
程序的功能要求具有图形化界面，根据目前状况中的问题，综合考虑，在此使用MFC开发工具编程。
关于棋盘的绘制，因为棋盘的规格（n*n）是不确定的，显然不能根据规格的大小来确定棋盘的面积，所以我们首先划分出一个指定区域，用来绘制棋盘，这个正方形区域的边长大小为一个整型常量board，单位为像素，这样就能轻易的计算出每个棋子格的大小，即我们自定义的单位长度，cell=board/n；在此有衍生出另外一个问题，board不可能被所有的n整除，这样得到的cell可能会是一个无理数，在C++语言中，处理浮点型数据时不能存储无理数，所以最好的方法是让cell为一个整数，这里使用一个技巧，board = board - board % n;这就将取整后的余数去掉了，在Dialog中，board%n是很小的区域，不会引起视觉冲突；
关于棋子的摆放，在绘制完棋盘之后，我们同样也获取了每个棋子位的坐标，落子的过程其实就是一个贴图的过程，在指定坐标的位置使用绘图函数绘出棋子，同样，取出棋子也是擦去棋子的图形；
程序在算法上使用回溯算法，即从第一行起逐行放置皇后，每放置一个皇后均需要对第1，2，…，8列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，则将该行i的列
位置j保存在数组的queen[i]=j变量中，然后继续在下一行寻安全位置，若当前试探的列位置不安全，则用下一列试探；当8列位置试探完毕都未到安全位置时，就退栈回溯到上一行，修改最后一行保存的皇后位置，然后继续试探。同时根据queen[i]的值摆放和去除棋子，queen[i]=j>0是，在（i，j）位置摆棋，queen[i]<0时，清除该行的棋子；
关于“死区”的标记。落子规则为逐行落子，那么就不存在两个棋子同行的情况，我们只需要考虑是否同列和是否在同一斜线；观察落子点的坐标，同一列的任意两个位置坐标（i1,j1）、（i2,j2），有j1 =j2 ，可以设置布尔型数组mk[n]来存储标记信息，当mk[j]=true时j列为“死区”；在棋盘中的斜线，有左上右下和右上左下两种，各有2n-1条，其中在同一左上右下斜线上的两点（i1,j1）、（i2,j2），有这样的特征，i1-i2=j1-j2，即i1+j1=i2+j2，可以设置标记数组lk[2n-1]，lk[i+j]=true表示该点所在坐上右下斜线为“死区”；同理，右上左下的斜线上的两点坐标有关系：i1-j1=i2-j2，可以设置数组rk[2n-1]来标记，当lk[n+i-j]=true时，表示当前点所在右上左下斜线为“死区”。