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

	Backmarking algorithm applied to the N-Queens CSP.
	Algorithm from _Foundations of Constraint Satisfaction_
	by E. P. K. Tsang section 5.4.3 page 147.
*/

#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;
}

bool satisfies(int x, int v, int y, int vp) {
	if (x == y) return false;
	if (v == vp) return false;
	if (x - y == v - vp || x - y == vp - v) return false;
	return true;
}

bool Compatible(int x, int v, int *LowUnit, int *Ordering, int **Mark,
				vector<int> compoundLabel) {
	bool compat = true;
	int vp, y = LowUnit[x];
	
	while (Ordering[y] < Ordering[x] && compat) {
		if (compoundLabel[y] != - 1) {
			vp = compoundLabel[y];
			if (satisfies(x, v, y, vp))
				y = Ordering[y] + 1;
			else
				compat = false;
		}
	}
	Mark[x][v] = Ordering[y];
	return compat;
}

bool BM1(int Level, int *LowUnit, int *Ordering, int **Mark,
	vector<int> unlabelled, vector<int> compoundLabel, vector<int> &solution) {
	bool result;
	int i, v, x, y;
	vector<int> Dx(compoundLabel.size());

	if (unlabelled.empty()) {
		for (i = 0; i < compoundLabel.size(); i++)
			solution[i] = compoundLabel[i];
		return true;
	}
	for (i = 0; i < unlabelled.size(); i++) {
		x = unlabelled[i];
		if (Ordering[x] == Level) break;
	}
	result = false;
	for (i = 0; i < compoundLabel.size(); i++)
   		Dx[i] = i;
	do {
		// pick a random value from domain of x
		i = rand() % Dx.size();
		v = Dx[i];
		vector<int>::iterator vIterator = find(Dx.begin(), Dx.end(), v);
		Dx.erase(vIterator);
		if (Mark[x][v] >= LowUnit[x]) {
			if (Compatible(x, v, LowUnit, Ordering, Mark, compoundLabel)) {
				compoundLabel[x] = v;
				vIterator = find(unlabelled.begin(), unlabelled.end(), x);
				unlabelled.erase(vIterator);
				result = BM1(Level + 1, LowUnit, Ordering, Mark, 
					unlabelled, compoundLabel, solution);
				if (!result) {
					compoundLabel[x] = - 1;
					unlabelled.push_back(x);
				}
			}
		}
	} while (!Dx.empty() && !result);
	if (!result) {
		LowUnit[x] = Level - 1;
		for (i = 0; i < unlabelled.size(); i++) {
			y = unlabelled[i];
			LowUnit[y] = LowUnit[y] < Level - 1 ? LowUnit[y] : Level - 1;
		}
	}
	return result;
}

bool Backmark1(vector<int> unlabelled, vector<int> compoundLabel, vector<int> &solution) {
	int i, n = compoundLabel.size(), v, x;
	int *LowUnit = new int[n];
	int *Ordering = new int[n];
	int **Mark = new int*[n];

	for (i = 0; i < n; i++)
		Mark[i] = new int[n];
	i = 0;
	for (x = 0; x < n; x++) {
		LowUnit[x] = 0;
		for (v = 0; v < n; v++)
			Mark[x][v] = 0;
		Ordering[x] = i++;
	}
	return BM1(0, LowUnit, Ordering, Mark, unlabelled, compoundLabel, solution);
}
	
void printSolution(vector<int> &solution) {
	char hyphen[256];
	int column, i, i4, n = solution.size(), row;

	if (n <= 12) {
		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, n = atoi(argv[1]);
	vector<int> compoundLabel(n, - 1), solution(n, - 1), unlabelled(n);
	for (i = 0; i < n; i++)
   		unlabelled[i] = i;
	srand(time(NULL));
	if (Backmark1(unlabelled, compoundLabel, solution))
		printSolution(solution);
	else
		cout << "problem has no solution" << endl;
	return 0;
}