/*
	Author:	Pate Williams (c) 2000

	Morris' breakout algorithm
	Our breakout algorithms
	Minton's MCHC
	Wallace & Freuder MCHC
	n-queens problem
	Optimized version
*/

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

//#define DEBUG 1

const int Base = 0;	// base algorithm
const int Limit = 7;	// limit algorithm
const int Size = 7;	// size of arrays (# of algorithms)
const int MaxN = 500;	// maximum number of queens
const int MaxBreakouts = MaxN;	// maximum number of breakouts
const int MaxCandSol = 100000;	// maximum number of candidate solutions

int candidateSolutions, constraintChecks;

class Breakout {
private:
	int ltTuple, ltValue, rtTuple, rtValue, weight;
public:
	Breakout(void) { ltTuple = rtTuple = weight = - 1; };
	Breakout(int ltTup, int ltVal, int rtTup, int rtVal) {
		ltTuple = ltTup;
		ltValue = ltVal;
		rtTuple = rtTup;
		rtValue = rtVal;
	};
	Breakout(int ltTup, int ltVal, int rtTup, int rtVal, int w) {
		ltTuple = ltTup;
		ltValue = ltVal;
		rtTuple = rtTup;
		rtValue = rtVal;
		weight = w;
	};
	Breakout(Breakout &breakout) {
		ltTuple = breakout.ltTuple;
		ltValue = breakout.ltValue;
		rtTuple = breakout.rtTuple;
		rtValue = breakout.rtValue;
		weight = breakout.weight;
	};
	bool operator == (Breakout &breakout) {
		return ltTuple == breakout.ltTuple &&
			   ltValue == breakout.ltValue &&
			   rtTuple == breakout.rtTuple &&
			   rtValue == breakout.rtValue;
	};
	bool operator < (Breakout &breakout) {
		if (ltTuple < breakout.ltTuple)
			return true;
		if (ltTuple > breakout.ltTuple)
			return false;
		if (ltValue < breakout.ltValue)
			return true;
		if (ltValue > breakout.ltValue)
			return false;
		if (rtTuple < breakout.rtTuple)
			return true;
		if (rtTuple > breakout.rtTuple)
			return false;
		if (rtValue < breakout.rtValue)
			return true;
		return false;
	};
	int getLtTuple(void) { return ltTuple; };
	int getLtValue(void) { return ltValue; };
	int getRtTuple(void) { return rtTuple; };
	int getRtValue(void) { return rtValue; };
	int getWeight(void) { return weight; };
	void setLtTuple(int lt) { ltTuple = lt; };
	void setRtTuple(int rt) { rtTuple = rt; };
	void setWeight(int w) { weight = w; };
	void incrementWeight(void) { weight++; };
	friend ostream &operator << (ostream &output, const Breakout &breakout) {
		cout << breakout.ltTuple << ' ' << breakout.ltValue << ' '
			 << breakout.rtTuple << ' ' << breakout.rtValue << ' '
			 << breakout.weight;
		return output;
	};
};

class BreakoutList {
private:
	int length;
	Breakout breakout[MaxBreakouts];
public:
	BreakoutList(void) { length = 0; };
	int getLength(void) { return length; };
	void setLength(int len) { length = len; };
	void add(Breakout &bo) {
		add(bo.getLtTuple(), bo.getLtValue(),
			bo.getRtTuple(), bo.getRtValue(), bo.getWeight());
	};
	void add(int ltTuple, int ltValue, int rtTuple, int rtValue, int weight) {
		bool found;
		int i, index;
		Breakout bo(ltTuple, ltValue, rtTuple, rtValue, weight);

		assert(length < MaxBreakouts);
		for (found = false, i = index = 0; !found && i < length; i++) {
			if (bo < breakout[i]) {
				found = true;
				index = i;
			}
		}
		if (!found) {
			breakout[length++] = bo;
			return;
		}
		for (i = length; i >= index + 1; i--)
			breakout[i] = breakout[i - 1];
		breakout[index] = bo;
		length++;
	};
	int binarySearch(Breakout bo) {
		int lo = 0, hi = length - 1, mid;

		while (hi >= lo) {
			mid = (lo + hi) / 2;
			if (bo == breakout[mid])
				return mid;
			if (bo < breakout[mid])
				hi = mid - 1;
			else
				lo = mid + 1;
		}
		return - 1;
	};
	Breakout &operator [](int i) { return breakout[i]; };
	friend ostream &operator << (ostream &output, const BreakoutList &breakoutList) {
		for (int i = 0; i < breakoutList.length; i++)
			output << breakoutList.breakout[i] << endl; 
		return output;
	};
};

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

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

