学步园

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;
}