#include <iomanip.h>
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <vector>
using namespace std;

int constraintsViolated(vector<int> &Q) {
    int a, b, c = 0, i, j, n;

    n = Q.size();
    for (i = 0; i < n; i++) {
        a = Q[i];
        for (j = 0; j < n; j++) {
            b = Q[j];
            if (i != j && a != - 1 && b != - 1) {
                if (a == b) c++;
                if (i - j == a - b || i - j == b - a) c++;
            }
        }
    }
    return c;
}

const int MaxQueens = 100000;
int LevelOf[MaxQueens];
int backtrackTo[MaxQueens] = {- 1};

int AnalyseBTLevel(int L, int x, vector<int> compoundLabel, vector<int> Dx) {
    bool NoConflict;
    int Level = - 1, Temp, a, b, i, j;

    for (i = 0; i < Dx.size(); i++) {
        a = Dx[i];
        Temp = L - 1;
        NoConflict = true;
        for (j = 0; j < compoundLabel.size(); j++) {
            if (compoundLabel[j] != - 1) {
                b = compoundLabel[j];
                if (i != j && a != - 1 && b != - 1) {
                    if (a == b) NoConflict = false;
                    if (i - j == a - b || i - j == b - a) NoConflict = false;
                    if (!NoConflict)
                        Temp = Temp < LevelOf[j] ? Temp : LevelOf[j];
                }
            }
        }
        if (NoConflict) return LevelOf[x] - 1;
        Level = (Level > Temp) ? Level : Temp;
    }
    return Level;
}

int Backjump(int L, vector<int> unlabelled, vector<int> compoundLabel,
    vector<int> &solution, vector<int> *D) {
    int Level = L, Result, i, j, v, x;

    if (unlabelled.empty()) {
        for (i = 0; i < compoundLabel.size(); i++)
            solution[i] = compoundLabel[i];
        return true;
    }
    // pick a random variable from unlabelled array
    i = rand() % unlabelled.size();
    x = unlabelled[i];
    vector<int> TDx(D[x].size());
    copy(D[x].begin(), D[x].end(), TDx.begin());
    LevelOf[x] = L;
    do {
        // pick a random value from domain of x
        j = rand() % TDx.size();
        v = TDx[j];
        vector<int>::iterator vIterator = find(TDx.begin(), TDx.end(), v);
        TDx.erase(vIterator);
        compoundLabel[x] = v;
        if (constraintsViolated(compoundLabel) == 0) {
            vIterator = find(unlabelled.begin(), unlabelled.end(), x);
            unlabelled.erase(vIterator);
            Result = Backjump(L + 1, unlabelled, compoundLabel, solution, D);
            if (Result != backtrackTo[Level]) return Result;
            unlabelled.push_back(x);
        }
        else
            compoundLabel[x] = - 1;
    } while (!TDx.empty() && (Result != backtrackTo[Level] || Level >= L));
    if (Result == backtrackTo[Level] && Level < L) return backtrackTo[Level];
    Level = AnalyseBTLevel(L, x, compoundLabel, D[x]);
    backtrackTo[Level] = Level;
    return Level;
}

void printSolution(vector<int> &solution) {
    char hyphen[256];
    int column, i, i4, n = solution.size(), row;

    if (n <= 10) {
        for (i = 0; i < n; i++) {
            i4 = i * 4;
            hyphen[i4 + 0] = '-';
            hyphen[i4 + 1] = '-';
            hyphen[i4 + 2] = '-';
            hyphen[i4 + 3] = '-';
        }
        i4 = i * 4;
        hyphen[i4 + 0] = '-';
        hyphen[i4 + 1] = 'n';
        hyphen[i4 + 2] = '';
        for (row = 0; row < n; row++) {
            column = solution[row];
            cout << hyphen;
            for (i = 0; i < column; i++)
                cout << "|   ";
            cout << "| Q ";
            for (i = column + 1; i < n; i++)
                cout << "|   ";
            cout << '|' << endl;
        }
        cout << hyphen;
    }
    else
        for (row = 0; row < n; row++)
            cout << row << ' ' << solution[row] << endl;
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        cout << "usage: " << argv[0] << " numberOfQueens" << endl;
        exit(1);
    }
    int i, j, n = atoi(argv[1]);
    if (n > MaxQueens) {
        cout << "error: too many queens maximum = " << MaxQueens << endl;
        exit(1);
    }
    vector<int> compoundLabel(n, - 1), solution(n, - 1), unlabelled(n);
    vector<int> *D = new vector<int>[n];
    if (D == NULL) {
        cout << "error: can't allocate memory in main" << endl;
        exit(1);
    }
    for (i = 0; i < n; i++) {
        unlabelled[i] = i;
        for (j = 0; j < n; j++)
            D[i].push_back(j);
    }
    for (i = 0; i < n; i++)
    unlabelled[i] = i;
    srand(time(NULL));
    Backjump(1, unlabelled, compoundLabel, solution, D);
    printSolution(solution);
    return 0;
}