#include <stdio.h>
#include <stdlib.h>
#define N 4 /* Taille du cube */
#define Taille N*N*N /* Nombre de petits cubes */
//#define Nb_sit 1 /* Nombre de situations de départ : pour 2, une seule */
#define Nb_sit 6 /* Nombre de situations de départ : pour 3 et 4, il y en a 3 */
/* Pour le cube d'ismael : 6 */
#define D 3 /* On travaille en 3 dimensions */
/* NB : pas adapté à faire autre chose que 3 dimensions !
Ou en tous cas pas sans un peu de boulot */
#define STOP 0 /* STOP : est-ce qu'on s'arrête après avoir trouvé une solution.
Quand STOP vaut 0, il teste tout ! */
#define V 0 /* Mode verbeux (attention les zyeux) */
/* Pour changer la taille : changer N, changer la séquence des longueurs (en dessous),
et changer l'initialisation (voir le main) */
// nombre de situations testées
static int nb_tests = 0 ;
/* La séquence des longueurs : spécifique au cube */
/* N = 3 */
//int sequence[Taille] =
//{ 3, 0, 0, 1, 1, 2, 0, 1, 2, 0, 1, 1, 2, 0, 2, 0, 1, 1, 1, 2, 0, 2, 0, 2, 0, 2, 0 } ;
/* N = 2 */
/*int sequence[N*N*N] =
{ 2, 0, 1, 1, 1, 1, 1, 1} ;
*/
/* N = 4 */
/*
int sequence[Taille] =
{
4, 0, 0, 0, 1, 1, 3, 0, 0, 3, 0, 0, 1, 2, 0, 2, 0, 1, 1, 1, 1, 3, 0, 0, 3, 0, 0, 1, 1, 1, 2, 0,
1, 3, 0, 0, 1, 3, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 2, 0, 1, 3, 0, 0, 1, 1, 1, 1, 1, 2, 0
} ;
*/
// Cube d'Ismael
int sequence[Taille] =
{
3, 0, 0, 1, 2, 0, 1, 1, 3, 0, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1,
2, 0, 2, 0, 1, 1, 1, 1, 1, 2, 0, 3, 0, 0, 1, 1, 1, 3, 0, 0, 1, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
3, 0, 0, 1
} ;
/* La liste des orientations possibles */
int orientations[2*D][D] =
{
{0, 0, 1}, {0, 0, -1}, { 0, 1, 0}, {0, -1, 0},
{1, 0, 0}, {-1, 0, 0}
} ;
/*** Structure ***/
typedef struct Situation {
int Cube[N][N][N] ; /* Le cube, rempli d'entiers */
int X ; /* Coord du dernier cube qu'on y a mis */
int Y ;
int Z ;
int Orientation[D] ; /* L'orientation du dernier cube : par ex (0, +1, 0) */
int Num ; /* Le numéro du dernier cube qu'on y a mis */
} t_sit ;
int taillesituation=sizeof(struct Situation) ;
/*********************************************/
/*** Affichage ***/
/* Affichage du cube */
void affiche_cube(int (*cube)[N][N][N])
{
int i, j, k ;
for(k=0;k<N; k++)
{
printf("*** z=%i :\n", k) ;
for(j=0;j<N;j++)
{
for(i=0;i<N; i++)
printf("%i\t", (*cube)[i][j][k]) ;
printf("\n") ;
}
//printf("\n") ;
}
}
/* Affichage d'une situation */
void affiche_situation(t_sit* situation)
{
printf("-> Cube : \n") ;
affiche_cube(&situation->Cube) ;
printf("-> Coordonnées du dernier cube : %i, %i, %i\n", situation->X, situation->Y, situation->Z) ;
printf("-> Numéro du dernier cube : %i\n", situation->Num) ;
printf("-> Orientation : %i, %i, %i\n",
situation->Orientation[0], situation->Orientation[1], situation->Orientation[2]) ;
return ;
}
/********************************************/
/*** Fonctions d'initialisation diverses ***/
/* Vérifie que la séquence a la bonne taille */
int verif_sequence(int* seq)
{
int somme=0 ;
int i ;
for(i=0; i<Taille; i++)
{
somme+=sequence[i] ;
}
// test de la taille
if(somme != Taille)
{
printf("verif_seq : somme = %i, Taille = %i\n", somme, Taille) ;
return 0 ;
}
//test des zéros bien placés
int j ;
j=0 ;
for(i=0; i<Taille; i++)
{
if(seq[i] !=0)
{
if(j !=0) //raté
{
printf("verif_seq : j=%i, i=%i, seq[%i] = %i\n", j, i, i, seq[i]) ;
return 0 ;
}
j=seq[i] ;
}
j-- ;
}
return 1 ;
}
/* Prépare une situation initialisée */
t_sit * initialise_sit()
{
int i, j, k ;
t_sit * situation ;
situation = malloc(taillesituation) ;
// le cube
for(i=0; i<N; i++)
for(j=0; j<N; j++)
for(k=0; k<N; k++)
situation->Cube[i][j][k] = 0 ;
// l'orientation : rien pour le moment
for(i=0; i<D; i++)
{
situation->Orientation[i] = 0 ;
}
// le reste
situation->X = 0 ;
situation->Y = 0 ;
situation->Z = 0 ;
situation->Num = 0 ;
return situation ;
}
/* Effectue une copie de la situation. */
void copie_sit(t_sit *originale, t_sit *nouvelle)
{
int i, j, k ;
// copie du cube
for(i=0; i<N; i++)
for(j=0; j<N; j++)
for(k=0; k<N; k++)
nouvelle->Cube[i][j][k] = originale->Cube[i][j][k] ;
// copie de l'orientation
for(i=0; i<D; i++)
{
nouvelle->Orientation[i] = originale->Orientation[i] ;
}
// copie du reste
nouvelle->X = originale->X ;
nouvelle->Y = originale->Y ;
nouvelle->Z = originale->Z ;
nouvelle->Num = originale->Num ;
return;
}
/* Prépare une situation de départ : on donne un point de départ du cube et l'orientation,
et la fonction "place" la première séquence dans le cube */
/* depart est censée être une situation déjà initialisée */
int prepare(t_sit * depart, int x, int y, int z, int* orientation)
{
int longueur, i, xp, yp, zp ;
// la longueur de la première séquence
longueur = sequence[0] ;
if(V)
printf("Initialisation : longueur de la première séquence : %i\n", longueur) ;
// coordonnées du cube à mettre
xp = x ;
yp = y ;
zp = z ;
for(i=0; i<longueur; i++)
{
// coordonnées valides ? (pas hors du cube)
if(hors_cube(xp, yp, zp) )
{
printf("Initialisation : les coord sont hors du cube ! Pas normal !\n") ;
return 0 ;
}
depart->Cube[xp][yp][zp] = i+1 ;
if(i != longueur -1)
{
xp += orientation[0] ;
yp += orientation[1] ;
zp += orientation[2] ;
}
}
if(V)
printf("Initialisation : cubes placés\n") ;
depart->Num = longueur ;
// copie de l'orientation
for(i=0; i<D; i++)
depart->Orientation[i] = orientation[i] ;
// la position du dernier cube
depart->X = xp ;
depart->Y = yp ;
depart->Z = zp ;
return 1 ;
}
/***********************************************/
/*** Manipulation du cube ***/
// Est-ce que les coordonnées sont hors du cube ?
int hors_cube(int x, int y, int z)
{
return (x<0 || x>=N || y<0 || y>=N || z<0 || z>=N) ;
}
// Vérifie que deux orientations sont compatibles, ie si elles sont bien différentes (sans compter le sens)
// ex : (1, 0, 0) et (0, -1, 0) ok, mais pas (1, 0, 0) et (-1, 0, 0)
int valide_orientations(int* orient1, int* orient2)
{
return (abs(orient1[0]) != abs(orient2[0])
|| abs(orient1[1]) != abs(orient2[1])
|| abs(orient1[2]) != abs(orient2[2]) ) ;
}
/* teste de placer les cubes suivants selon l'orientation donnée */
/* Renvoie une situation t_sit. Si ça plante, on renvoie la situation, mais avec Num=-1 */
t_sit * tester_cas(t_sit * situation, int * nouvelle_orientation)
{
int i, longueur ;
int x, y, z, num ;
// incrémentation du nombre de tests
nb_tests++ ;
// copie de la situation actuelle
t_sit *situation2 ;
situation2 = malloc(taillesituation) ;
copie_sit(situation, situation2) ;
if(V)
{
printf("Tester_cas : situation actuelle : \n") ;
affiche_situation(situation) ;
printf("-----\n") ;
}
// quelle est la longueur de la prochaine séquence ?
longueur = sequence[situation->Num] ;
if(V)
printf("Tester_cas : longueur de la séquence à appliquer : %i\n", longueur) ;
if(longueur ==0)
{
printf("Tester_cas : problème >_< : la séquence à appliquer est de longueur nulle...\n") ;
printf("Situation obtenue :\n") ;
affiche_situation(situation) ;
}
x = situation2->X ;
y = situation2->Y ;
z = situation2->Z ;
num = situation2->Num ;
for(i=0; i<longueur; i++)
{
// calculer les nouvelles coordonnées
x += nouvelle_orientation[0] ;
y += nouvelle_orientation[1] ;
z += nouvelle_orientation[2] ;
if(hors_cube(x,y,z) || situation2->Cube[x][y][z]>0)
{
if(V)
{
printf("Tester_cas %i : l'orientation (%i, %i, %i) ne marche pas\n", i,
nouvelle_orientation[0], nouvelle_orientation[1], nouvelle_orientation[2]) ;
printf("Nouvelles coordonnées : %i, %i, %i\n", x, y, z) ;
}
situation2->Num = -1 ;
return situation2 ;
}
// c'est bon !
if(V)
printf("Tester_cas %i : l'orientation (%i, %i, %i) marche\n", i,
nouvelle_orientation[0], nouvelle_orientation[1], nouvelle_orientation[2]) ;
num++ ; // il ne faut pas oublier que num commence à 0
situation2->Cube[x][y][z] = num ;
}
if(V)
printf("Tester_cas : tout bon\n") ;
// tout a été bon jusque là, on remet dans la structure
situation2->X = x ;
situation2->Y = y ;
situation2->Z = z ;
situation2->Num = num ;
// copier la nouvelle orientation
for(i=0; i<D; i++)
situation2->Orientation[i] = nouvelle_orientation[i] ;
if(V)
{
printf("Nouvelle situation : \n") ;
affiche_situation(situation2) ;
printf("-----\n") ;
}
return situation2 ;
}
/********** La résolution **********/
int resoudre(t_sit * situation)
{
int i ;
int reussi ;
t_sit *retour ;
// si on est arrivé à la fin de la séquence
if(situation->Num == Taille)
{
printf("Solution trouvée, youhouuuu \\o/\n\n") ;
affiche_cube(&(situation->Cube)) ;
printf("--------------\n") ;
printf("Nombre de cas testés jusque là : %i\n",nb_tests) ;
if(STOP)
return 1 ;
else
return 0 ;
}
for(i=0; i<6; i++)
{
// est-ce que cette orientation est valide ?
if(valide_orientations(situation->Orientation, orientations[i]))
{
if(V)
printf("Test de l'orientation : %i, %i, %i\n",
orientations[i][0], orientations[i][1], orientations[i][2]) ;
// tester ce cas précis
retour = tester_cas(situation, orientations[i]) ;
if(retour->Num ==-1)
{
if(V)
printf("Test échoué ! On passe à la suite\n") ;
}
else
{
// on récurre
reussi = resoudre(retour) ;
if(reussi)
return 1 ;
// si pas réussi, il faut tester d'autres orientations !
}
// libérer la situation qu'on a testée
free(retour) ;
}
}
if(V)
printf("Toutes les orientations sont testées.\n") ;
return 0 ;
}
/****************************************************/
int main(argc, argv)
{
int i ;
if(!verif_sequence(sequence))
{
printf("La séquence des cubes n'est pas valide, c'est mal barré !\n") ;
return 1 ;
}
// Créer les situations de départ
/* Situations de départ */
t_sit * situations_depart[Nb_sit] ;
for(i=0; i<Nb_sit; i++)
{
situations_depart[i] = initialise_sit() ;
}
int orX[D] = {1,0,0} ;
/* Spécifique à la taille N donnée */
/* N = 3 */
/*
prepare(situations_depart[0], 0, 0, 0, orX) ;
prepare(situations_depart[1], 0, 1, 0, orX) ;
prepare(situations_depart[2], 0, 1, 1, orX) ;
*/
/* N = 2 */
// prepare(situations_depart[0], 0, 0, 0, orX) ;
/* N= 4, cube d'ismael */
prepare(situations_depart[0], 0, 0, 0, orX) ;
prepare(situations_depart[1], 0, 1, 0, orX) ;
prepare(situations_depart[2], 0, 1, 1, orX) ;
prepare(situations_depart[3], 1, 0, 0, orX) ;
prepare(situations_depart[4], 1, 1, 0, orX) ;
prepare(situations_depart[5], 1, 1, 1, orX) ;
/* Fin spécifique taille N donnée */
if(V)
{
for(i=0; i<Nb_sit; i++)
{
printf("-- Situation de départ %i --\n", i) ;
affiche_situation(situations_depart[i]) ;
}
printf("----------\n") ;
}
/* Et c'est partiiiii i*/
for(i=0; i<Nb_sit; i++)
{
if(V)
printf("---------\nTest de la situation de départ %i\n-----------\n",i) ;
resoudre(situations_depart[i]) ;
}
printf("Nombre de cas testés au total : %i\n",nb_tests) ;
return 0 ;
}
