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

	GENET algorithm from section 8.3.2 of _Foundations of
	Constraint Satisfaction_ by E. P. K. Tsang page 261.
	Applied to the n-queens problem.
*/

#include <iostream.h>
#include <stdlib.h>
#include <time.h>

const int MaxEpochs = 1000;
const int MaxRowColumn = 20000;

class Node {
private:
	bool on;
public:
	Node(void) {on = false;}
	bool getOn(void) {return on;}
	void setOn(bool on) {this->on = on;}
};

class RowColumn {
private:
	int column, row;
public:
	RowColumn(void) {}
	RowColumn(int row, int column) {
		this->column = column;
		this->row = row;
	}
	int getColumn(void) {return column;}
	int getRow(void) {return row;}
	void setColumn(int column) {this->column = column;}
	void setRow(int row) {this->row = row;}
};

class Adjacency {
private:
	int count, weight[MaxRowColumn];
	RowColumn beg[MaxRowColumn], end[MaxRowColumn];
public:
	Adjacency(void) {count = 0;}
	void addEndPoints(int row1, int column1, int row2, int column2) {
		int i;

		for (i = 0; i < count; i++)
			if (row1 == beg[i].getRow() && column1 == beg[i].getColumn())
				if (row2 == end[i].getRow() && column2 == end[i].getColumn())
					return;
		for (i = 0; i < count; i++)
			if (row1 == end[i].getRow() && column1 == end[i].getColumn())
				if (row2 == beg[i].getRow() && column2 == beg[i].getColumn())
					return;
		beg[count].setColumn(column1);
		beg[count].setRow(row1);
		end[count].setColumn(column2);
		end[count].setRow(row2);
		weight[count] = - 1;
		if (count++ == MaxRowColumn) {
			cout << "about to overrun array bounds!" << endl;
			exit(1);
		}
	}
	void decrementWeights(Node **node) {
		int i, column1, column2, row1, row2;

		for (i = 0; i < count; i++) {
			row1 = beg[i].getRow();
			column1 = beg[i].getColumn();
			row2 = end[i].getRow();
			column2 = end[i].getColumn();
			if (node[row1][column1].getOn() && node[row2][column2].getOn())
				weight[i] -= 1;
		}
	}
	int getInput(int x, int y, Node **node) {
		int i, sum = 0;

		for (i = 0; i < count; i++) {
			if (x == beg[i].getRow() && y == beg[i].getColumn()) {
				if (node[end[i].getRow()][end[i].getColumn()].getOn())
					sum += weight[i];
			}
			else if (x == end[i].getRow() && y == end[i].getColumn()) {
				if (node[beg[i].getRow()][beg[i].getColumn()].getOn())
					sum += weight[i];
			}
		}
		return sum;
	}
	friend ostream &operator << (ostream &out, Adjacency &adjacency) {
		for (int i = 0; i < adjacency.count; i++)
			cout << adjacency.beg[i].getRow() << '\t'
				 << adjacency.beg[i].getColumn() << '\t'
				 << adjacency.end[i].getRow() << '\t'
				 << adjacency.end[i].getColumn() << endl;
		return out;
	}
};

bool constraintViolated(int row1, int column1, int row2, int column2) {
	if (row1 == row2 || column1 == column2) return true;
	if (row1 - row2 == column1 - column2 || row1 - row2 == column2 - column1)
		return true;
	return false;
}

void initNetwork(int n, Adjacency &adjacency, Node **node) {
	int column1, column2, i, row1, row2;

	for (row1 = 0; row1 < n; row1++) {
		for (column1 = 0; column1 < n; column1++) {
			for (row2 = 0; row2 < n; row2++) {
				for (column2 = 0; column2 < n; column2++) {
					if (row1 == row2 && column1 == column2) continue;
					if (constraintViolated(row1, column1, row2, column2))
						adjacency.addEndPoints(row1, column1, row2, column2);
				}
			}
		}
	}
	// turn on a random node in each column
	for (i = 0; i < n; i++)
		node[rand() % n][i].setOn(true);
}

int GENET(int nodesPerCluster, int numberVariables, int *solution) {
	bool onNodeInLabelSet;
	bool *Modified = new bool[numberVariables];
	int i, j, lsCount, max, onNodeJ, sum;
	int epochs = 0;
	int *inp = new int[nodesPerCluster];
	int *labelSet = new int[nodesPerCluster];
	Adjacency adjacency;
	Node **node = new Node*[nodesPerCluster];

	for (i = 0; i < nodesPerCluster; i++)
		node[i] = new Node[numberVariables];
	initNetwork(numberVariables, adjacency, node);
	do {
		do {
			for (i = 0; i < numberVariables; i++)
				Modified[i] = false;
			for (i = 0; i < numberVariables; i++) {
				if (!Modified[i]) {
					for (j = 0; j < nodesPerCluster; j++) {
						if (node[j][i].getOn()) {
							onNodeJ = j;
							break;
						}
					}
					max = - 2000000000;
					for (j = 0; j < nodesPerCluster; j++) {
						inp[j] = adjacency.getInput(j, i, node);
						if (inp[j] > max) max = inp[j];
					}
					lsCount = 0;
					for (j = 0; j < nodesPerCluster; j++)
						if (inp[j] == max) labelSet[lsCount++] = j;
					onNodeInLabelSet = false;
					for (j = 0; !onNodeInLabelSet && j < lsCount; j++)
						onNodeInLabelSet = labelSet[j] == onNodeJ;	
					if (!onNodeInLabelSet) {
						node[onNodeJ][i].setOn(false);
						Modified[i] = true;
						node[labelSet[rand() % lsCount]][i].setOn(true);
					}
				}
			}
			for (i = 0; i < numberVariables; i++)
				if (Modified[i]) break;
		} while (i != numberVariables);
		epochs++;
		sum = 0;
		for (i = 0; i < numberVariables; i++)
			for (j = 0; j < nodesPerCluster; j++)
				if (node[j][i].getOn())
					sum += adjacency.getInput(j, i, node);
		if (sum < 0) adjacency.decrementWeights(node);
	} while (sum != 0 && epochs < MaxEpochs);
	cout << "state\tvar\tdomain\tinput" << endl;
	for (i = 0; i < numberVariables; i++) {
		for (j = 0; j < nodesPerCluster; j++) {
			max = adjacency.getInput(j, i, node);
			if (node[j][i].getOn()) cout << "on\t";
			else cout << "off\t";
			cout << (char) (i + 'A') << '\t' << j + 1 << '\t' << max << endl;
		}
	}
	cout << endl;
	for (i = 0; i < numberVariables; i++) {
		cout << (char) (i + 'A') << " = ";
		for (j = 0; j < nodesPerCluster; j++) {
			if (node[j][i].getOn()) {
				cout << j + 1  << ' ';
				solution[i] = j;
				break;
			}
		}
	}
	cout << endl << endl;
	return epochs;
}

void printSolution(int n, int *solution) {
	char hyphen[256];
	int column, i, i4, row;

	if (n <= 16) {
		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 n = atoi(argv[1]);
	if (n * n > MaxRowColumn) {
		cout << "n is too large n * n must be less than " << MaxRowColumn << endl;
		exit(1);
	}
	srand(time(NULL));
	int *solution = new int[n];
	int epochs = GENET(n, n, solution);
	cout << "epochs = " << epochs << endl;
	printSolution(n, solution);
	return 0;
}