《计算机C++课程设计八皇后问题》由会员分享，可在线阅读，更多相关《计算机C++课程设计八皇后问题（13页珍藏版）》请在金锄头文库上搜索。
1、南京理工大学紫金学院VC+课程设计报告课 程：VC+课程设计系 别：计算机系班 级：学 号：姓 名：选题名称：八皇后问题选题难易别：B级起止时间：2011.11.212011.12.22指导教师：朱 俊2011年 12 月1 程序功能介绍答：这个程序是用于解决八皇后问题的。八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。我的程序进入时会让使用者选择程序的功能，选【1】将会通过使用者自己手动输入第一个皇后的坐标后获得答案；选【2】将会让程序自动运算出固定每一个皇后后所有的排列结果。
2、2 课程设计要求答：（1）增加函数，完成每输入一组解，暂停屏幕，显示“按任意键继续！”。（2）完善程序，编程计算八皇后问题共有集中排列方案。（3）增加输入，显示在第一个皇后确定后，共有几组排列。（4）将每组解的期盼横向排列输出在屏幕上，将五个棋盘并排排列，即一次8行同时输出5个棋盘，同样完成一组解后屏幕暂停，按任意键继续。（5）求出在什么位置固定一个皇后后，解的数量最多，在什么位置固定皇后后，解的数量最少，最多的解是多少，最少的解是多少，并将最多，最少解的皇后位置及所有的解求出，同样5个一组显示。3 对课程题目的分析与注释答：众所周知的八皇后问题是一个非常古老的问题，问题要求在一个的棋盘上放上
3、个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子。因此，本课程设计的目的也是通过用C+语言平台在一个的棋盘上放上个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现。使用递归方法最终将其问题变得一目了然，更加易懂。首先要用到类，将程序合理化：我编辑了一个盘棋8*8的类：class Board，还有个回溯法的类：class Stack，关键的类好了，然后编辑好类的成员，然后编辑主函数利用好这些类的成员，让其运算出结果。4 程序设计和说明（说明算法思想、
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 fa
5、lse; 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: Stat
6、es 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:P
7、rint() /显示一组排列结果 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; retu
8、rn 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; boar
9、drowcol=.; 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 如果您想让程序自动运算出所有
10、的排列结果，请选择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) /超界 e
11、xitLoop=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;j8;j+) PrintBoard
