Wallace and Freuder’s Min-Conflicts Hill Climber Solution of the N-Queens Problem

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

	Min-conflicts hill-climbing applied to N-Queens problem.
	Wallace and Freuder's algorithm with an unbiased
	preprocessor.
*/

#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

const bool Debug = true;
const int MaxRepairs = 1000000;

int conflicts(int a, int i, int n, vector<int> &Q) {
	int b, c = 0, j;

	for (j = 0; j < n; j++) {
		b = Q[j];
		if (i != j && a != - 1 && b != - 1) {
			if (a == b) c++;
			if (i - j == a - b || i - j == b - a) c++;
		}
	}
	return c;
}

int constraintsViolated(vector<int> &Q) {
	int a, b, c = 0, i, j, n;
	
	n = Q.size();
	for (i = 0; i < n; i++) {
		a = Q[i];
		for (j = 0; j < n; j++) {
			b = Q[j];
			if (i != j && a != - 1 && b != - 1) {
				if (a == b) c++;
				if (i - j == a - b || i - j == b - a) c++;
			}
		}
	}
	return c;
}

int mchcAlgorithm(int n, vector<int> &compoundLabel) {
	bool commit, firstLoop = true;
	double p = 0.1, r;
	int c, i, index, j, minConflict, v;
	int repairs = 0;
	vector<int> conflict, domain, position;

	// preprocessing
	for (i = 0; i < n; i++) {
		conflict.erase(conflict.begin(), conflict.end());
		for (j = 0; j < n; j++)
			domain.push_back(j);
		for (commit = false, j = 0; !commit && j < n; j++) {
			v = domain[rand() % domain.size()];
			vector<int>::iterator vIterator = find(domain.begin(), domain.end(), v);
			domain.erase(vIterator);
			compoundLabel[i] = v;
			c = conflicts(v, i, i, compoundLabel);
			conflict.push_back(c);
			if (c == 0) commit = true;
		}
		if (!commit) {
			minConflict = conflict[0];
			for (j = 1; j < n; j++)
				if (conflict[j] < minConflict) minConflict = conflict[j];
			position.erase(position.begin(), position.end());
			for (j = 0; j < n; j++)
				if (minConflict == conflict[j]) position.push_back(j);
			compoundLabel[i] = position[rand() % position.size()];	
		}
	}
	for (;;) {
		conflict.erase(conflict.begin(), conflict.end());
		for (i = 0, j = 0; i < n; i++) {
			c = conflicts(compoundLabel[i], i, n, compoundLabel);
			conflict.push_back(c);
			j += c;
		}
		if (firstLoop) {
			cout << "conflicts after preprocessor: " << j << endl;
			firstLoop = false;
		}
		if (j == 0) break;
		position.erase(position.begin(), position.end());
		for (i = 0; i < n; i++)
			if (conflict[i] >= 1) position.push_back(i);
		index = position[rand() % position.size()];
		r = (double) rand() / RAND_MAX;
		if (r <= p)
			compoundLabel[index] = rand() % n;
		else {
			for (i = 0; i < n; i++) {
				compoundLabel[index] = i;
				conflict[i] = conflicts(i, index, n, compoundLabel);
				repairs++;
				if (repairs == MaxRepairs) return repairs;
			}
			minConflict = conflict[0];
			for (i = 1; i < n; i++)
				if (conflict[i] < minConflict) minConflict = conflict[i];
			position.erase(position.begin(), position.end());
			for (i = 0; i < n; i++)
				if (minConflict == conflict[i]) position.push_back(i);
			compoundLabel[index] = position[rand() % position.size()];
		}
	}
	return repairs;
}

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 n = atoi(argv[1]), repairs;
	double seconds;
	clock_t time0, time1;
	vector<int> solution(n, - 1);
	srand(time(NULL));
	time0 = clock();
	repairs = mchcAlgorithm(n, solution);
	time1 = clock();
	time1 -= time0;
	seconds = (double) time1 / CLOCKS_PER_SEC;
	if (Debug) printSolution(solution);
	cout << "Repairs: " << repairs << endl;
	cout << "seconds: " << seconds << endl;
	return 0;
}