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

C课程设计八皇后问题

26
2020年4月19日
文档仅供参考
南京理工大学紫金学院VC++课程设计报告

课 程：
VC++课程设计
系 别：
计算机系
班 级：

学 号：

姓 名：

选题名称：
八皇后问题
选题难易别：
B级
起止时间：
.11.21~ .12.22
指导教师：
朱 俊

12 月

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&d) //将整数d出栈
{if(!Top) //栈中没有数据，操作不成功
return false;
else
{Top--; //先动栈顶，再出数据
d=data[Top];
return true;
}
}
bool Stack::StackTop(SType&d) //复制栈顶的数据到d
{if(!Top)
return false;
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<<"请输入您选择的数字：";
cin>>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: "<<flush;
cin>>qRow;
cout<<"Col: "<<flush;
cin>>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<8;j++)
PrintBoard[p][i][j]=myBoard.board[i][j];
p++;
}
m++;
row=8;
}
if (row==8)
{
rowStack.Pop(row); //前一列皇后所在行号出栈
col--; //到前一列
if (col==qCol)
col--;
myBoard.RemoveQueen(row,col); //移去皇后
row++; //找下一个位置
}
} while(col>=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<<"请选择是否结束程序？\n---> 选择[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<8;j++)
zzz[p][i][j]=myBoard.board[i][j];
}
p++;
m++;
cmp++;
row=8;
}
if (row==8)
{
rowStack.Pop(row);
col--; //到前一列
if (col==qCol)
col--;
myBoard.RemoveQueen(row,col); //移去皇后
row++; //找下一个位置
}
} while(col>=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;qCol<8;qCol++)
{
if(compare[qRow][qCol]>max)
{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<<"请选择是否结束程序？\n---> 选择[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. 对课程设计的感想和心得体会

答：经过了这几个星期的程序设计，我从中得到了许多的经验以及软件设计的一些新的思路；从这个八皇后问题设计以及分析中，本人从中理解到了数据结构对于计算机软件设计的重要性，它的使用，能够改变一个软件的运行周期，也能够将软件的思路从繁化简，而且都能够经过数据结构的相关引导，将本身以前编程思想进行扩充，发展；这也是在这次课程设计中我所掌握得到的。但由于我的基本知识还不是那么扎实，也缺乏对软件设计的经验，在这过程中也出现了一些问题，后来我对数据结构的第六章进行了比较深入的研读，才发现了数据结构树的实际运用的空间是相当的大，而且，经过了重温树的回溯，以及二叉树的遍历，最终将程序进行了一次较大的改造。而且经过思考，再将以前的数组知识加以运用才最终解决了这个问题，整个程序的算法的可看性也有了相当的改进。课程设计随着时间的推移，也即将结束了，但这个学期数据结构的学习还是具有相当大的意义，它从一个程度上改变了我们的编程思想，如何将一个程序快速而又准备的进行编写，进行编译，都成为了我们思考的重点，也经过这一个学期的学习，我们将数据结构的思想带入到了我们以后的编程学习中去。在这个阶段，我也明白了，好的思想，不能提留于字面上的认知，还需要的是平时多练多写一些相关的程序，而且经过修改，加入新的算法去尝试改变自己的一些编程思想。保持更新算法的速度，这才是关键。课程设计已经接近尾声了，但它给我的不只是程序设计上的满足，更重要的是对自己编程思想的一次更新，以及对算法的一个全新的认识！

10.分工情况（选做）

答：无。

致 谢
课程设计终于告一段落了，一周的努力过后，也算是颇有收获，很多以前不清楚、不熟悉的内容都在这一周的努力中得到了锻炼，感谢老师给予的大量帮助及指导，感谢同学们的帮助！感谢帮助过我的每一个人！谢谢！！！