#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <boost/foreach.hpp>

using namespace std;

/* This solves the N-queen problem in C++ using recursion */

/* Sample Makefile

BOOST_ROOT=/var/tmp/omiga/boost_1_40_0
solve_n_queen: solve_n_queen.cc
	g++ -I$(BOOST_ROOT) -g -o $@ $<

*/

// return solutions which are vector of vector of ints
typedef vector<int> single_solution;
typedef vector<int> free_cols;
typedef vector<single_solution > solutions;

free_cols get_free_cols(const single_solution& s, const int n)
{
	set<int> used_cols;
	free_cols f;
	BOOST_FOREACH(int col, s)  {
		used_cols.insert(col);
	}
	for (int i=1; i<=n; i++) {
		if (used_cols.find(i) == used_cols.end()) {
			f.push_back(i);
		}
	}
	return f;
}

bool is_there_any_piece_at_row_col(const int row, const int col, const single_solution& s)
{
	int count = 1;
	BOOST_FOREACH(int p, s) {
		if ((row == count) && (col == p)) {
			return true;
		}
		++count;
	}
	return false;
}

bool can_attack(const int col, const single_solution& s, const int n)
{
	int row;
	row = s.size() + 1;
	for (int i=1; (i<=col-1) && ((row-i)>0); ++i) {
		if (is_there_any_piece_at_row_col(row-i, col-i, s)) {
			return true;
		}
	}
	for (int i=col+1; (i<=n) && (row-(i-col)>0); ++i) {
		if (is_there_any_piece_at_row_col(row-(i-col), i, s)) {
			return true;
		}
	}
	return false;
}

void print_solutions(const solutions& ss)
{
	int count =1;
	BOOST_FOREACH(single_solution s, ss)  {
		cout<<"Solution "<<count<<"\n";
		int n = s.size();
		BOOST_FOREACH(int col, s)  {
			for (int i=1; i<col; ++i) {
				cout<<"-";
			}
			cout<<"Q";
			for (int i=1; i<=n-col; ++i) {
				cout<<"-";
			}
			cout<<"\n";
		}
		count++;
	}
}

solutions resolve_queen_helper(int m, int n)
{
	solutions ss;
	if (m==1) {
		for (int i=1; i<=n; ++i) {
			single_solution s;
			s.push_back(i);
			ss.push_back(s);
		}
		return ss;
	}
	solutions partial_ss;
	partial_ss = resolve_queen_helper(m-1, n);
	BOOST_FOREACH(single_solution s, partial_ss)  {
		free_cols f;
		f = get_free_cols(s, n);
		BOOST_FOREACH(int col, f)  {
			if (!can_attack(col, s, n)) {
				single_solution ns;
				ns = s;
				ns.push_back(col);
				ss.push_back(ns);
			}
		}
	}
	return ss;
}

solutions resolve_queen(int n)
{
	return resolve_queen_helper(n, n);
}


int main(int argc, char** argv)
{
	if (argc<=1) {
		return -1;
	}
	int n = atoi(argv[1]);
	if (n<0) {
		return -1;
	}
	solutions ss;
	ss = resolve_queen(n);
	print_solutions(ss);
	return 0;
}