// ENTREE: Un couple (lettre,nombre) qui désigne la case de départ
//         de l'échiquier, avec le codage traditionnel du jeu:
//         lettre de A à H de gauche à droite pour la colonne
//         et nombre de 1 à 8 de bas en haut pour la ligne
//         
// SORTIE: Un chemin hamiltonien de l'échiquier (passe par 
//         chaque case une fois exactement) en partant de (l,c)
// NB. compilation:
//     gcc -Wall -o cavaliers cavaliers.c -g
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <ctype.h>
#include <string.h>

#define abs(a) ((a) < 0 ? (-a) : (a))


// Tableau des nombres de cases accessibles.
// Les valeurs sont négatives pour laisser la possibilité
// de ranger le déplacement du cavalier avec les
// valeurs positives pour décrire le parcours.
int ECHIQUIER[8][8] =
  {{-2,-3,-4,-4,-4,-4,-3,-2},
   {-3,-4,-6,-6,-6,-6,-4,-3},
   {-4,-6,-8,-8,-8,-8,-6,-4},
   {-4,-6,-8,-8,-8,-8,-6,-4},
   {-4,-6,-8,-8,-8,-8,-6,-4},
   {-4,-6,-8,-8,-8,-8,-6,-4},
   {-3,-4,-6,-6,-6,-6,-4,-3},
   {-2,-3,-4,-4,-4,-4,-3,-2}};

// Tableau contenant les 8 couples de décalages (ligne,colonne)
// correspondant aux 8 sauts possibles du cavalier dans l'ordre
// des aiguilles d'une montre autour de sa position. Certains 
// déplacements peuvent sortir de l'échiquier selon la position
// du cavalier mais ceci est testé par la fonction IsMvtOk
int MVTS[8][2] =
  {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
 
typedef unsigned char uchar;

// Le tableau Sauts contient les indices [0..7] des mouvements
// possibles triés dans l'ordre croissant des valeurs pour le 
// cavalier à un instant donné. Par exemple si
// Avisiter=[3,2,0,1,....], le premier déplacement est
// MVTS[3], soit la case située 2 lignes plus bas et 
// 1 colonne à droite. C'est la valeur de retour de la fonction
// OuSauter qui fixe le nombre effectif de cases accessibles.

uchar nbcases;
uchar * Sauts;
uchar n;
ulong nbsols = 0;


// Affiche l'échiquier en utilisant les ressources X11 pour gérer
// les couleurs du terminal.
void AfficherEchiquier(uchar l, uchar c,ulong nbsols)
{
  uchar i,j;
  short pos;
  const char BLANC[29] = "\033[0;30m\033[47m%2hu\033[0m";
  const char NOIR[29] = "\033[1;37m\033[40m%2hu\033[0m";
  const char BLANCV[27] = "\033[0;30m\033[47m%s\033[0m";
  const char NOIRV[27] = "\033[1;37m\033[40m%s\033[0m";
  const char VIDE[3] = "  \0";
  char couleur[29];

  if (nbsols)
    printf("\nSolution #%lu:\t",nbsols);
  printf("\n    A B C D E F G H\n");
  for (i = 0; i < 8; i++)
    {
      printf("%2hu ",8 - i);
      for (j = 0; j < 8; j++) 
	{
	  pos = ECHIQUIER[i][j];
	  if (pos > 0)
	    {
	    if ((j+i) % 2)
	      strcpy(couleur,NOIR);
	    else
	      strcpy(couleur,BLANC);    
	    printf(couleur,ECHIQUIER[i][j]);
	    }
	  else
	    {
	    if ((j+i) % 2)
	      strcpy(couleur,NOIRV);
	    else
	      strcpy(couleur,BLANCV); 
	    printf(couleur,VIDE);
	    }
	}
      printf("\n");
    }
  printf("    A B C D E F G H\n");
  printf("\n(Tapez ENTREE pour continuer)");
  getchar();
}
 	
// Teste si le mouvement numéro num laisse le cavalier 
// dans l'échiquier en partant de la case (l,c).
uchar IsMvtOk(short l, short c, uchar num)
{
  return (l + MVTS[num][0] >= 0) && (l + MVTS[num][0] < 8) && 
         (c + MVTS[num][1] >= 0) && (c + MVTS[num][1] < 8);
}


// Détermine les numéros de mouvements correspondant aux 
// cases accessibles par le cavalier en partant de (l,c) 
// Ces numeros sont ranges dans le tableau Sauts et sont
// triées dans l'ordre croissant du nombre d'accès possibles.
uchar * OuSauter(short l, short c, uchar *nbcases)
{
  int i,j;
  uchar min;
  uchar liste[8];  
  uchar * Sauts;
  
  // détermine le nombre de cases accessibles en partant de (l,c)
  // et le tableau de 8 booleens "liste" contient les indices des 
  // mouvements autorisés.
  *nbcases = 0;
  for (i = 0; i < 8; i++)
    {
      liste[i] = IsMvtOk(l,c,i) && (ECHIQUIER[l+MVTS[i][0]][c+MVTS[i][1]] < 0);
      if (liste[i])
	(*nbcases)++;
    }

  Sauts = (uchar *) calloc(*nbcases,sizeof(uchar));
  // Trie les cases dans l'ordre croissant des valeurs.
  for (i = 0; i < *nbcases; i++)
    {
      min = 16;
      for (j = 0; j < 8; j++)
	if ((liste[j]) && (abs(ECHIQUIER[l+MVTS[j][0]][c+MVTS[j][1]])< min))
	  {
	    min = abs(ECHIQUIER[l+MVTS[j][0]][c+MVTS[j][1]]);
	    Sauts[i] = j;
	  }
      liste[Sauts[i]] = 0;
    }  
  return Sauts;			   
}

// Backtracking du cavalier
void Cavalier(uchar l, uchar c, uchar n)
{
  short val;
  uchar *Sauts;
  uchar nb,cc,nbcases;

  if (n > 64)
    AfficherEchiquier(l,c,++nbsols);
  else
    {
      Sauts = OuSauter(l, c, &nbcases);
      AfficherEchiquier(l,c,0);
      for (nb = 0; nb < nbcases; nb++)
	{	     
	  val = ECHIQUIER[l + MVTS[Sauts[nb]][0]][c + MVTS[Sauts[nb]][1]];
	  for (cc = 0; cc < nbcases; cc++)
	    ECHIQUIER[l + MVTS[Sauts[cc]][0]][c + MVTS[Sauts[cc]][1]]++;
	  ECHIQUIER[l + MVTS[Sauts[nb]][0]][c + MVTS[Sauts[nb]][1]] = n;

	  Cavalier(l + MVTS[Sauts[nb]][0],c + MVTS[Sauts[nb]][1],n + 1);

	  for (cc = 0; cc < nbcases; cc++)
	    ECHIQUIER[l + MVTS[Sauts[cc]][0]][c + MVTS[Sauts[cc]][1]]--;
	  ECHIQUIER[l + MVTS[Sauts[nb]][0]][c + MVTS[Sauts[nb]][1]] = val;    	
	}
      free(Sauts);
    }		   
}

int main(int argc, char * argv[])
{

  uchar l;
  uchar c;

  if ((argc < 2) || (strlen(argv[1]) < 2))
    { 
      printf("Syntaxe: %s [A-H][1-8]\n\n",argv[0]);
      return 1;
    }
  
  l = 8 - argv[1][1] + '0';
  if (argv[1][0] > 'a')
    c = argv[1][0] - 'a';
  else 
    c = argv[1][0] - 'A';
  ECHIQUIER[l][c] = 1;  
  Cavalier(l,c,2);
  return 0;
}