/*
	Author:	James Pate Williams (c) 2000

	Sosic and Gu's Queen Search algorithm to solve the n-queens problem
*/

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

//#define DEBUG 1	// see that qs solves n-queens problem

const int MaxN = 10000;	// maximum number of queens

int MaxCandSol;	// maximum number of candidate solutions
int constraintChecks;

inline
bool violation(int i, int j, int queen[MaxN]) {
	int a = queen[i], b = queen[j];

	constraintChecks++;
	if (a == - 1 || b == - 1)
		return false;
	//if (a == b)
	//	return true;
	if (abs(i - j) == abs(a - b)) 
		return true;
	return false;
}

inline
int f(int n, int cv[MaxN], int queen[MaxN]) {
	// calculate the total number of constraint violations
	int c, i, j, v = 0;

	for (i = 0; i < n; i++) {
		for (c = 0, j = 0; j < n; j++)
			if (i != j && violation(i, j, queen))
				c++;
		cv[i] = c;
		v += c;
	}
	return v;
}

bool qs(int n, int queen[MaxN], int &candidateSolutions) {
	bool used[MaxN];
	int c, cs, f0, f1, i, iTemp, j, jTemp, k, swaps;
	int cv[MaxN], queenTemp[MaxN], tempCV[MaxN];

	candidateSolutions = 0;
	constraintChecks = 0;
	do {
		cs = 1;
		for (i = 0; i < n; i++)
			used[i] = false;
		// initilize queen to random permutation of 0 to n - 1
		for (i = 0; i < n; i++) {
			do
				j = rand() % n;
			while (used[j]);
			used[j] = true;
			queen[i] = j;
		}
		f0 = f(n, cv, queen);
		candidateSolutions++;
		if (f0 == 0)
			break;
		do {
			swaps = 0;
			for (i = 0; i < n - 1; i++) {
				for (j = i + 1; j < n; j++) {
					if (cv[i] != 0 || cv[j] != 0) {
						// copy queen to queenTemp
						for (k = 0; k < n; k++) {
							queenTemp[k] = queen[k];
							tempCV[k] = cv[k];
						}
						iTemp = queen[i];
						jTemp = queen[j];
						// propagate out-ness
						for (k = 0; k < n; k++) {
							if (k != i && violation(k, i, queen)) {
								tempCV[k]--;
								tempCV[i]--;
							}
						}
						queen[i] = - 1;
						// propagate out-ness
						for (k = 0; k < n; k++) {
							if (k != j && violation(k, j, queen)) {
								tempCV[k]--;
								tempCV[j]--;
							}
						}
						queen[i] = iTemp;
						// propagate in-ness
						queenTemp[i] = jTemp;
						queenTemp[j] = - 1;
						for (c = k = 0; k < n; k++) {
							if (k != i && violation(k, i, queenTemp)) {
								c++;
								tempCV[k]++;
							}
						}
						tempCV[i] = c;
						// propagate in-ness
						queenTemp[j] = iTemp;
						for (c = k = 0; k < n; k++) {
							if (k != j && violation(k, j, queenTemp)) {
								c++;
								tempCV[k]++;
							}
						}
						tempCV[j] = c;
						// calculate f1
						for (f1 = k = 0; k < n; k++)
							f1 += tempCV[k];
						candidateSolutions++;
						cs++;
						if (cs >= MaxCandSol)
							break;
						if (f1 <= f0) {
							for (k = 0; k < n; k++) {
								queen[k] = queenTemp[k];
								cv[k] = tempCV[k];
							}
							f0 = f1;
							swaps++;
						}
					}
				}
				if (cs >= MaxCandSol)
					break;
			}
			if (cs >= MaxCandSol)
				break;
		} while (swaps != 0);
	} while (f0 != 0);
	return true;
}

void print(int n, int *queen) {
	char hyphen[256];
	int column, i, i4, 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 = queen[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 << ' ' << queen[row] << endl;
}

int main(int argc, char **argv) {
	bool value;
	char name[4] = "QS";
	double cc = 0, candSol = 0, runTime = 0;
	int candidateSolutions, i, n, queen[MaxN], trials;
	int converged = 0;
	clock_t clock0, clock1;
	time_t startTime = time(NULL), finishTime;
	
	srand(startTime);
#ifdef DEBUG
	if (argc != 2) {
		cerr << "usage: " << argv[0] << " n" << endl;
		exit(0);
	}
	n = atoi(argv[1]);
	if (n < 4 || n > MaxN) {
		cerr << "4 <= n <= " << MaxN << endl;
		exit(0);
	}
	qs(n, queen, candidateSolutions);
	print(n, queen);
	return 0;
#endif
	if (argc != 3) {
		cerr << "usage: " << argv[0] << " n trials" << endl;
		exit(0);
	}
	n = atoi(argv[1]);
	if (n < 4 || n > MaxN) {
		cerr << "error: 4 <= n <= " << MaxN << endl;
		exit(0);
	}
	trials = atoi(argv[2]);
	MaxCandSol = 50 * n;
	for (i = 0; i < trials; i++) {
		clock0 = clock();
		value = qs(n, queen, candidateSolutions);
		clock1 = clock();
		if (value) {
			converged++;
			cc += constraintChecks;
			candSol += candidateSolutions;
			runTime += (double) (clock1 - clock0) / CLOCKS_PER_SEC;
			for (int j = 0; j < n - 1; j++) 
				for (int k = j + 1; k < n; k++)
					if (violation(j, k, queen))
						cout << i << " constraint violation!" << endl;
		}
	}
	cout << "number of queens:             " << '\t' << n << endl;
	cout << "random number generator seed: " << '\t' << startTime << endl;
	cout << "number of trials:             " << '\t' << trials << endl;
	cout << "algo\tcan sol\tcc\t%\ttime (s)" << endl;
	cout << name << '\t'
		 << candSol / converged << '\t' << cc / converged << '\t'
		 << 100.0 * converged / trials << '\t'
		 << runTime / converged << endl;
	finishTime = time(NULL) - startTime;
	cout << "total time in seconds: " << finishTime << endl;
	return 0;
}