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

}