/************************************************/
/*						*/
/*	TROILO Fabrice : Huit reines		*/
/*       Modifie par PL                         */
/*	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
	{
		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, int from )
{       int j ;
        if ( num >= n )  {
          printf("\n%d [shape = circle, color = red ];", from); 
          printf("\n%d -> sol", from); 
          cpt++;
        }
        else
          for(j = 0; j < n; j++) 
	     {
	 	       noeud++;
		       printf("\n%d -> %d", from, noeud);   
		       pos[num] = j;    
		       if (libre(num,j,pos,n))   
		          backtrack( num+1 , n, pos,   noeud);		
		      
	      }
		
}


int main (int argc, char* argv[])
{
        int n, *pos;
	n = 4;
	pos=(int*)malloc(sizeof (int)*n);
	
	printf("\ndigraph g {\n\t graph [\n  ];\n size=\"6,8\";");
        printf("\nnode [\n\t fontsize = \"32\"\n];");
	printf("\nedge [ ];");
      	backtrack(0, n, pos, 0  );
	free(pos);
	printf("\n}");
	return 0;
}