inline
bool violation(int *queen, Breakout &breakout) {
	int i = breakout.getLtTuple(), j = breakout.getRtTuple();
	int a = queen[i], b = queen[j];

	if (breakout.getLtValue() == a && breakout.getRtValue() == b) {
		if (a == b)
			return true;
		if (abs(i - j) == abs(a - b)) 
			return true;
	}
	return false;
}

bool ndboAlgorithm(int n, int *queen, int &breakouts) {
	bool commit;
	int c, i, index, j, newCost, oldCost, oldValue, t, tempCost, value, wt;
	int cv[MaxN], tempCV[MaxN];
	BreakoutList list;

	breakouts = 0;
	for (i = oldCost = 0; i < n; i++) {
		for (c = j = 0; j < n; j++)
			if (j != i && violation(i, j, queen))
				c++;
		cv[i] = c;
		oldCost += c;
	}
	oldCost /= 2;
	while (oldCost != 0) {
		tempCost = oldCost;
		for (i = 0; oldCost != 0 && i < n; i++) {
			if (cv[i] != 0) {
				oldValue = queen[i];
				for (j = 0; j < n; j++)
					tempCV[j] = cv[j];
				for (commit = false, value = 0; !commit && oldCost != 0 
					&& value < n; value++) {
					if (value != oldValue) {
						for (j = 0; j < n; j++)
							if (j != i && violation(i, j, queen))
								cv[j]--;
						queen[i] = value;
						for (c = j = 0; j < n; j++) {
							if (j != i && violation(i, j, queen)) {
								c++;
								cv[j]++;
							}
						}
						cv[i] = c;
						for (j = t = 0; j < n; j++)
							t += cv[j];
						for (j = wt = 0; j < list.getLength(); j++) {
							Breakout breakout = list[j];
							if (violation(queen, breakout))
								wt += breakout.getWeight();
						}
						newCost = t / 2 + wt;
						if (newCost < oldCost) {
							oldCost = newCost;
							commit = true;
						}
						candidateSolutions++;
						if (candidateSolutions == MaxCandSol)
							return false;
					}
				}
				if (!commit) {
					queen[i] = oldValue;
					for (j = 0; j < n; j++)
						cv[j] = tempCV[j];
				}
			}
		}
		if (oldCost == tempCost) {
			breakouts++;
			for (i = oldCost = 0; i < n - 1; i++) {
				for (j = i + 1; j < n; j++) {
					if (violation(i, j, queen)) {
						Breakout breakout(i, queen[i], j, queen[j], 1);
						index = list.binarySearch(breakout);
						if (index != - 1) {
							list[index].incrementWeight();
							oldCost += 1 + list[index].getWeight();
						}
						else {
							list.add(breakout);
							oldCost += 2;
						}
					}
				}
			}
		}
	}
	return true;
}

bool sdboAlgorithm1(int n, int *queen, int &breakouts) {
	int minCost, tempCost, oldValue;
	int c, i, index, j, oldCost, value, wt, t;
	int array[MaxN], cv[MaxN], newCost[MaxN], tempCV[MaxN][MaxN];
	BreakoutList list;

	breakouts = 0;
	for (i = oldCost = 0; i < n; i++) {
		for (c = j = 0; j < n; j++)
			if (j != i && violation(i, j, queen))
				c++;
		cv[i] = c;
		oldCost += c;
	}
	oldCost /= 2;
	while (oldCost != 0) {
		tempCost = oldCost;
		for (i = 0; oldCost != 0 && i < n; i++) {
			if (cv[i] != 0) {
				oldValue = queen[i];
				for (value = 0; value < n; value++) {
					if (value != oldValue) {
						for (j = 0; j < n; j++)
							tempCV[value][j] = cv[j];
						for (j = 0; j < n; j++)
							if (j != i && violation(i, j, queen))
								tempCV[value][j]--;
						queen[i] = value;
						for (c = j = 0; j < n; j++) {
							if (j != i && violation(i, j, queen)) {
								c++;
								tempCV[value][j]++;
							}
						}
						tempCV[value][i] = c;
						for (j = t = 0; j < n; j++)
							t += tempCV[value][j];
						for (j = wt = 0; j < list.getLength(); j++) {
							Breakout breakout = list[j];
							if (violation(queen, breakout))
								wt += breakout.getWeight();
						}
						newCost[value] = t / 2 + wt;
						queen[i] = oldValue;
						candidateSolutions++;
						if (candidateSolutions == MaxCandSol)
							return false;
					}
					else
						newCost[value] = oldCost;
				}
				minCost = newCost[0];
				for (value = 1; value < n; value++)
					if (newCost[value] < minCost)
						minCost = newCost[value];
				for (j = value = 0; value < n; value++)
					if (minCost == newCost[value])
						array[j++] = value;
				value = array[0];
				if (value != oldValue) {
					oldCost = minCost;
					queen[i] = value;
					for (j = 0; j < n; j++)
						cv[j] = tempCV[value][j];
				}	
			}
		}
		if (oldCost == tempCost) {
			breakouts++;
			for (i = oldCost = 0; i < n - 1; i++) {
				for (j = i + 1; j < n; j++) {
					if (violation(i, j, queen)) {
						Breakout breakout(i, queen[i], j, queen[j], 1);
						index = list.binarySearch(breakout);
						if (index != - 1) {
							list[index].incrementWeight();
							oldCost += 1 + list[index].getWeight();
						}
						else {
							list.add(breakout);
							oldCost += 2;
						}
					}
				}
			}
		}
	}
	return true;
}

