//This program places N queens on an NxN checkered board such that
//no two queens conflict each other according to the rules of chess

#include<fstream.h>
#include<time.h>

const int MAX = 50;

void main()
{
	int row, col;
	int board[MAX];
	unsigned long solutions;
	bool flag, cols[MAX], diags[2*MAX], adiags[2*MAX];
	
	clock_t start, finish;
//	ofstream fout("queens.txt");

	for(int n=1;n<24;n++)
	{
		/**** Initializing the state indicator arrays *****/
		for(row=0;row<n;row++)
		{
			board[row] = -1;
			cols[row] = false;
		}
		for(row=0;row<2*n;row++)
		{
			diags[row]=false;
			adiags[row]=false;
		}
		/**************************************************/

		/* Initializing row, column and solution counters */
		row=0;
		col=-1;
		solutions=0;
		/**************************************************/
		start = clock();
		/****************** The Processing ******************/
		/******************* The Search *******************/
		while(row > -1)
		{
			flag = true;
			for(col++;col<n;col++)
			{
				if(!cols[col] && !adiags[row+col] && !diags[n+row-col])
				{
					board[row]=col;
					diags[n+row-col]=true;
					adiags[row+col]=true;
					cols[col]=true;
					flag = false;
					break;
				}
			}
			if(flag)
			{
				if(--row > -1)		//backtrack
				{
					col=board[row];
					board[row]=-1;
					diags[n+row-col] = false;
					adiags[row+col] = false;
					cols[col] = false;
				}
/*				if(!(n&1) && !row && col==(n>>1)-1)
				{
					solutions<<=1;
					break;
				}*/
			}
			else
			{
				++row;
				col=-1;
			}
			if(row == n)
			{
				solutions++;
			}
		}
		/**************************************************/
		/****************************************************/
		finish = clock();
		cout<<n<<"\t"<<solutions<<"\t\t"<<(double)(finish-start)/CLOCKS_PER_SEC<<endl;
	}
//	fout.close();
	cout<<"Done"<<endl;
}