#include <iostream>
#include <memory.h>
#include <conio.h>
#include <stdlib.h>

using namespace std;

/*
92 solution.
* * * * * * * Q
* * * Q * * * *
Q * * * * * * *
* * Q * * * * *
* * * * * Q * *
* Q * * * * * *
* * * * * * Q *
* * * * Q * * *
*/ 

class QueenPuzzle
{
public:
	QueenPuzzle(int _n);

public:
	void printOut();
	void QueenDFS(int _n);
	int IsValidate(int _n);

private:
	int sum;
	int max;
	int * queen;
};

QueenPuzzle::QueenPuzzle(int _n)
{
	this->sum = 0;
	this->max = _n;
	this->queen = new int[this->max]();
}

void QueenPuzzle::printOut()
{
	for(int i = 0; i < this->max; i++)
	{
		for(int j = 0; j < this->max; j++)
		{
			if(j == this->queen[i])
				cout << "Q ";
			else
				cout << "* ";
		}
		cout << endl;
	}
	
	cout << endl << "Enter any key to continue, Q key exit:" << endl << endl;
	if(getch() == ‘q‘) exit(0);
}

void QueenPuzzle::QueenDFS(int _n)
{	
	if(_n == this->max)
	{
		sum++;
		cout << endl << sum << " solution." << endl;
		this->printOut();
		return;
	}

	for(int i = 0; i < this->max; i++)
	{
		this->queen[_n] = i;
		
		if(IsValidate(_n))
		{	
			this->QueenDFS(_n + 1);
		} 
	}
}

int QueenPuzzle::IsValidate(int _n)
{
	for(int i = 0; i < _n; i++)
	{
		if(this->queen[i] == this->queen[_n])
			return 0;
		
		if(abs(this->queen[i] - this->queen[_n]) == (_n - i))
			return 0;
	}
	
	return 1;
}

int main()
{
	QueenPuzzle queen(8);
	queen.QueenDFS(0);
	
	return 0;
}