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

    Programme qui tente de résoudre le problème du cavalier
    en utilisant uniquement la récursivité

    (le temps mis par ce programme pour résoudre le problème
    du parcours de toutes les cases est prohibitif, il faut
    utiliser une "heuristique" comme par exemple, déplacer
    le cavalier sur la case à partir de laquelle il lui reste
    le moins de cases)  

*/

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

typedef int bool;

#define true 1
#define false 0

/* --- */


#define vide -1 /* valeur d'une case vide */


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

  printf("   1  2  3  4  5  6  7  8\n"); 
  for(i=0;i<8;i++) /* on parcours toutes les lignes */
    {
    printf("%d ",i+1);
    for(j=0;j<8;j++) /* on parcours toutes les colonnes */
      if(echiquier[i][j]==vide) 
        printf("   "); /* si la case est vide, on affiche un espace */ 
      else 
        printf("%2d ",echiquier[i][j]); /* sinon, on affiche le nombre de déplacements pour atteindre la case */
    printf("\n");
    }
}


bool deplace_cavalier(int n,int echiquier[8][8],int x,int y)
    /* fonction qui effecture n déplacements du cavalier sur l'échiquier
      à partir de la case de coordonnées (x,y) en faisant attention à ce que 
      le cavalier ne se déplace pas sur une case où il est déja passé
      le résultat est vrai si on a réussi a effectué ces déplacements et faux sinon */
   /* pré-conditions: n>=0 */
    /* post-condition: chaque case de l'échiquier soit n'a pas encore
       été visitée (elle est vide), soit a déja été visitée et dans ce cas 
       elle contient le nombre de déplacements qu'a effectué 
       le cavalier pour atteindre la case (ce qui permet de retrouver le chemin du cavalier) */
{
  int dep_x[8] = { 1, -1, -1, 2, 2, -2,-2 }; /* les 8 déplacements possibles en x et en y */
  int dep_y[8] = { -2, 2, -2, 1, -1, 1,-1 };
  int i; /* pour parcourir les 8 cases possibles du cavalier */

  bool fini=false; /* résultat (initialement faux) */

  if(n>0) /* si n est non nul */

    for(i=0;i<8 && !fini;i++) /* on parcours les 8 cases possibles */
      {
      int x_ = x+dep_x[i];
      int y_ = y+dep_y[i];

      if(0<=x_ && x_<8 && 0<=y_ && y_<8 && echiquier[x_][y_]==vide) /* si la case est vide */
        {
	echiquier[x_][y_]=n; /* on déplace le cavalier */
        fini=deplace_cavalier(n-1,echiquier,x_,y_); /* reste n-1 déplacement à effectuer */
        if(!fini) echiquier[x_][y_]=vide; /* si on échoue, on ote le cavalier et on essaie une autre case */ 
        }        
      }

  else /* si il ne reste aucun déplacement à faire */

    fini=true; /* on a réussi */

  return fini;
}



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;

 
   echiquier[0][0]=51; /* on place le cavalier sur la case (0,0) */ 
   if(deplace_cavalier(50,echiquier,0,0)) /* on tente d'effectuer 50 déplacements */
     affiche_echiquier(echiquier); /* si on réussi, on affiche l'échiquier */
}