Backtracking : Les cavaliers

// pb du cavalier

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>

#define DIM 8
int dx[]={1, 1, 2, 2, -1, -1, -2, -2};
int dy[]={2, -2, 1, -1, 2, -2, 1, -1};
FILE *fichier;

typedef struct {
  int maxcase;
  int nombreCasesExplorees;
  int libre[DIM][DIM];
  int chemin_x[DIM*DIM];
  int chemin_y[DIM*DIM];
} Situation;

void afficher (Situation *sit)
{
int i;
static n=0;

  fprintf (fichier,"\n----%d\n",n++);
  for (i= 0 ; i< DIM*DIM; i++)
    fprintf (fichier,"%d-%d\n",sit->chemin_x[i],sit->chemin_y[i]);
  printf ("%d\n",n);
}

inline int case_ok (Situation *sit, int x, int y)
{

  return (x>0) && (x<9) && (y<9) && (y>0) && sit->libre[x-1][y-1];
}

inline void deplace (Situation *sit, int x, int y)
{

  sit->libre[x-1][y-1] = 0;
  sit->chemin_x[sit->nombreCasesExplorees] = x;
  sit->chemin_y[sit->nombreCasesExplorees++] = y;
  if (sit->nombreCasesExplorees > sit->maxcase) {
    sit->maxcase = sit->nombreCasesExplorees;
    printf ("\a");
  }
}

inline void revient (Situation *sit)
{
  sit->nombreCasesExplorees--;
  sit->libre[sit->chemin_x[sit->nombreCasesExplorees]-1]
        [sit->chemin_y[sit->nombreCasesExplorees]-1] = 1;
  sit->chemin_x[sit->nombreCasesExplorees]=0;
  sit->chemin_y[sit->nombreCasesExplorees]=0;

}




void Cavalier (Situation *sit)
{
int x,y,xs,ys,i;

  gotoxy (1,1);
  printf ("%2.2d",sit->maxcase);
  if (sit->nombreCasesExplorees == DIM*DIM)
    afficher (sit);
  else
  {
    x = sit->chemin_x[sit->nombreCasesExplorees -1];
    y = sit->chemin_y[sit->nombreCasesExplorees -1];
    for (i=0; i<8; i++) {
      xs = x + dx[i];
      ys = y + dy[i];
      if (case_ok (sit, xs, ys)) {
        deplace (sit, xs, ys);
        Cavalier (sit);
        revient (sit);
      }
    }
  }
}

void Init (Situation *sit,int x, int y)
{
int i;
int j;

  for (i=0; i<DIM; i++)
    for (j=0; j<DIM; j++) {
      sit->libre [i][j] = 1;
      sit->chemin_x[i+j*DIM] = 0;
      sit->chemin_y[i+j*DIM] = 0;
    }
  sit->maxcase = 0;
  sit->nombreCasesExplorees = 1;
  sit->libre[x-1][y-1] = 0;
  sit->chemin_x[0] = x;
  sit->chemin_y[0]= y;
}



main ()
{
Situation situation;
int xinit,yinit;
time_t t1,t2;


  clrscr ();
  fichier = fopen ("cavalier.out", "a");
  if (fichier == NULL) {
    printf ("Erreur d'ouverture du fichier\n");
    exit (1);
  }     
  for (xinit=4; xinit > 0; xinit--)
    for (yinit=1; yinit <= xinit; yinit++) {
      Init (&situation, xinit, yinit);
      t1 = time(NULL);
      Cavalier (&situation);
      t2 = time(NULL);
      printf ("temps = %f", difftime(t2,t1));
  }
  fclose (fichier);
  return 0;
}