//  Name      :  Matthew E. Massey
//  order n! N-queens solution finder.

#include <ctime>
#include <iostream>    // Provides cout and cin


void printBoard(char queenList[], char size);

int main( )
{
	const char n=8;
	char m=0;
	std::cout << "Solving for n= "<< (int)n << std::endl;
	char nextY=0, currentY=0;
	bool allFound=false, conflict;

	char* a;
	a = new char[n]; // a[x]=y
	for (char i = 0; i < n; ++i) // no queens on board
		a[i] = -1;

	bool * y;
	y = new bool [n]; // list of occupied y values, columns
	for (char i = 0; i < n; ++i) // all rows open
		y[i] = false;

	bool* posDiag;
	posDiag = new bool[2*n+1]; // list of occupied positive diagonals
	for (char i = 0; i < 2*n+1; ++i) // all positive diagonals open
		posDiag[i] = false;

	bool* negDiag;
	negDiag = new bool[2*n+1]; // list of occupied negative diagonals
	for (char i = 0; i < 2*n+1; ++i) // all negative diagonals open
		negDiag[i] = false;

	long unsigned int solutions=0, tS1eax=0, tS1edx=0, tS2eax=0, tS2edx=0, secondCount=0;
	unsigned long long bigTime1=0, bigTime2=0;
	secondCount = time(NULL);
	_asm
	{
		rdtsc; // get 64bit timestamp from intel 586 cpu
		mov	tS1eax,eax;
		mov	tS1edx,edx;
	}

	while(allFound == false) // keep looping until all solutions found
	{
		nextY = a[m]; // load queen y value for current x cursor 'm'
		if (nextY == -1) ++nextY; // if the queen is -1 (off the board) put it on the board

		do
		{
			//conflict=0; // assume no conflicts yet
			while(y[nextY] == true) ++nextY;  // keep moving queen up until open row is found
			if (nextY < n) // if queen is still on board
			{
				if(negDiag[m+nextY]==true) // check for negative diagonal conflicts
				{
					conflict=true;
					++nextY;
				}
				else if(posDiag[m-nextY+(n-1)]==true)// check for positive diagonal conflicts
				{
					conflict=true;
					++nextY;
				}
				else conflict=false;
			}
			else conflict =false;
		} while(conflict == true);

		currentY = a[m];
		if(nextY > (n-1)) // If queen was moved off board, no safe spot was found
		{
			if (m == 0) allFound=true; // if the first queen was moved off, we're done
			else // otherwise delete current position and go back a column
			{
				if(currentY != -1) 
				{
					y[currentY]=false;
					negDiag[m+currentY]=false;
					posDiag[m-currentY+(n-1)]=false;
				}
				a[m]=-1;
				--m;
			}
		}
		else // a safe position was found, store it and move to next colum
		{
			if(currentY != -1)
			{
				y[currentY]=false;
				negDiag[m+currentY]=false;
				posDiag[m-currentY+(n-1)]=false;
			}
			y[nextY]=true;
			negDiag[m+nextY]=true;
			posDiag[m-nextY+(n-1)]=true;
			a[m]=nextY;
			if(m == (n-1))	++solutions; // if we're on lost column we have found a solution
			else ++m;// otherwise move to next column
		}
	}
	_asm
	{
		rdtsc; // get 64bit timestamp from intel 586 cpu
		mov	tS2eax,eax;
		mov	tS2edx,edx;
	}
	bigTime1=tS1edx*4294967296+tS1eax;
	bigTime2=tS2edx*4294967296+tS2eax;
	std::cout << "Elasped clock cycles: " << bigTime2-bigTime1 << std::endl;
	secondCount = time(NULL)-secondCount;
	std::cout << secondCount << " seconds." << std::endl;
	std::cout << solutions << " solutions." << std::endl;
	delete [] a;
	delete [] y;
	delete [] posDiag;
	delete [] negDiag;
	return 0;
}

void printBoard(char queenList[], char size)
{

	for(char i=size-1; i>=0; i--) // y
	{
		for(char j=0; j<size; j++) // x
		{
			if(queenList[j]!=i)
				std::cout << "- ";
			else
				std::cout << "Q ";
		}
		std::cout << std::endl;
	}
	std::cout << std::endl;
}