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

南京理工大学紫金学院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.分工情况（选做）

答：无。

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