]>
git.immae.eu Git - perso/Denise/cube.git/blob - cube.c
ac9204236dde03c8cbd52ea7f4763064add9d5ee
4 #define N 4 /* Taille du cube */
5 #define Taille N*N*N /* Nombre de petits cubes */
6 //#define Nb_sit 1 /* Nombre de situations de départ : pour 2, une seule */
7 #define Nb_sit 6 /* Nombre de situations de départ : pour 3 et 4, il y en a 3 */
8 /* Pour le cube d'ismael : 6 */
9 #define D 3 /* On travaille en 3 dimensions */
10 /* NB : pas adapté à faire autre chose que 3 dimensions !
11 Ou en tous cas pas sans un peu de boulot */
12 #define STOP 0 /* STOP : est-ce qu'on s'arrête après avoir trouvé une solution.
13 Quand STOP vaut 0, il teste tout ! */
15 #define V 0 /* Mode verbeux (attention les zyeux) */
17 /* Pour changer la taille : changer N, changer la séquence des longueurs (en dessous),
18 et changer l'initialisation (voir le main) */
20 // nombre de situations testées
21 static int nb_tests
= 0 ;
23 /* La séquence des longueurs : spécifique au cube */
25 //int sequence[Taille] =
26 //{ 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 } ;
30 /*int sequence[N*N*N] =
31 { 2, 0, 1, 1, 1, 1, 1, 1} ;
36 int sequence[Taille] =
38 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,
39 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
45 int sequence
[Taille
] =
47 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,
48 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,
53 /* La liste des orientations possibles */
54 int orientations
[2*D
][D
] =
56 {0, 0, 1}, {0, 0, -1}, { 0, 1, 0}, {0, -1, 0},
66 typedef struct Situation
{
67 int Cube
[N
][N
][N
] ; /* Le cube, rempli d'entiers */
68 int X
; /* Coord du dernier cube qu'on y a mis */
71 int Orientation
[D
] ; /* L'orientation du dernier cube : par ex (0, +1, 0) */
72 int Num
; /* Le numéro du dernier cube qu'on y a mis */
75 int taillesituation
=sizeof(struct Situation
) ;
78 /*********************************************/
81 /* Affichage du cube */
82 void affiche_cube(int (*cube
)[N
][N
][N
])
87 printf("*** z=%i :\n", k
) ;
91 printf("%i\t", (*cube
)[i
][j
][k
]) ;
98 /* Affichage d'une situation */
99 void affiche_situation(t_sit
* situation
)
101 printf("-> Cube : \n") ;
102 affiche_cube(&situation
->Cube
) ;
103 printf("-> Coordonnées du dernier cube : %i, %i, %i\n", situation
->X
, situation
->Y
, situation
->Z
) ;
104 printf("-> Numéro du dernier cube : %i\n", situation
->Num
) ;
105 printf("-> Orientation : %i, %i, %i\n",
106 situation
->Orientation
[0], situation
->Orientation
[1], situation
->Orientation
[2]) ;
111 /********************************************/
112 /*** Fonctions d'initialisation diverses ***/
114 /* Vérifie que la séquence a la bonne taille */
115 int verif_sequence(int* seq
)
120 for(i
=0; i
<Taille
; i
++)
127 printf("verif_seq : somme = %i, Taille = %i\n", somme
, Taille
) ;
131 //test des zéros bien placés
134 for(i
=0; i
<Taille
; i
++)
140 printf("verif_seq : j=%i, i=%i, seq[%i] = %i\n", j
, i
, i
, seq
[i
]) ;
150 /* Prépare une situation initialisée */
151 t_sit
* initialise_sit()
156 situation
= malloc(taillesituation
) ;
162 situation
->Cube
[i
][j
][k
] = 0 ;
164 // l'orientation : rien pour le moment
167 situation
->Orientation
[i
] = 0 ;
180 /* Effectue une copie de la situation. */
181 void copie_sit(t_sit
*originale
, t_sit
*nouvelle
)
188 nouvelle
->Cube
[i
][j
][k
] = originale
->Cube
[i
][j
][k
] ;
190 // copie de l'orientation
193 nouvelle
->Orientation
[i
] = originale
->Orientation
[i
] ;
196 nouvelle
->X
= originale
->X
;
197 nouvelle
->Y
= originale
->Y
;
198 nouvelle
->Z
= originale
->Z
;
200 nouvelle
->Num
= originale
->Num
;
207 /* Prépare une situation de départ : on donne un point de départ du cube et l'orientation,
208 et la fonction "place" la première séquence dans le cube */
209 /* depart est censée être une situation déjà initialisée */
210 int prepare(t_sit
* depart
, int x
, int y
, int z
, int* orientation
)
212 int longueur
, i
, xp
, yp
, zp
;
214 // la longueur de la première séquence
215 longueur
= sequence
[0] ;
218 printf("Initialisation : longueur de la première séquence : %i\n", longueur
) ;
220 // coordonnées du cube à mettre
225 for(i
=0; i
<longueur
; i
++)
227 // coordonnées valides ? (pas hors du cube)
228 if(hors_cube(xp
, yp
, zp
) )
230 printf("Initialisation : les coord sont hors du cube ! Pas normal !\n") ;
233 depart
->Cube
[xp
][yp
][zp
] = i
+1 ;
236 xp
+= orientation
[0] ;
237 yp
+= orientation
[1] ;
238 zp
+= orientation
[2] ;
242 printf("Initialisation : cubes placés\n") ;
244 depart
->Num
= longueur
;
245 // copie de l'orientation
247 depart
->Orientation
[i
] = orientation
[i
] ;
249 // la position du dernier cube
257 /***********************************************/
258 /*** Manipulation du cube ***/
260 // Est-ce que les coordonnées sont hors du cube ?
261 int hors_cube(int x
, int y
, int z
)
263 return (x
<0 || x
>=N
|| y
<0 || y
>=N
|| z
<0 || z
>=N
) ;
266 // Vérifie que deux orientations sont compatibles, ie si elles sont bien différentes (sans compter le sens)
267 // ex : (1, 0, 0) et (0, -1, 0) ok, mais pas (1, 0, 0) et (-1, 0, 0)
268 int valide_orientations(int* orient1
, int* orient2
)
270 return (abs(orient1
[0]) != abs(orient2
[0])
271 || abs(orient1
[1]) != abs(orient2
[1])
272 || abs(orient1
[2]) != abs(orient2
[2]) ) ;
276 /* teste de placer les cubes suivants selon l'orientation donnée */
277 /* Renvoie une situation t_sit. Si ça plante, on renvoie la situation, mais avec Num=-1 */
278 t_sit
* tester_cas(t_sit
* situation
, int * nouvelle_orientation
)
283 // incrémentation du nombre de tests
286 // copie de la situation actuelle
288 situation2
= malloc(taillesituation
) ;
289 copie_sit(situation
, situation2
) ;
293 printf("Tester_cas : situation actuelle : \n") ;
294 affiche_situation(situation
) ;
298 // quelle est la longueur de la prochaine séquence ?
299 longueur
= sequence
[situation
->Num
] ;
302 printf("Tester_cas : longueur de la séquence à appliquer : %i\n", longueur
) ;
305 printf("Tester_cas : problème >_< : la séquence à appliquer est de longueur nulle...\n") ;
306 printf("Situation obtenue :\n") ;
307 affiche_situation(situation
) ;
313 num
= situation2
->Num
;
315 for(i
=0; i
<longueur
; i
++)
317 // calculer les nouvelles coordonnées
318 x
+= nouvelle_orientation
[0] ;
319 y
+= nouvelle_orientation
[1] ;
320 z
+= nouvelle_orientation
[2] ;
322 if(hors_cube(x
,y
,z
) || situation2
->Cube
[x
][y
][z
]>0)
326 printf("Tester_cas %i : l'orientation (%i, %i, %i) ne marche pas\n", i
,
327 nouvelle_orientation
[0], nouvelle_orientation
[1], nouvelle_orientation
[2]) ;
328 printf("Nouvelles coordonnées : %i, %i, %i\n", x
, y
, z
) ;
330 situation2
->Num
= -1 ;
335 printf("Tester_cas %i : l'orientation (%i, %i, %i) marche\n", i
,
336 nouvelle_orientation
[0], nouvelle_orientation
[1], nouvelle_orientation
[2]) ;
337 num
++ ; // il ne faut pas oublier que num commence à 0
338 situation2
->Cube
[x
][y
][z
] = num
;
343 printf("Tester_cas : tout bon\n") ;
345 // tout a été bon jusque là, on remet dans la structure
349 situation2
->Num
= num
;
351 // copier la nouvelle orientation
353 situation2
->Orientation
[i
] = nouvelle_orientation
[i
] ;
357 printf("Nouvelle situation : \n") ;
358 affiche_situation(situation2
) ;
365 /********** La résolution **********/
368 int resoudre(t_sit
* situation
)
374 // si on est arrivé à la fin de la séquence
375 if(situation
->Num
== Taille
)
377 printf("Solution trouvée, youhouuuu \\o/\n\n") ;
378 affiche_cube(&(situation
->Cube
)) ;
379 printf("--------------\n") ;
380 printf("Nombre de cas testés jusque là : %i\n",nb_tests
) ;
389 // est-ce que cette orientation est valide ?
390 if(valide_orientations(situation
->Orientation
, orientations
[i
]))
393 printf("Test de l'orientation : %i, %i, %i\n",
394 orientations
[i
][0], orientations
[i
][1], orientations
[i
][2]) ;
396 // tester ce cas précis
397 retour
= tester_cas(situation
, orientations
[i
]) ;
401 printf("Test échoué ! On passe à la suite\n") ;
406 reussi
= resoudre(retour
) ;
409 // si pas réussi, il faut tester d'autres orientations !
414 printf("Toutes les orientations sont testées.\n") ;
420 /****************************************************/
426 if(!verif_sequence(sequence
))
428 printf("La séquence des cubes n'est pas valide, c'est mal barré !\n") ;
432 // Créer les situations de départ
434 /* Situations de départ */
435 t_sit
* situations_depart
[Nb_sit
] ;
437 for(i
=0; i
<Nb_sit
; i
++)
439 situations_depart
[i
] = initialise_sit() ;
443 int orX
[D
] = {1,0,0} ;
444 /* Spécifique à la taille N donnée */
447 prepare(situations_depart[0], 0, 0, 0, orX) ;
448 prepare(situations_depart[1], 0, 1, 0, orX) ;
449 prepare(situations_depart[2], 0, 1, 1, orX) ;
452 // prepare(situations_depart[0], 0, 0, 0, orX) ;
454 /* N= 4, cube d'ismael */
455 prepare(situations_depart
[0], 0, 0, 0, orX
) ;
456 prepare(situations_depart
[1], 0, 1, 0, orX
) ;
457 prepare(situations_depart
[2], 0, 1, 1, orX
) ;
459 prepare(situations_depart
[3], 1, 0, 0, orX
) ;
460 prepare(situations_depart
[4], 1, 1, 0, orX
) ;
461 prepare(situations_depart
[5], 1, 1, 1, orX
) ;
465 /* Fin spécifique taille N donnée */
469 for(i
=0; i
<Nb_sit
; i
++)
471 printf("-- Situation de départ %i --\n", i
) ;
472 affiche_situation(situations_depart
[i
]) ;
474 printf("----------\n") ;
476 /* Et c'est partiiiii i*/
478 for(i
=0; i
<Nb_sit
; i
++)
481 printf("---------\nTest de la situation de départ %i\n-----------\n",i
) ;
482 resoudre(situations_depart
[i
]) ;
485 printf("Nombre de cas testés au total : %i\n",nb_tests
) ;