复制代码#include <iostream>
#include <stack>
using namespace std;
const int MAXSIZE = 8;//棋盘大小
int chess[MAXSIZE][MAXSIZE]={0};//棋盘
/* 定义栈结点，表示一个皇后的位置*/
struct Node
{
int row; /* 行*/
int col; /* 列*/
bool isMarked; /* 是否标记*/
};
/* 进行皇后问题处理
* 返回找到的答案个数
*/
int Solve()
{
//定义解答树堆栈
stack<Node> stack;
//互斥标志，表示同一列及对角线上是否有皇后
int col[MAXSIZE] = {0},
md[2 * MAXSIZE - 1] = {0},
sd[2 * MAXSIZE - 1] = {0};
int str, stc, i,j;
// 解决方案个数
int scount = 0;
Node topNode;
//初始化栈
for(i = 0; i <MAXSIZE; i++)
{
topNode.row = 0;
topNode.col = MAXSIZE - 1 - i;
topNode.isMarked = false;
stack.push(topNode);
}
//以行为单位开始回溯
while(!stack.empty())
{
topNode = stack.top();//栈顶元素
str = topNode.row;//行
stc = topNode.col;//列
if(topNode.isMarked==false)
{// 如果栈顶元素的位置并没有确立
if(col[stc] || md[str - stc + MAXSIZE - 1] || sd[str + stc])
{//如果同一列或同一对角线上已有皇后，则退回*/
stack.pop();
}
else
{
//占据这个位置，设置列、对角线上的互斥标志
col[stc] = 1;
md[str - stc + MAXSIZE - 1] = 1;
sd[str + stc] = 1;
//标记栈顶元素的isMarked 值
topNode.isMarked = true;
stack.pop();
stack.push(topNode);
chess[str][stc] = 1;//标记棋盘对应位置
if(str == MAXSIZE - 1)
{// 如果此时已经到达最后一行,则表示此种布局方法是成功的,输出相关信息
cout<<"A solution is:"<<endl;
for(i=0;i<MAXSIZE;++i)
{
for(j=0;j<MAXSIZE;++j)
{
if(chess[i][j]==1)
{
cout<<"("<<i+1<<","<<j+1<<")";
}
}
}
cout<<endl;
scount++; // 解决方案数增
}
else
{// 如果此时没有到达最后一行,则继续进栈并初始化
for(i = 0; i < MAXSIZE; i++)
{
topNode.row = str + 1;
topNode.col = MAXSIZE - 1 - i;
topNode.isMarked = false;
stack.push(topNode);
}
}
}
}
else
{//如果栈顶元素位置已确立,则栈顶元素出栈，初始化互斥标志,准备继续寻找其它的方法
col[stc] = 0;
md[str - stc +MAXSIZE - 1] = 0;
sd[str + stc] = 0;
chess[str][stc] = 0;
stack.pop();
}
}
return scount;
}
int main()
{
int scount = 0;
scount = Solve();
cout<<scount<<"sulotions found."<<endl;
system("pause");
return 0;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/11/01/1324213.html，如需转载请自行联系原作者