bool sdboAlgorithm2(int n, int *queen, int &breakouts) {
	int minCost, tempCost, oldValue;
	int c, i, index, j, oldCost, value, wt, t;
	int array[MaxN], cv[MaxN], newCost[MaxN], tempCV[MaxN][MaxN];
	BreakoutList list;

	breakouts = 0;
	for (i = oldCost = 0; i < n; i++) {
		for (c = j = 0; j < n; j++)
			if (j != i && violation(i, j, queen))
				c++;
		cv[i] = c;
		oldCost += c;
	}
	oldCost /= 2;
	while (oldCost != 0) {
		tempCost = oldCost;
		for (i = 0; oldCost != 0 && i < n; i++) {
			if (cv[i] != 0) {
				oldValue = queen[i];
				for (value = 0; value < n; value++) {
					if (value != oldValue) {
						for (j = 0; j < n; j++)
							tempCV[value][j] = cv[j];
						for (j = 0; j < n; j++)
							if (j != i && violation(i, j, queen))
								tempCV[value][j]--;
						queen[i] = value;
						for (c = j = 0; j < n; j++) {
							if (j != i && violation(i, j, queen)) {
								c++;
								tempCV[value][j]++;
							}
						}
						tempCV[value][i] = c;
						for (j = t = 0; j < n; j++)
							t += tempCV[value][j];
						for (j = wt = 0; j < list.getLength(); j++) {
							Breakout breakout = list[j];
							if (violation(queen, breakout))
								wt += breakout.getWeight();
						}
						newCost[value] = t / 2 + wt;
						queen[i] = oldValue;
						candidateSolutions++;
						if (candidateSolutions == MaxCandSol)
							return false;
					}
					else
						newCost[value] = oldCost;
				}
				minCost = newCost[0];
				for (value = 1; value < n; value++)
					if (newCost[value] < minCost)
						minCost = newCost[value];
				for (j = value = 0; value < n; value++)
					if (minCost == newCost[value])
						array[j++] = value;
				value = array[rand() % j];
				if (value != oldValue) {
					oldCost = minCost;
					queen[i] = value;
					for (j = 0; j < n; j++)
						cv[j] = tempCV[value][j];
				}
			}
		}
		if (oldCost == tempCost) {
			breakouts++;
			for (i = oldCost = 0; i < n - 1; i++) {
				for (j = i + 1; j < n; j++) {
					if (violation(i, j, queen)) {
						Breakout breakout(i, queen[i], j, queen[j], 1);
						index = list.binarySearch(breakout);
						if (index != - 1) {
							list[index].incrementWeight();
							oldCost += 1 + list[index].getWeight();
						}
						else {
							list.add(breakout);
							oldCost += 2;
						}
					}
				}
			}
		}
	}
	return true;
}

void preprocessing(int n, int *queen) {
	int con, i, j, minConflict, value;
	int c[MaxN], conflict[MaxN];

	for (i = 0; i < n; i++) {
		for (value = 0; value < n; value++) {
			queen[i] = value;
			for (con = j = 0; j < i; j++)
				if (violation(i, j, queen))
					con++;
			conflict[value] = con;
		}
		minConflict = conflict[0];
		for (value = 1; value < n; value++)
		if (conflict[value] < minConflict)
			minConflict = conflict[value];
		for (value = j = 0; value < n; value++)
			if (minConflict == conflict[value])
				c[j++] = value;
		queen[i] = c[rand() % j];	
	}
}

