八皇后问题

采用试探回溯策略，通过栈记录查找结果，实现八皇后问题求解。

//
// Created by krislyy on 2018/11/21.
//
// 国际象棋中皇后的势力范围覆盖其所在的水平线、
// 垂直线以及两条对角线。现考查如下问题：在n*n的
// 棋盘上放置n个皇后，如何使他们不互相攻击--此时
// 称他们构成一个可行的棋局。对于任何整数n>=4，这就
// 是n皇后问题。
//
// N皇后问题，可以采用试探回溯策略，采用栈记录查找的结果
//

#ifndef ALGORITHM_EIGHTQUEEN_H
#define ALGORITHM_EIGHTQUEEN_H

#include <stack>

namespace Algorithm {
    struct Queen{
        int x, y;
        Queen(int xX, int yY): x(xX), y(yY) {}
        bool operator == (Queen const& q) const {
            //判断是否在同一行或者列或者正反对角线
            return (x == q.x) || (y == q.y) ||(x+y == q.x+q.y) || (x-y == q.x-q.y);
        }
        bool operator != (Queen const& q) const {
            return !(*this == q);
        }
    };

    int nCheck = 0, nSolu = 0;

    int findQueen(std::stack<Queen> queens, Queen q) {
        while (!queens.empty()) {
            Queen queen = queens.top();
            if (queen == q)
                return 1;
            queens.pop();
        }
        return -1;
    }

    std::stack<Queen> placeQueens(int N) {
        std::stack<Queen> solu; //存放已解得Queen
        Queen q(0,0); //从原点位置出发
        do {
            if (solu.size() >= N || q.y >= N) {
                q = solu.top(); solu.pop(); //若已经出界，则回溯一行并直接试探下一行
                q.y++;
            } else {
                while(q.y < N && findQueen(solu, q) >= 0){
                    q.y++; nCheck++; //通过与已有皇后的对比，尝试找到可摆放下一个皇后的列
                }
                if (q.y < N){
                    solu.push(q); //找到可摆放列，存入
                    if (solu.size() >= N) {
                        nSolu++; //若部分解已成为全局解，则通过全局变量计数
                        break; //此处如果不退出，则会探测所有可能得解
                    }
                    q.x++;
                    q.y = 0; //转入下一行，从第0列开始试探下一个皇后
                }
            }
        } while(0 < q.x || q.y < N); //所有分支都已经穷举或者剪枝后，算法结束
        return solu;
    }
}

#endif //ALGORITHM_EIGHTQUEEN_H

测试代码

///////////////////////////////八皇后问题////////////////////////////////////
void main() {   
    std::stack<Queen> Queens;
    Queens = placeQueens(8);
    while(!Queens.empty()) {
        Queen q = Queens.top();
        cout << "[" << q.x << "," << q.y << "] ";
        Queens.pop();
    }
    cout << endl;
}