/*
	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.
	AC-4 from page 87.
*/

#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 satisfies(int x, int v, int y, int w) {
	if (x == y) return false;
	if (v == w) return false;
	if (x - y == v - w || x - y == w - v) return false;
	return true;
}

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 Label {
private:
	int x, v;
public:
	Label(int x, int v) {this->x = x; this->v = v;}
	int getX(void) {return x;}
	int getV(void) {return v;}
	void setX(int x) {this->x = x;}
	void setV(int v) {this->v = v;}
	bool operator == (const Label &label) {
		return x == label.x && v == label.v;
	}
};

typedef vector<Label> LabelVector;
typedef vector<Label>* LabelVectorPtr;
typedef vector<Label>** LabelVectorMatrixPtr;

void AC4(int n, vector<int> compoundLabel, vector<int> *D) {
	int Total, b, c, i, j, k, l;;
	int **M = new int*[n], ***Counter = new int**[n];
	vector<int>::iterator vIterator;
	vector<Label>::iterator lIterator;
	LabelVector List;
	LabelVectorMatrixPtr S = new LabelVectorPtr[n];

	for (i = 0; i < n; i++) {
		M[i] = new int[n];
		S[i] = new vector<Label>[n];
		for (j = 0; j < n; j++) {
			Counter[i][j] = new int[n];
			M[i][j] = 0;
		}
	}
	for (i = 0; i < n - 1; i++) {
		for (j = i + 1; j < n; j++) {
			for (k = 0; k < D[i].size(); k++) {
				b = D[i][k];
				Total = 0;
				for (l = 0; l < D[j].size(); l++) {
					c = D[j][l];
					if (b != c && compoundLabel[i] == - 1 && satisfies(i, b, j, c)) {
						Label label(i, b);
						Total++;
						S[j][c].push_back(label);
					}
					else {
						Label label(i, b);
						Total++;
						lIterator = find(S[j][c].begin(), S[j][c].end(), label);
						if (lIterator != S[j][c].end())
							S[j][c].push_back(label);
					}
					if (Total == 0) {
						M[i][b] = 1;
						vIterator = find(D[i].begin(), D[i].end(), b);
						if (vIterator != D[i].end()) {
							D[i].erase(vIterator);
							cout << "b erased 1 = " << b << " from " << i << endl;
						}
					}
					Counter[i][j][b] = Total;
				}
			}
		}
	}
	for (i = 0; i < n; i++) {
		for (b = 0; b < n; b++) {
			if (M[i][b] == 1) {
				Label label(i, b);
				List.push_back(label);
			}
		}
	}
	while (!List.empty()) {
		Label label = List[rand() % List.size()];
		lIterator = find(List.begin(), List.end(), label);
		List.erase(lIterator);
		j = label.getX();
		c = label.getV();
		for (k = 0; k < S[j][c].size(); k++) {
			label = S[j][c][k];
			i = label.getX();
			b = label.getV();
			Counter[i][j][b]--;
			if (Counter[i][j][b] == 0 && M[i][b] == 0) {
				cout << "b erased 2 = " << b << " from " << i << endl;
				List.push_back(label);
				M[i][b] = 1;
				vIterator = find(D[i].begin(), D[i].end(), b);
				D[i].erase(vIterator);
			}
		}
	}
}

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 emp, result;
	int i, j, k, 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);
			AC4(compoundLabel.size(), compoundLabel, Dp);
			for (emp = false, k = 0; !emp && k < compoundLabel.size(); k++)
				if (compoundLabel[k] == - 1) emp = Dp[k].empty();
			if (!emp) {
				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;
}