/*----------------------------------------------------------*/
/*                                                          */
/*         AUTHOR : Eric VIOLARD                            */
/*         E-MAIL : violard@icps.u-strasbg.fr               */
/*         ORGANISM : Université Louis Pasteur (Strasbourg) */
/*         CREATION : 02/01/03                              */
/*                                                          */
/* ---------------------------------------------------------*/
  
/*  

    Programme qui résoud le problème des 8 reines.

*/

/* --- définition du type des booléens */

typedef int bool;

#define true 1
#define false 0

/* ---- */

/* contenu des cases de l'échiquier : */
#define reine 1 /* une reine */
#define vide 0  /* case vide */


bool en_prise(int x,int y,int echiquier[8][8])
     /* fonction qui détermine si une reine placée 
      sur la case de coordonnées (x,y)
      est en prise ou non */
     /* pré-conditions: 0<=x<8 et 0<=y<8 */
{
  int i,j; /* coordonnées d'une case de l'échiquier */
 
  bool r=false; /* résultat : on suppose qu'initialement la reine n'est pas en prise */

  for(i=0;i<8;i++) /* on parcours toutes les cases */
  for(j=0;j<8;j++)
    /* la reine est en prise si une reine se trouve sur la case (i,j)
      et cette case se trouve sur la même rangée, sur la même colonne
      ou sur la même diagonale que la case (x,y) */
     r = r || (echiquier[i][j]==reine && ((i==x) || (j==y) || (i+j)==(x+y) || (i-j)==(x-y)));
							 
  return r;
}


bool placer_reines(int n,int echiquier[8][8])     
    /* fonction qui place n reines 
      sur l'échiquier (par effet de bord) en faisant attention
      qu'aucune ne soit en prise 
      le résultat est vrai si on a trouvé 
      une place pour chaque reine faux sinon
   /* pré-conditions: n>=0 */
     /* post-condition: les reines sont placées sur l'échiquier */
{
  bool fini=false; /* résultat :
 initialement on n'a pas encore trouvé la place de chaque reine */ 

  if(n>0) /* si le nombre de reines à placer est non nul */
    {
      int i,j; /* coordonnées d'une case de l'échiquier */
      
      for(i=0;i<8;i++) /* on parcours toutes les cases (i,j) */
      for(j=0;j<8;j++)
        if(!fini && !en_prise(i,j,echiquier)) 
          /* si une reine placée sur la case (i,j) n'est pas en prise */
          {
	    echiquier[i][j]=reine; /* on place une reine */
            fini=placer_reines(n-1,echiquier); /* et on tente de placer les n-1 reines restantes */ 
            if(!fini) echiquier[i][j]=vide; /* si on échoue, on ote la reine et on essaie une autre case */ 
          }
    }
  else /* si le nombre de reines à placer est nul */
    fini=true;  /* on a réussi */

  return fini;
}

void affiche_echiquier(int echiquier[8][8])
     /* affiche l'échiquier et l'emplacement des reines */
{
  int i,j; /* coordonnées d'une case de l'échiquier */

  printf("  1 2 3 4 5 6 7 8\n"); /* affichage des numéro de colonne */

  for(i=0;i<8;i++) /* on parcours toutes les lignes */
    {
    printf("%d ",i+1); /* affichage du numéro de la rangée */
    for(j=0;j<8;j++) /* on parcours toutes les colonnes */

      if(echiquier[i][j]==vide) /* si la case est vide, on affiche un espace */
        printf("  ");
      else /* si la case est pleine, on affiche une étoile */
        printf("* "); 

    printf("\n");
    }
}

main()
{
  int echiquier[8][8]; /* l'échiquier */
   int i,j; /* coordonnées d'une case de l'échiquier */

   /* initialement l'échiquier est vide */
   for(i=0;i<8;i++)
   for(j=0;j<8;j++)
     echiquier[i][j]=vide;

   /* on tente de placer 8 reines et on affiche l'échiquier si on a réussi */
   if(placer_reines(8,echiquier))
     affiche_echiquier(echiquier);
}