bool MintonMchcAlgorithm(int n, int *queen) {
	int con, count, i, j, min, oldCost, oldValue, t, value;
	int conflict[MaxN], cost[MaxN], index[MaxN];
	int cv[MaxN], tempCV[MaxN][MaxN];

	for (i = oldCost = 0; i < n; i++) {
		for (con = j = 0; j < n; j++)
			if (j != i && violation(i, j, queen))
				con++;
		cv[i] = con;
		oldCost += con;
	}
	oldCost /= 2;
	while (oldCost != 0) {
		for (i = 0; oldCost != 0 && i < n; i++) {
			if (cv[i] != 0) {
				oldValue = queen[i];
				for (value = 0; value < n; value++) {
					if (value != oldValue) {
						for (j = 0; j < n; j++)
							tempCV[value][j] = cv[j];
						for (j = 0; j < n; j++)
							if (j != i && violation(i, j, queen))
								tempCV[value][j]--;
						queen[i] = value;
						for (con = j = 0; j < n; j++) {
							if (j != i && violation(i, j, queen)) {
								con++;
								tempCV[value][j]++;
							}
						}
						tempCV[value][i] = con;
						for (j = t = 0; j < n; j++)
							t += tempCV[value][j];
						conflict[value] = con;
						cost[value] = t / 2;
						queen[i] = oldValue;
						candidateSolutions++;
						if (candidateSolutions == MaxCandSol)
							return false;
					}
					else
						conflict[oldValue] = cv[i];
				}
				min = n * n;
				for (value = 0; value < n; value++)
					if (conflict[value] < min)
						min = conflict[value];
				count = 0;
				for (value = 0; value < n; value++)
					if (min == conflict[value])
						index[count++] = value;
				value = index[rand() % count];
				if (value != oldValue) {
					queen[i] = value;
					oldCost = cost[value];
					for (j = 0; j < n; j++)
						cv[j] = tempCV[value][j];
				}
			}
		}
	}
	return true;
}

bool WFMchcAlgorithm(int n, int *queen) {
	bool first = true;
	double p = 0.1, r;
	int con, i, j, minConflict, oldValue, pivot, t, value;
	int c[MaxN], conflict[MaxN];
	int cv[MaxN], tempCV[MaxN][MaxN];

	for (i = 0; i < n; i++) {
		for (con = j = 0; j < n; j++)
			if (j != i && violation(i, j, queen))
				con++;
		if (first && con != 0) {
			first = false;
			pivot = i;
		}
		cv[i] = con;
	}
	for (;;) {
		for (i = 0, j = 0; i < n; i++)
			if (cv[i] >= 1)
				c[j++] = i;
		if (j == 0)
			break;
		do
			i = c[rand() % j];
		while (i == pivot);
		pivot = i;
		r = (double) rand() / RAND_MAX;
		if (r <= p) {
			for (j = 0; j < n; j++)
				if (j != i && violation(i, j, queen))
					cv[j]--;
			queen[i] = rand() % n;
			for (con = j = 0; j < n; j++) {
				if (j != i && violation(i, j, queen)) {
					con++;
					cv[j]++;
				}
			}
			cv[i] = con;
			candidateSolutions++;
			if (candidateSolutions == MaxCandSol)
				return false;
		}
		else {
			oldValue = queen[i];
			for (value = 0; value < n; value++) {
				if (value != oldValue) {
					for (j = 0; j < n; j++)
						tempCV[value][j] = cv[j];
					for (j = 0; j < n; j++)
						if (j != i && violation(i, j, queen))
							tempCV[value][j]--;
					queen[i] = value;
					for (con = j = 0; j < n; j++) {
						if (j != i && violation(i, j, queen)) {
							con++;
							tempCV[value][j]++;
						}
					}
					tempCV[value][i] = con;
					for (j = t = 0; j < n; j++)
						t += tempCV[value][j];
					conflict[value] = con;
					queen[i] = oldValue;
					candidateSolutions++;
					if (candidateSolutions == MaxCandSol)
						return false;
				}
				else
					conflict[value] = cv[i];
			}
			minConflict = conflict[0];
			for (value = 1; value < n; value++)
				if (conflict[value] < minConflict)
					minConflict = conflict[value];
			for (value = 0, j = 0; value < n; value++)
				if (minConflict == conflict[value])
					c[j++] = value;
			value = c[rand() % j];
			if (value != oldValue) {
				queen[i] = value;
				for (j = 0; j < n; j++)
					cv[j] = tempCV[value][j];
			}
		}
	}
	return true;
}

