// 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;
}
