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

南京理工大学紫金学院VC+课程设计报告课 程：VC+课程设计系 别：计算机系班 级：学 号：姓 名：选题名称：八皇后问题选题难易别：B级起止时间：2011.11.212011.12.22指导教师：朱 俊2011年 12 月1 程序功能介绍答：这个程序是用于解决八皇后问题的。八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。我的程序进入时会让使用者选择程序的功能，选【1】将会通过使用者自己手动输入第一个皇后的坐标后获得答案；选【2】将会让程序自动运算出固定每一个皇后后所有的排列结果。2 课程设计要求答：（1）增加函数，完成每输入一组解，暂停屏幕，显示“按任意键继续！”。（2）完善程序，编程计算八皇后问题共有集中排列方案。（3）增加输入，显示在第一个皇后确定后，共有几组排列。（4）将每组解的期盼横向排列输出在屏幕上，将五个棋盘并排排列，即一次8行同时输出5个棋盘，同样完成一组解后屏幕暂停，按任意键继续。（5）求出在什么位置固定一个皇后后，解的数量最多，在什么位置固定皇后后，解的数量最少，最多的解是多少，最少的解是多少，并将最多，最少解的皇后位置及所有的解求出，同样5个一组显示。3 对课程题目的分析与注释答：众所周知的八皇后问题是一个非常古老的问题，问题要求在一个的棋盘上放上个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子。因此，本课程设计的目的也是通过用C+语言平台在一个的棋盘上放上个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现。使用递归方法最终将其问题变得一目了然，更加易懂。首先要用到类，将程序合理化：我编辑了一个盘棋8*8的类：class Board，还有个回溯法的类：class Stack，关键的类好了，然后编辑好类的成员，然后编辑主函数利用好这些类的成员，让其运算出结果。4 程序设计和说明（说明算法思想、设计思路，给出重要的、关键的代码）答：算法思想：关键代码：class Stackprivate:SType dataSSize;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 dataTop=d; Top+; return true; bool Stack:Pop(SType&d) /将整数d出栈if(!Top) /栈中没有数据，操作不成功 return false; else Top-; /先动栈顶，再出数据 d=dataTop; return true; bool Stack:StackTop(SType&d) /复制栈顶的数据到dif(!Top) return false; else d=dataTop-1; return true; enum Statesused,free;class Board /一盘棋8*8private: States Rows8,DiagsLR15,DiagsRL15; /行，左右斜线public:char board88;Board();Board()bool isAttacked(int,int);void Print();void PlaceQueen(int,int);void RemoveQueen(int,int);Board:Board() /构造函数，初始化为空for(int i=0;i8;i+)Rowsi=free; for(int j=0;j8;j+) boardij=.;for(int k=0;k15;k+) DiagsLRk=DiagsRLk=free;void Board:Print() /显示一组排列结果 coutendl;for(int i=0;i8;i+) for(int j=0;j8;j+) coutboardij ; coutendl;bool Board:isAttacked(int row,int col) /判断是否冲突，是返回TRUE，否则返回FALSE int diagLR=col-row+7; /该皇后的右倾斜线的所有位置 int diagRL=row+col; /该皇后的左倾斜线的所有位置 if(Rowsrow=used | DiagsLRdiagLR=used | DiagsRLdiagRL=used) return true; return false;void Board:PlaceQueen(int row,int col) /放皇后 int diagLR=col-row+7; /右倾斜线 int diagRL=row+col; /左倾斜线 boardrowcol=Q; Rowsrow=used; /该行不能再放置 DiagsLRdiagLR=used; /左倾斜线上不能再放置 DiagsRLdiagRL=used; /右倾斜线上不能再放置void Board:RemoveQueen(int row,int col) /移去皇后 int diagLR=col-row+7; int diagRL=row+col; boardrowcol=.; Rowsrow=free; DiagsLRdiagLR=free; DiagsRLdiagRL=free;int comp(char a88,char b88) /定义比较函数for(int i=0;i8;i+) for(int j=0;j8;j+) if (aij!=bij) return 1; return 0;/*主函数开始*int main(void)do while(8) kaishi: char xz; couttt* 请您选择程序的功能 *nnn; cout 如果您想通过自己输入第一个皇后的坐标获得答案，请选择1.n; cout 如果您想让程序自动运算出所有的排列结果，请选择2.nn; coutxz; switch(xz)case 1: do char PrintBoard10088; Stack rowStack; int qRow, qCol, col, row, attacked, exitLoop,m=0; Board myBoard; cout请输入第一个皇后的坐标Row(行)和Col(列)nRow: qRow; coutCol: qCol; /第一个皇后位置 myBoard.PlaceQueen(qRow,qCol); if (qCol=0) col=1; else col=0; row=0; do while(row8) /超界 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;i8;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-p5) m1=n; for(i=0;i8;i+) for(p=s;pm1;p+) for(j=0;j8;j+) coutPrintBoardpij ; cout|; coutendl; s=p;/一次8行同时输出5个棋盘： p=p-1; m1=(m1+5)n?(m1+5):n; coutnnflush; if(m1!=n)m1=m1+5; while(m1!=n); cout当皇后坐标为(qRow,qCol)时的解的个数为：mttnnn; cout 选择1继续程序.n- 选择2结束程序.nnn; char xz2; cinxz2; 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 zzz100088; int compare88; char news10088; int ii,jj,kk,qq; int nn; for(qRow=0;qRow8;qRow+) for(qCol=0;qCol8;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(row8) /超界 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;i8;i+) for(j=0;j=0); /回到0列 compareqRowqCol=cmp;/*cout(qRow,qCol):cmptn;*/*以下是对坐标和解的数目的输出* int n=m;int m1=5;int p=0;int s=0;int i,j; do if (n-p5) m1=n; for(i=0;i8;i+) for(p=s;pm1;p+) for(j=0;j8;j+) coutzzzpij ; cout|; coutendl; s=p;/一次8行同时输出5个棋盘： p=p-1; m1=(m1+5)n?(m1+5):n; coutnnflush; if(m1!=n) m1=m1+5; while(m1n); cout程序自动求出了所有的答案的个数为:m/8种。n程序自动排除重复的答案后的个数为：92种。n; /* nn=sizeof(zzz)/(sizeof(char)*64); for(ii=0;ii100;ii+) for(qq=0;qqnn;qq+) if(comp(newsii,zzzqq) for(jj=0;jj8;jj+) for(kk=0;kk8;kk+) newsiijjkk=zzzqqjjkk; /*接下来是进行比较大小* min=max=compare00; rmax=rmin=cmax=cmin=0; /初始化过程记录大小值的行列号 for (qRow=0;qRow8;qRow+) for(qCol=0;qColmax)max=compareqRowqCol;rmax=qRow;cmax=qCol; if(compareqRowqColmin) min=compareqRowqCol;rmin=qRow;cmin=qCol; coutnn; cout在(rmax,cmax)固定一个皇后的数目最多，个数为:maxn; cout在(rmin,cmin)固定一个皇后的数目最少，个数为:minn; coutnnn; cout 选择1继续程序.n- 选择2结束程序.nnn; char xz2; cinxz2; 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. 对课程设计的感想和心得体会答：通过了这几个星期的程序设计，我从中得到了许多的经验以及软件设计的一些新的思路；从这个八皇后问题设计以及分析中，本人从中理解到了数据结构对于计算机软件设计的重要性，它的使用，可以改变一个