N皇后问题代码

/*.h*/
#ifndef _NQUEEN_H
#define _NQUEEN_H
#include<iostream> 
#include<vector> 
#include<string> 
using namespace std;


class Queen{
public:
    Queen();
    Queen(int num);
    //~Queen();
    void show(const vector<vector<string>>&input);
    void solve();
private:
    bool is_valid(const int row, const int col);
    //void init(const int num);
    void TraceBack(const int curRow);
private:
    int m_num;
    vector<int>pos;
    vector<vector<string>>res;
};

#endif
/*cpp*/
#include"NQueen.h"

Queen::Queen(int num) :m_num(num), pos(4, -1){ }
void Queen::TraceBack(int curRow){
    //cout << m_num << endl;
    if (curRow == m_num)
    {
        vector<string>out(m_num, string(m_num, '*'));
        for (int i = 0; i < m_num; i++){
            out[i][pos[i]] = 'Q';
        }
        res.push_back(out);
    }
    else{
        for (int col = 0; col < m_num; col++){
            if (is_valid(curRow, col)){
                pos[curRow] = col;
                TraceBack(curRow + 1);
                pos[curRow] = -1;
            }
        }
    }
}
bool Queen::is_valid(int row, int col){
    for (int i = 0; i < row; i++){
        if (pos[i] == col || abs(i - row) == abs(pos[i] - col))
            return false;
    }
    return true;
}
void Queen::solve(){
    TraceBack(0);
    //cout << res.size() << endl;
    show(res);
}
void Queen::show(const vector<vector<string>>&input){
    //cout << input.size() << endl;
    //cout << input[0].size() << endl;
    for (int i = 0; i < input.size(); i++){
        for (int j = 0; j < input[0].size(); j++){
            cout << input[i][j] << endl;
            //if ((j + 1) % input.size() == 0)cout << input[i][j]<<e
        }
        cout << endl;
    }
}
原文地址:https://www.cnblogs.com/inception6-lxc/p/8820803.html