//	chess problem
//	programmer :
//	seyed mohammmad hoseini		871412306		hardware
//______________________________________________________

#include <iostream>
#include <time.h>
#include <conio.h>
using namespace std;

//prototype
void mark_location(int x, int y);
void start_new();
void clear_t_i();

//global (public)
bool m_location  [9][9] = {0};	// marked locations
bool q_location  [9][9] = {0};	// queen location
int t_i[9]={0};					// tested i

int main()
{
	cout << "Project #1 : chess problem\nprogrammer : \nseyed mohammad hoseini	871412306	hardware\n________________________________________________\n";

	int i,ii,j,k;
	int rnd_i;
	char generate_again='y', ichar;
	srand((unsigned)time(0/*Null*/));
	
	while (generate_again == 'y' || generate_again == 'Y')
	{
		cout << "\n\n";

generate_again:
		start_new();

		for (k = 1; k <= 8; k++) //----------------------------------------------- loop for each queen
		{
			j = k;	
			while (true)
			{
				rnd_i = ((int)((double)rand()/(RAND_MAX+1) * 8)) + 1;	//-------- random i  for each line
				if (m_location [rnd_i][j] == 0)	//-------------------------------- check the location to find out a threat from a queen
				{	
					q_location [rnd_i][j] = 1;	//-------------------------------- place the queen
					mark_location(rnd_i,j);		//-------------------------------- mark the locations that the queen can cover
					break;
				}
				t_i [rnd_i] = 1;
				for (ii = 1; ii <= 8; ii++)
				{
					if (t_i [ii] == 0)
						break;
					if (ii == 8)	//-------------------------------------------- impossible to place 8 queen
					{
						goto generate_again;
					}
				}
			}	
			clear_t_i();
		}

		for (j = 8; j >= 1; j--)	//-------------------------------------------- draw chess board
		{
			cout << " " << j << "   ";
			for (i = 1; i <= 8; i++)
			{
				if (q_location [i][j] == 1)
					cout << "*" << " ";	//---------------------------------------- queen location
				else
					cout << "O" << " ";	//---------------------------------------- blank location
			}
			cout << "\n";
		}
		cout << "\n     ";
		for (i = 65; i <= 72; i++)
		{
			ichar = i;
			cout << ichar << " ";
		}

		cout << "\n\ngenerate again ? (y/n) ";
		generate_again = getch();
	}
	return 0;
}

void mark_location(int x, int y)
{
	int i,j;
	for (i = 1; i <= 8; i++)
		m_location [i][y] = 1;
	for (j = 1; j <= 8; j++)
		m_location [x][j] = 1;
	
	i = x; j = y;
	while ((i-1)>=1 && (j-1)>=1)
	{
		i -= 1; j -= 1;
		m_location [i][j] = 1;
	}
	i = x; j = y;
	while ((i+1)<=8 && (j+1)<=8)
	{
		i += 1; j += 1;
		m_location [i][j] = 1;
	}
	i = x; j = y;
	while ((i+1)<=8 && (j-1)>=1)
	{
		i += 1; j -= 1;
		m_location [i][j] = 1;
	}
	i = x; j = y;
	while ((i-1)>=1 && (j+1)<=8)
	{
		i -= 1; j += 1;
		m_location [i][j] = 1;
	}
}

void start_new()
{
	int i,j;
	for (i = 1; i <= 8; i++)
	{
		for (j = 1; j <= 8; j++)
		{
			m_location [i][j] = 0;
			q_location [i][j] = 0;
		}
		t_i [i] = 0;
	}
}

void clear_t_i()
{
	for (int i = 1; i <= 8; i++)
		t_i [i] = 0;
}