N-Queens problem implemented using genetic algorithm. Support up to 255 queens. Algorithm will converge in a few minutes at most.

nqueens-genetic-algorithm.cpp

#include <bits/stdc++.h>

using namespace std;

bool CONVERGED = false;
int const MUTATION_STEP = 1e2;
int const ROULETTE_SIZE = 1e3;
int const MAX_INTERATION = 1e5;

void init(vector<string>& status)
{
	int n = status.size();
	for (auto &itr:status) {
		string s;
		for (auto i = 0; i < n; ++i)
			s += (unsigned char)(rand()%n);
		itr = s;
	}
	// cout<<"init() succeeded"<<endl;
}

vector<double> fitness(vector<string> const& status)
{
	int n = status.size();
	vector<double> f(n);
	int total = 0;
	for (auto i = 0; i < n; ++i) {
		vector<int> c(n, -1), l(2*n, -1), r(2*n, -1);
		for (auto j = 0; j < n; ++j) {
			int column = (unsigned char)status.at(i).at(j);
			// cout<<j<<"  "<<status.at(i).at(j)<<"  "<<column<<"  "<<column + j<<"  "<<column - j + n<<endl;
			++c.at(column);
			++l.at(column + j);
			++r.at(column - j + n);
		}
		for (auto const&j:c)
			f.at(i) += (j > 0)?j:0;
		for (auto const&j:l)
			f.at(i) += (j > 0)?j:0;
		for (auto const&j:r)
			f.at(i) += (j > 0)?j:0;
		total += f.at(i);
	}
	// for (auto &itr:f)
	// 	itr /= total;
	// cout<<"fitness() succeeded"<<endl;
	return f;
}

void print(vector<string> const& status)
{
	int n = status.size();
	for (auto &itr:status) {
		for (auto i = 0; i < n; ++i){
			string s(n, '+');
			s.at((unsigned char)itr.at((unsigned char)i)) = 'Q';
			cout<<s<<endl;
		}
		cout<<endl;
	}
	// cout<<"print() succeeded"<<endl;
}

void printcase(string str)
{
	int n = str.size();
	for (auto i = 0; i < n; ++i) {
		string s(n, '+');
		s.at((unsigned char)str.at((unsigned char)i)) = 'Q';
		cout<<s<<endl;
	}
	// cout<<"printcase() succeeded"<<endl;
}

void select(vector<string>& status)
{
	int n = status.size();
	vector<pair<string, double>> cmpvec;
	auto fn = fitness(status);
	for (int i = 0; i < n; ++i)
		cmpvec.push_back(pair<string, double>(status.at(i), fn.at(i)));
	sort(cmpvec.begin(), cmpvec.end(),
		[](pair<string, double> const& l, pair<string, double> const& r){
			return l.second < r.second;
	});
	for (int i = 0; i < n; ++i) {
		status.at(i) = cmpvec.at(i).first;
		fn.at(i) = cmpvec.at(i).second;
	}
	if (!*fn.begin()) {
		CONVERGED = true;
		return;
	}
	// int tc = 0;
	// for (auto const &itr:fn)
	// 	tc += itr;
	vector<int> roulette(ROULETTE_SIZE);
	auto itr = fn.begin();
	for (int i = 0, t = 0; i < ROULETTE_SIZE; ++i) {
		roulette.at(i) = itr - fn.begin();
		++t;
		if (t > ROULETTE_SIZE / *itr) {
			t = 0;
			++itr;
		}
	}
	vector<string> parent(n);
	for (auto &itr:parent)
		itr = *(status.begin() + roulette.at(rand()%ROULETTE_SIZE));
	status = parent;
	// cout<<"select() succeeded"<<endl;
}

void crossover(vector<string>& status)
{
	int n = status.size();
	random_shuffle(status.begin(), status.end());
	for (int i = 1, p; i < n; i+=2) {
		p = rand()%n;
		string s0 = status.at(i-1).substr(0, p) + status.at(i).substr(p);
		string s1 = status.at(i).substr(0, p) + status.at(i-1).substr(p);
		status.at(i-1) = s0;
		status.at(i) = s1;
	}
	// cout<<"crossover() succeeded"<<endl;
}

void mutate(vector<string>& status)
{
	int n = status.size();
	for (auto &itr:status)
		for (int i = 0; i < n; ++i) 
			if (rand()%MUTATION_STEP==1)
				itr.at(i) = (unsigned char)(rand()%n);
	// cout<<"mutate() succeeded"<<endl;
};

int ga(int n)
{
	srand(time(nullptr));
	vector<string> status(n);
	init(status);
	clock_t t = clock();
	select(status);
	int i;
	for (i = 0; i < MAX_INTERATION && !CONVERGED; ++i) {
		crossover(status);
		mutate(status);
		select(status);
	}
	t = clock() - t;
	if (!CONVERGED)
		return -1;
	cout<<"Converged at iteration "<<i<<endl;
	cout<<t/CLOCKS_PER_SEC<<" seconds has passed"<<endl;
	printcase(status.at(0));
	return 0;
}

int main(int ac, char **av)
{
	// n    itr  time
	// 255 18307 183
	// 255  6123  60
	// 255  8799  87
	// 255 12045 121
	int n = 255;
	ga(n);
}