#include <iostream>
#include <cstdlib>
using namespace std;

typedef bool* TPBool;

class TBoard {
	private:
		TPBool *board;
		int     size;
	public:
		TBoard(int N);
      TBoard(const TBoard &brd);
		~TBoard();
		void print();
		void set(int i, int j) { board[i][j] = true; };
		void unset(int i, int j) { board[i][j] = false; };
		int getsize() { return size; };
		void clear();
		bool taken(int i, int j) const { return board[i][j]; };
};

TBoard::TBoard(int N)
{
	int i, j;
	size = N;
	board = new TPBool[N];
	for(i=0;i<N;i++){
		board[i] = new bool[N];
		for(j=0;j<N;j++) board[i][j] = false;
	}
}

TBoard::TBoard(const TBoard &brd)
{
	int i, j;
	size = brd.size;
	board = new TPBool[size];
	for(i=0;i<size;i++){
		board[i] = new bool[size];
		for(j=0;j<size;j++) board[i][j] = brd.taken(i, j);
	}
}


TBoard::~TBoard()
{
	for(int i=0;i<size;i++) delete board[i];
	delete board;
}

void TBoard::print()
{
	int i, j;
	cout<<endl;
	for(j=0;j<size;j++) cout<<"----";
	cout<<endl;
	for(i=0;i<size;i++){
		for(j=0;j<size;j++) cout<<(board[i][j]?"| Q ":"| . ");
		cout<<"|"<<endl;
		for(j=0;j<size;j++) cout<<"----";
		cout<<"-"<<endl;
	}
}

void TBoard::clear()
{
	int i, j;
	for(i=0;i<size;i++)
		for(j=0;j<size;j++) board[i][j] = false;
}


// -------------------------------------------------------------------------
bool set_next_queen(TBoard &board, int qnum, int Queens[])
{
	int N = board.getsize(), i, j, k;
	if( qnum == N ) return true;

	for(i=0;i<N;i++){
	   TBoard brd(board);
 		if( ! board.taken(qnum, i) ){ // find the next available position in the row #qnum
			brd.set(qnum,i); // put a queen here
			//  and mark all the fields it attacks as taken
			for(j=0;j<N;j++){  
				brd.set(qnum, j);
				brd.set(j, i);
			}
			for(j=1; i-j>=0 && qnum-j>=0; j++ ) brd.set(qnum-j, i-j);
			for(j=1; i+j<N && qnum+j<N; j++ ) brd.set(qnum+j, i+j);
			for(j=1; i+j<N && qnum-j>=0; j++ ) brd.set(qnum-j, i+j);
			for(j=1; i-j>=0 && qnum+j<N; j++ ) brd.set(qnum+j, i-j);
			if( set_next_queen(brd, qnum+1, Queens) ){
				Queens[qnum] = i;
				return true;
			}
		}
	}
	return false;
}

void set_queens(int N)
{
	int *Queens = new int[N];
	TBoard board(N);

	if( set_next_queen(board, 0, Queens) ){
		for(int i=0;i<N;i++) board.set(i, Queens[i]);
		board.print();
	}
	else
		cout<<"Cannot perform the task.\n";
}

// -------------------------------------------------------------------------

void main(int argc, char *argv[])
{
	int N = (argc>1 && (N=atoi(argv[1])) ) ?  N : 8;

	cout<<"Board size: "<<N<<"x"<<N<<endl;
	set_queens(N);
}