/*
    1.初始化k = 0,初始化解向量x[n] = {-1};
    2.重复执行下述操作,拜访皇后k
        2.1 把皇后k摆放在下一列的位置,即x[k]++;
        2.2 如果皇后k摆放在x[k]位置发生冲突,x[k]++试探下一列,直到不冲突或x[k]出界
        2.3 如果x[k]没出界且所有的皇后都摆放完毕,则输出一个解
        2.4 如果x[k]没出界但尚有皇后没摆放,则k++,转2.1摆放下一个皇后
        2.5 如果x[k]出界,则回溯,x[k] = -1, k--, 转2.1重现摆放皇后k
*/
#include <iostream>
#include <cstring>

using namespace std;

class Queen
{
public:
    Queen(int n);
    ~Queen(); 
    int SetQueen(); // 填写n皇后
    void PrintQueen(); // 打印皇后的位置
private:
    int Place(int k); // 判断皇后k是否冲突
    int *x;
    int num; // 皇后的个数
};

Queen :: Queen(int n)
{
    x = new int[n];
    memset(x, -1, n); // -1表示皇后未放置 
    num = n; 
}

Queen :: ~Queen()
{
    delete [] x;
}

int Queen :: SetQueen()
{
    int k = 0, count = 0;  // count 存储解的个数
    while (k >= 0) // 摆放皇后k,注意0<=k<n
    {
        x[k]++; //在下一列摆放皇后k
        while (x[k] < num && Place(k) == 1) x[k]++; // 发生冲突时候,皇后k试探下一列
        if (x[k] < num && k == num - 1) // 得到一个解 输出
        {
            cout << "第" << ++count << "个解是: ";
            PrintQueen();
        }
        else if (x[k] < num && k < num - 1) k += 1;// 尚有皇后未摆放, 准备摆放下一个皇后
        else x[k --] = -1; // 重置x[k], 回溯, 重新摆放皇后k
    }
    return count;
}

// 判断皇后k是否冲突
int Queen :: Place(int k) 
{
    for (int i = 0; i < k; i++)
        if (x[i] == x[k] || abs(i - k) == abs(x[i] - x[k])) // 违法约束 条件 该约束条件推导得来 不同行 不同列 不同斜
            return 1; // 冲突返回1
        return 0; // 不冲突 返回0
}

void Queen :: PrintQueen() // 打印n皇后的一个解
{
    for (int i = 0; i < num; i++)
        cout << x[i] + 1 << "\t"; // 数组下标0开始,打印的列号从1开始
    cout << endl;
}


int main()
{
    int n;
    cout << "请输入皇后的个数(n>=4) :" << endl;;
    cin >> n;

    Queen Q{n};

    int res = Q.SetQueen();

    cout << "所有解的个数为: " << res << endl;

    return 0;
}