C++实现八皇后问题的方法
本文实例展示了C++实现八皇后问题的方法，是数据结构与算法中非常经典的一个算法。分享给大家供大家参考之用。具体方法如下：
一般在八皇后问题中，我们要求解的是一个8*8的国际象棋棋盘中，放下8个皇后且互相不能攻击的排列总数。皇后的攻击范围为整行，整列，以及其斜对角线。
由于皇后的攻击范围特性，注定我们每行只能放下一个皇后，于是我们要做的只是逐行放下皇后。八皇后问题是回溯法的典型问题。这里我们用的方法很简单：
从第一行开始逐个检索安全位置摆放皇后，一旦有安全位置则考虑下一行的安全位置。如果发现某行没有安全位置，则返回上一行继续检索安全位置;如果发现在最后一行找到了安全位置则输出整个棋盘。
原理很简单，整个程序中表现了这个思想的函数是voidSolve()
下面是实现的代码：
//八皇后问题的实现
#include<iostream>
#include<string>
usingnamespacestd;
//QueenChess类声明
classQueenChess
{
public:
QueenChess();//构造函数
voidSolve();//求解八皇后问题，并给出放置成功的棋盘总个数
private:
stringchessState[8];//用于存放棋盘状态
intsolves;//八个皇后放置成功的棋盘解的总个数
boolSafeJudge(introw,intcol)const;//判断位置(row,col)是否安全
voidPlaceQueen(introw);//在第row行放置一个皇后
voidDrawChess()const;//打印八个皇后放置成功的棋盘
};
//构造函数，将棋盘初始化
QueenChess::QueenChess()
{
solves=0;
inti=0,j=0;
for(;i<8;++i)
chessState[i]="--------";
}
//求解八皇后问题，并给出放置成功的棋盘总个数
voidQueenChess::Solve()
{
//从第0行开始放置皇后
PlaceQueen(0);
cout<<"/n八皇后问题总共的解的个数是："<<solves<<endl;
}
//在第row行的各列放置皇后
voidQueenChess::PlaceQueen(introw)
{
//穷尽第row行的所有列
for(intcol=0;col<8;col++)
{
if(SafeJudge(row,col))
{
//位置(row,col)安全，则放一皇后
chessState[row][col]='Q';
//若还没有放到第八行，则尝试下一行
if(row<7)
PlaceQueen(row+1);
//已经放置了八个皇后，打印出成功的棋盘，并将解数加1
else
{
solves++;
DrawChess();
}
}//endif
//不安全，将该处的皇后拿走，尝试下一列位置
chessState[row]="--------";
}
}
//判断是否(row,col)是安全位置
boolQueenChess::SafeJudge(introw,intcol)const
{
intqRow,qCol;
//检查前面各行，看与前面的皇后是否发生攻击
for(qRow=0;qRow<row;qRow++)
{
stringrowState=chessState[qRow];
//寻找第qRow行放置皇后的列数
qCol=rowState.find("Q");
//如果两个皇后在同一行、同一列或两条对角线上，则说明该位置不安全
if(qRow==row||qCol==col||(qCol-qRow)==(col-row)||(qCol+qRow)==(col+row))
returnfalse;
}//endif
returntrue;
}
//打印成功的棋盘
voidQueenChess::DrawChess()const
{
inti,j;
cout<<"/n八皇后问题的第"<<solves<<"个解为："<<endl;
cout<<"01234567"<<endl;
for(i=0;i<8;++i)
{
cout<<i<<"";
for(j=0;j<8;++j)
cout<<chessState[i][j]<<"";
cout<<endl;
}//endfor
//每打印一个成功的八皇后棋盘，暂停一下
//system("pause");
}
//main函数进行测试
intmain()
{
QueenChesschess;
chess.Solve();
system("pause");
return0;
}
希望本文所述实例对大家C++算法设计有所帮助。