#include <iostream>
#include <vector>
#include <stdexcept>
#include <string>
#include <limits>
#include <thread>
#include <future>

using namespace std;

//External bitbanging to keep the solve()-function mostly as it is.
typedef uint64_t inttype;  //yes, works "only" until n=32 but gcc has __int128. There is  uint265_t from immintrin.h and uint512_t from boost...
class BoolArr {
    inttype arr=0;
    public:
    inline void set(int n) {
        arr|=1<<n;
    }
    inline void unset(int n) {
        arr&=~(1<<n);
    }
    inline int get(int n){
        return (arr>>n)&1;
    }
};
int solve(const int row, const int n, BoolArr lockCol, BoolArr lockLtrb, BoolArr lockRtlb) {
    int count=0;
    if (row < n) {
        for (int dx = 0; dx < n; dx++) {
            if (lockCol.get(dx) | lockLtrb.get(dx - row + n - 1) | lockRtlb.get(dx + row)) {
                continue;
            }
            lockCol.set(dx);
            lockLtrb.set(dx - row + n - 1);
            lockRtlb.set(dx + row);
            count+=solve(row + 1, n, lockCol, lockLtrb, lockRtlb);
            lockCol.unset(dx);
            lockLtrb.unset(dx - row + n - 1);
            lockRtlb.unset(dx + row);
        }
        return count;
    } else {
        return 1;
    }
}
//parallel function for the first loop
int solve_p(const int row, const int n, BoolArr lockCol, BoolArr lockLtrb, BoolArr lockRtlb) {
    std::future<int> countn[n];
    if (row < n) {
        for (int dx = 0; dx < n; dx++) {
            if (lockCol.get(dx) | lockLtrb.get(dx - row + n - 1) | lockRtlb.get(dx + row)) {
                continue;
            }
            lockCol.set(dx);
            lockLtrb.set(dx - row + n - 1);
            lockRtlb.set(dx + row);
            countn[dx]=std::async(launch::async|launch::deferred,&solve,row + 1, n, lockCol, lockLtrb, lockRtlb);
            lockCol.unset(dx);
            lockLtrb.unset(dx - row + n - 1);
            lockRtlb.unset(dx + row);
        }
        int count=0;
        for (int dx = 0; dx < n; dx++)
        {
            //if(countn[dx].valid())
            count+=countn[dx].get();
        }
        return count;
    } else {
        return 1;
    }
}

int main(int argc, char* argv[]) {
    int n = 10;
    if (argc != 2) {
        cout << "Usage: NQueens <board_size>" << endl;
        return 1;
    }

    try {
        n = stoi(argv[1]);
    } catch (invalid_argument&) {
        cout << "Invalid input! Board size must be a positive integer!" << endl;
        return 1;
    } catch (out_of_range&) {
        cout << "Invalid input! Board size is out of range!" << endl;
        return 1;
    }

    if (n <= 0||n>sizeof(inttype)*4) {
        cout << "Invalid input! Board size must be a positive integer!" << endl;
        return 1;
    }

    cout << "Solving: n=" << n << endl;

    BoolArr lockCol;
    BoolArr lockLtrb;
    BoolArr lockRtlb;

    int count = solve_p(0, n, lockCol, lockLtrb, lockRtlb);

    cout << "Result:  " << count << endl;
    return 0;
}