采用試探回溯策略外恕，通過棧記錄查找結(jié)果取试，實(shí)現(xiàn)八皇后問題求解。

//
// Created by krislyy on 2018/11/21.
//
// 國際象棋中皇后的勢力范圍覆蓋其所在的水平線荣倾、
// 垂直線以及兩條對(duì)角線∠狄耍現(xiàn)考查如下問題：在n*n的
// 棋盤上放置n個(gè)皇后，如何使他們不互相攻擊--此時(shí)
// 稱他們構(gòu)成一個(gè)可行的棋局霎冯。對(duì)于任何整數(shù)n>=4铃拇，這就
// 是n皇后問題。
//
// N皇后問題肃晚，可以采用試探回溯策略锚贱，采用棧記錄查找的結(jié)果
//

#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 {
            //判斷是否在同一行或者列或者正反對(duì)角線
            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); //從原點(diǎn)位置出發(fā)
        do {
            if (solu.size() >= N || q.y >= N) {
                q = solu.top(); solu.pop(); //若已經(jīng)出界，則回溯一行并直接試探下一行
                q.y++;
            } else {
                while(q.y < N && findQueen(solu, q) >= 0){
                    q.y++; nCheck++; //通過與已有皇后的對(duì)比关串，嘗試找到可擺放下一個(gè)皇后的列
                }
                if (q.y < N){
                    solu.push(q); //找到可擺放列拧廊，存入
                    if (solu.size() >= N) {
                        nSolu++; //若部分解已成為全局解，則通過全局變量計(jì)數(shù)
                        break; //此處如果不退出晋修，則會(huì)探測所有可能得解
                    }
                    q.x++;
                    q.y = 0; //轉(zhuǎn)入下一行吧碾，從第0列開始試探下一個(gè)皇后
                }
            }
        } while(0 < q.x || q.y < N); //所有分支都已經(jīng)窮舉或者剪枝后，算法結(jié)束
        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;
}