/*
	Author:	James Pate Williams, Jr. (c) 2000

	Backjumping algorithm applied to the N-Queens CSP.
	Algorithm from _Foundations of Constraint Satisfaction_
	by E. P. K. Tsang Chapter 5 page 138 - 140.
*/

#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] = '\0';
		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;
}