solutions_ismael rajoutée

[perso/Denise/cube.git] / cube.c

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