void print(int n, int *queen) {
	char hyphen[256];
	int column, i, i4, 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 = 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[Size][4] = {"NDB", "SD1", "SD2", "MT1", "MT2", "WF1", "WF2"};
	double breakouts[Size] = {0}, candidate[Size] = {0};
	double cc[Size] = {0}, runTime[Size] = {0};
	int bo, i, j, k, l, n, trials, queen[MaxN];
	int converged[Size] = {0};
	clock_t clock0, clock1;
	time_t startTime = time(NULL), finishTime;

#ifdef DEBUG
	if (argc != 2) {
		cout << "usage: " << argv[0] << " n" << endl;
		exit(0);
	}
	n = atoi(argv[1]);
	srand(startTime);
	for (i = 0; i < n; i++)
		queen[i] = rand() % n;
	ndboAlgorithm(n, queen, bo);
	print(n, queen);
	cout << endl;
	for (i = 0; i < n; i++)
		queen[i] = rand() % n;
	sdboAlgorithm1(n, queen, bo);
	print(n, queen);
	cout << endl;
	for (i = 0; i < n; i++)
		queen[i] = rand() % n;
	sdboAlgorithm2(n, queen, bo);
	print(n, queen);
	cout << endl;
	for (i = 0; i < n; i++)
		queen[i] = rand() % n;
	MintonMchcAlgorithm(n, queen);
	print(n, queen);
	cout << endl;
	for (i = 0; i < n; i++)
		queen[i] = rand() % n;
	preprocessing(n, queen);
	MintonMchcAlgorithm(n, queen);
	print(n, queen);
	cout << endl;
	cout << endl;
	for (i = 0; i < n; i++)
		queen[i] = rand() % n;
	WFMchcAlgorithm(n, queen);
	print(n, queen);
	cout << endl;
	for (i = 0; i < n; i++)
		queen[i] = rand() % n;
	preprocessing(n, queen);
	WFMchcAlgorithm(n, queen);
	print(n, queen);
	cout << endl;
	return 0;
#endif
	if (argc != 3) {
		cout << "usage: " << argv[0] << " n trials" << endl;
		exit(0);
	}
	n = atoi(argv[1]);
	trials = atoi(argv[2]);
	srand(startTime);
	for (i = 0; i < trials; i++) {
		for (j = Base; j < Limit; j++) {
			candidateSolutions = 1;
			constraintChecks = 0;
			bo = 0;
			clock0 = clock();
			for (k = 0; k < n; k++)
				queen[k] = rand() % n;
			if (j == 0)
				value = ndboAlgorithm(n, queen, bo);
			else if (j == 1)
				value = sdboAlgorithm1(n, queen, bo);
			else if (j == 2)
				value = sdboAlgorithm2(n, queen, bo);
			else if (j == 3)
				value = MintonMchcAlgorithm(n, queen);
			else if (j == 4) {
				preprocessing(n, queen);
				value = MintonMchcAlgorithm(n, queen);
			}
			else if (j == 5)
				WFMchcAlgorithm(n, queen);
			else if (j == 6) {
				preprocessing(n, queen);
				WFMchcAlgorithm(n, queen);
			}
			clock1 = clock();
			if (value) {
				for (k = 0; k < n - 1; k++) {
					for (l = k + 1; l < n; l++) {
						if (violation(k, l, queen)) {
							cout << "constraint violation!" << endl;
							exit(0);
						}
					}
				}		
				runTime[j] += (double) (clock1 - clock0) / CLOCKS_PER_SEC;
				breakouts[j] += bo;
				candidate[j] += candidateSolutions;
				cc[j] += constraintChecks;
				converged[j]++;
			}
		}
	}
	cout << "number of queens:             " << n << endl;
	cout << "random number generator seed: " << startTime << endl;
	cout << "number of trials:             " << trials << endl;
	cout << "algo\tcan sol\tbo\tcc\t%\ttime (s)" << endl;
	for (i = Base; i < Limit; i++) {
		if (converged[i] != 0)
			cout << name[i] << '\t'
				 << candidate[i] / converged[i] << '\t'
				 << breakouts[i] / converged[i] << '\t'
				 << cc[i] / converged[i] << '\t'
				 << 100.0 * converged[i] / trials << '\t'
				 << runTime[i] / converged[i] << endl;
		else
			cout << name[i] << '\t' << 0 << '\t'
				 << 0 << '\t' << 0 << '\t' << 0 << endl;
	}
	finishTime = time(NULL) - startTime;
	cout << "total time in seconds: " << finishTime << endl;
	return 0;
}