/************************************************/
/*						*/
/*	TROILO Fabrice : Huit reines		*/
/*	date : 24/10/07				*/
/************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <ctype.h>
#include <string.h>

int cpt=0;
int noeud=0;

int libre(int r, int c, int* pos, int n)
{
	int i,j=0;
	for(i=(r-1);i>=0;i--)//colonne
	{
		noeud++;if(pos[i]==c)
		{
			return 0;	
		}
	}
	for(i=(r-1),j=(c+1);(j<n) && (i>=0);i--,j++)//diag droite
	{
		if(pos[i]==j)
		{
			return 0;
		}
	}
	for(i=(r-1),j=(c-1);(j>=0) && (i>=0);i--,j--)//diag gauche
	{
		if(pos[i]==j)
		{
			return 0;
		}
	}
	return 1;
}

void placer (int num, int j,int* pos)
{
	pos[num]=j;	
}

void backtrack(int num,int n,int *pos)
{
	noeud++;
	int j;
	if(num>=n)
	{
		cpt++;
	}
	else
	{
		for(j=0;j<n;j++)
		{
		
			if (libre(num,j,pos,n))
			{
				pos[num]=j;
				backtrack(num+1,n,pos);	
			}
		}
	}
}

int main (int argc, char* argv[])
{
	int n, *pos;
	n=atoi(argv[1]);
	pos=(int*)malloc(sizeof (int)*n);
	backtrack(0,n,pos);
	free(pos);
	printf ("\nNb solutions :%d\nNb noeuds :%d\n",cpt,noeud);//cpt = nbre de solutions, variable globale
	return 0;
}