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;

}