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

	Arc-consistency lookahead 1 algorithm applied to the
	N-Queens CSP. Algorithm from _Foundations of Constraint
	Satisfaction_ by E. P. K. Tsang Chapter 5 page 127.
	Uses AC-3 from page 83.
*/

#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 - 1; i++) {
		a = Q[i];
		for (j = i + 1; j < n; j++) {
			b = Q[j];
			if (a != - 1 && b != - 1) {
				if (a == b) c++;
				if (i - j == a - b || i - j == b - a) c++;
			}
		}
	}
	return c;
}

bool C(int x, int y, vector<int> &compoundLabel) {
	int a = compoundLabel[x];
	int b = compoundLabel[y];

	if (a == b) return true;
	if (x - y == a - b || x - y == b - a) true;
	return false;
}

bool ReviseDomain(int n, int x, int y, vector<int> *D) {
	bool c, deleted = false;
	int a, b, i, j;
	vector<int> label(n, - 1);

	for (i = 0; i < D[x].size(); i++) {
		a = D[x][i];
		label[x] = a;
		for (c = false, j = 0; !c && j < D[y].size(); j++) {
			b = D[y][j];
			label[y] = b;
			if (constraintsViolated(label) == 0)
				c = true;
			label[y] = - 1;
		}
		if (!c) {
			vector<int>::iterator vIterator = find(D[x].begin(), D[x].end(), a);
			if (vIterator == D[x].end()) {
				cout << "error: can't find a = " << a << endl;
				cout << "D[" << x << "][" << i << "] = " << a << endl;
				cout << "D[" << x << "].size() = " << D[x].size() << endl;
				for (j = 0; j < D[x].size(); j++)
					cout << "D[" << x << "][" << j << "] = " << D[x][j] << endl;
				exit(1);
			}
			D[x].erase(vIterator);
			deleted = true;
		}
		label[x] = - 1;
	}
	return deleted;
}

class Arc {
private:
	int x, y;
public:
	Arc(void) {}
	Arc(int x, int y) {
		this->x = x, this->y = y;
	}
	int getX(void) {return x;}
	int getY(void) {return y;}
	void setX(int x) {this->x = x;}
	void setY(int y) {this->y = y;}
	bool operator == (const Arc &arc) {
		return x == arc.x && y == arc.y;
	}
};

void AC3(int n, vector<int> &compoundLabel, vector<int> *D) {
	int x, y, z;
	Arc arc;
	vector<Arc>::iterator aIterator;
	vector<Arc> Q;

	for (x = 0; x < n - 1; x++) {
		for (y = x + 1; y < n; y++) {
			if (C(x, y, compoundLabel)) {
				arc.setX(x);
				arc.setY(y);
				aIterator = find(Q.begin(), Q.end(), arc);
				if (aIterator == Q.end()) Q.push_back(arc);
			}
		}
	}
	while (!Q.empty()) {
		arc = Q[rand() % Q.size()];
		aIterator = find(Q.begin(), Q.end(), arc);
		Q.erase(aIterator);
		x = arc.getX();
		y = arc.getY();
		if (ReviseDomain(n, x, y, D)) {
			for (z = 0; z < n - 1; z++) {
				for (x = z + 1; x < n; x++) {
					if (z != y && C(z, x, compoundLabel)) {
						arc.setX(z);
						arc.setY(x);
						aIterator = find(Q.begin(), Q.end(), arc);
						if (aIterator == Q.end()) Q.push_back(arc);
					}
				}
			}
		}
	}
}

vector<int> *Update1(int n, int x, int v, vector<int> unlabelled, vector<int> *D) {
	int i, j, u, y;
	vector<int> Q(n, - 1), *Dp = new vector<int>[n];

	if (Dp == NULL) {
		cout << "error: can't allocate memory in Update1" << endl;
		exit(1);
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < D[i].size(); j++)
			Dp[i].push_back(D[i][j]);
	Q[x] = v;
	for (i = 0; i < unlabelled.size(); i++) {
		y = unlabelled[i];
		vector<int> Dpp = Dp[y];
		vector<int>::iterator vIterator = Dpp.begin();
		while (vIterator != Dpp.end()) {
			u = *vIterator;
			Q[y] = u;
			if (constraintsViolated(Q) != 0) {
				vector<int>::iterator uIterator = find(Dp[y].begin(), Dp[y].end(), u);
				Dp[y].erase(uIterator);
			}
			Q[y] = - 1;
			vIterator++;
		}
	}
	return Dp;
}

bool ArcConsistency1(vector<int> unlabelled, vector<int> compoundLabel,
	vector<int> &solution, vector<int> *D) {
	bool result;
	int count, 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];
	do {
		// pick a random value from domain of x
		j = rand() % D[x].size();
		v = D[x][j];
		vector<int>::iterator vIterator = find(D[x].begin(), D[x].end(), v);
		D[x].erase(vIterator);
		compoundLabel[x] = v;
		if (constraintsViolated(compoundLabel) == 0) {
			vIterator = find(unlabelled.begin(), unlabelled.end(), x);
			unlabelled.erase(vIterator);			
			vector<int> *Dp = Update1(compoundLabel.size(), x, v, unlabelled, D);
			AC3(compoundLabel.size(), compoundLabel, Dp);
			for (count = 0, i = 0; i < compoundLabel.size(); i++)
				if (compoundLabel[i] == - 1 && Dp[i].empty()) count = 1;
			if (count == 0) {
				result = ArcConsistency1(unlabelled, compoundLabel, solution, Dp);
				if (result) return result;
				unlabelled.push_back(x);
			}
			else
				unlabelled.push_back(x);
		}
		else
			compoundLabel[x] = - 1;
	} while (!D[x].empty());
	return false;
}

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]);
	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);
	}
	srand(time(NULL));
	if (ArcConsistency1(unlabelled, compoundLabel, solution, D))
		printSolution(solution);
	else
		cout << "problem has no solution" << endl;
	return 0;
}