]>
git.immae.eu Git - perso/Denise/cube.git/blob - cube.c
f170bd21ee11a7350cb771c5efb8648107b9a141
4 #define N 3 /* 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 3 /* Nombre de situations de départ : pour 3 et 4, il y en a 3 */
8 #define D 3 /* On travaille en 3 dimensions */
9 /* NB : pas adapté à faire autre chose que 3 dimensions !
10 Ou en tous cas pas sans un peu de boulot */
11 #define STOP 0 /* STOP : est-ce qu'on s'arrête après avoir trouvé une solution.
12 Quand STOP vaut 0, il teste tout ! */
14 #define V 0 /* Mode verbeux (attention les zyeux) */
16 /* Pour changer la taille : changer N, changer la séquence des longueurs (en dessous),
17 et changer l'initialisation (voir le main) */
19 // nombre de situations
20 static int nb_tests
= 0 ;
22 /* La séquence des longueurs : spécifique au cube */
24 int sequence
[Taille
] =
25 { 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 } ;
29 /*int sequence[N*N*N] =
30 { 2, 0, 1, 1, 1, 1, 1, 1} ;
34 int sequence[Taille] =
36 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,
37 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
41 /* La liste des orientations possibles */
42 int orientations
[2*D
][D
] =
44 {0, 0, 1}, {0, 0, -1}, { 0, 1, 0}, {0, -1, 0},
54 typedef struct Situation
{
55 int Cube
[N
][N
][N
] ; /* Le cube, rempli d'entiers */
56 int X
; /* Coord du dernier cube qu'on y a mis */
59 int Orientation
[D
] ; /* L'orientation du dernier cube : par ex (0, +1, 0) */
60 int Num
; /* Le numéro du dernier cube qu'on y a mis */
63 int taillesituation
=sizeof(struct Situation
) ;
66 /*********************************************/
69 /* Affichage du cube */
70 void affiche_cube(int (*cube
)[N
][N
][N
])
75 printf("*** z=%i :\n", k
) ;
79 printf("%i\t", (*cube
)[i
][j
][k
]) ;
86 /* Affichage d'une situation */
87 void affiche_situation(t_sit
* situation
)
89 printf("-> Cube : \n") ;
90 affiche_cube(&situation
->Cube
) ;
91 printf("-> Coordonnées du dernier cube : %i, %i, %i\n", situation
->X
, situation
->Y
, situation
->Z
) ;
92 printf("-> Numéro du dernier cube : %i\n", situation
->Num
) ;
93 printf("-> Orientation : %i, %i, %i\n",
94 situation
->Orientation
[0], situation
->Orientation
[1], situation
->Orientation
[2]) ;
99 /********************************************/
100 /*** Fonctions d'initialisation diverses ***/
102 /* Vérifie que la séquence a la bonne taille */
103 int verif_sequence(int* seq
)
108 for(i
=0; i
<Taille
; i
++)
115 printf("verif_seq : somme = %i, Taille = %i\n", somme
, Taille
) ;
119 //test des zéros bien placés
122 for(i
=0; i
<Taille
; i
++)
128 printf("verif_seq : j=%i, i=%i, seq[%i] = %i\n", j
, i
, i
, seq
[i
]) ;
138 /* Prépare une situation initialisée */
139 t_sit
* initialise_sit()
144 situation
= malloc(taillesituation
) ;
150 situation
->Cube
[i
][j
][k
] = 0 ;
152 // l'orientation : rien pour le moment
155 situation
->Orientation
[i
] = 0 ;
168 /* Effectue une copie de la situation. */
169 void copie_sit(t_sit
*originale
, t_sit
*nouvelle
)
176 nouvelle
->Cube
[i
][j
][k
] = originale
->Cube
[i
][j
][k
] ;
178 // copie de l'orientation
181 nouvelle
->Orientation
[i
] = originale
->Orientation
[i
] ;
184 nouvelle
->X
= originale
->X
;
185 nouvelle
->Y
= originale
->Y
;
186 nouvelle
->Z
= originale
->Z
;
188 nouvelle
->Num
= originale
->Num
;
195 /* Prépare une situation de départ : on donne un point de départ du cube et l'orientation,
196 et la fonction "place" la première séquence dans le cube */
197 /* depart est censée être une situation déjà initialisée */
198 int prepare(t_sit
* depart
, int x
, int y
, int z
, int* orientation
)
200 int longueur
, i
, xp
, yp
, zp
;
202 // la longueur de la première séquence
203 longueur
= sequence
[0] ;
206 printf("Initialisation : longueur de la première séquence : %i\n", longueur
) ;
208 // coordonnées du cube à mettre
213 for(i
=0; i
<longueur
; i
++)
215 // coordonnées valides ? (pas hors du cube)
216 if(hors_cube(xp
, yp
, zp
) )
218 printf("Initialisation : les coord sont hors du cube ! Pas normal !\n") ;
221 depart
->Cube
[xp
][yp
][zp
] = i
+1 ;
224 xp
+= orientation
[0] ;
225 yp
+= orientation
[1] ;
226 zp
+= orientation
[2] ;
230 printf("Initialisation : cubes placés\n") ;
232 depart
->Num
= longueur
;
233 // copie de l'orientation
235 depart
->Orientation
[i
] = orientation
[i
] ;
237 // la position du dernier cube
245 /***********************************************/
246 /*** Manipulation du cube ***/
248 // Est-ce que les coordonnées sont hors du cube ?
249 int hors_cube(int x
, int y
, int z
)
251 return (x
<0 || x
>=N
|| y
<0 || y
>=N
|| z
<0 || z
>=N
) ;
254 // Vérifie que deux orientations sont compatibles, ie si elles sont bien différentes (sans compter le sens)
255 // ex : (1, 0, 0) et (0, -1, 0) ok, mais pas (1, 0, 0) et (-1, 0, 0)
256 int valide_orientations(int* orient1
, int* orient2
)
258 return (abs(orient1
[0]) != abs(orient2
[0])
259 || abs(orient1
[1]) != abs(orient2
[1])
260 || abs(orient1
[2]) != abs(orient2
[2]) ) ;
264 /* teste de placer les cubes suivants selon l'orientation donnée */
265 /* Renvoie une situation t_sit. Si ça plante, on renvoie la situation, mais avec Num=-1 */
266 t_sit
* tester_cas(t_sit
* situation
, int * nouvelle_orientation
)
271 // incrémentation du nombre de tests
274 // copie de la situation actuelle
276 situation2
= malloc(taillesituation
) ;
277 copie_sit(situation
, situation2
) ;
281 printf("Tester_cas : situation actuelle : \n") ;
282 affiche_situation(situation
) ;
286 // quelle est la longueur de la prochaine séquence ?
287 longueur
= sequence
[situation
->Num
] ;
290 printf("Tester_cas : longueur de la séquence à appliquer : %i\n", longueur
) ;
293 printf("Tester_cas : problème >_< : la séquence à appliquer est de longueur nulle...\n") ;
294 printf("Situation obtenue :\n") ;
295 affiche_situation(situation
) ;
301 num
= situation2
->Num
;
303 for(i
=0; i
<longueur
; i
++)
305 // calculer les nouvelles coordonnées
306 x
+= nouvelle_orientation
[0] ;
307 y
+= nouvelle_orientation
[1] ;
308 z
+= nouvelle_orientation
[2] ;
310 if(hors_cube(x
,y
,z
) || situation2
->Cube
[x
][y
][z
]>0)
314 printf("Tester_cas %i : l'orientation (%i, %i, %i) ne marche pas\n", i
,
315 nouvelle_orientation
[0], nouvelle_orientation
[1], nouvelle_orientation
[2]) ;
316 printf("Nouvelles coordonnées : %i, %i, %i\n", x
, y
, z
) ;
318 situation2
->Num
= -1 ;
323 printf("Tester_cas %i : l'orientation (%i, %i, %i) marche\n", i
,
324 nouvelle_orientation
[0], nouvelle_orientation
[1], nouvelle_orientation
[2]) ;
325 num
++ ; // il ne faut pas oublier que num commence à 0
326 situation2
->Cube
[x
][y
][z
] = num
;
331 printf("Tester_cas : tout bon\n") ;
333 // tout a été bon jusque là, on remet dans la structure
337 situation2
->Num
= num
;
339 // copier la nouvelle orientation
341 situation2
->Orientation
[i
] = nouvelle_orientation
[i
] ;
345 printf("Nouvelle situation : \n") ;
346 affiche_situation(situation2
) ;
353 /********** La résolution **********/
356 int resoudre(t_sit
* situation
)
362 // si on est arrivé à la fin de la séquence
363 if(situation
->Num
== Taille
)
365 printf("Solution trouvée, youhouuuu \\o/\n\n") ;
366 affiche_cube(&(situation
->Cube
)) ;
367 printf("--------------\n") ;
368 printf("Nombre de cas testés jusque là : %i\n",nb_tests
) ;
377 // est-ce que cette orientation est valide ?
378 if(valide_orientations(situation
->Orientation
, orientations
[i
]))
381 printf("Test de l'orientation : %i, %i, %i\n",
382 orientations
[i
][0], orientations
[i
][1], orientations
[i
][2]) ;
384 // tester ce cas précis
385 retour
= tester_cas(situation
, orientations
[i
]) ;
389 printf("Test échoué ! On passe à la suite\n") ;
394 reussi
= resoudre(retour
) ;
397 // si pas réussi, il faut tester d'autres orientations !
402 printf("Toutes les orientations sont testées.\n") ;
408 /****************************************************/
414 if(!verif_sequence(sequence
))
416 printf("La séquence des cubes n'est pas valide, c'est mal barré !\n") ;
420 // Créer les situations de départ
422 /* Situations de départ */
423 t_sit
* situations_depart
[Nb_sit
] ;
425 for(i
=0; i
<Nb_sit
; i
++)
427 situations_depart
[i
] = initialise_sit() ;
431 int orX
[D
] = {1,0,0} ;
432 /* Spécifique à la taille N donnée */
435 prepare(situations_depart
[0], 0, 0, 0, orX
) ;
436 prepare(situations_depart
[1], 0, 1, 0, orX
) ;
437 prepare(situations_depart
[2], 0, 1, 1, orX
) ;
440 // prepare(situations_depart[0], 0, 0, 0, orX) ;
442 /* Fin spécifique taille N donnée */
446 for(i
=0; i
<Nb_sit
; i
++)
448 printf("-- Situation de départ %i --\n", i
) ;
449 affiche_situation(situations_depart
[i
]) ;
451 printf("----------\n") ;
453 /* Et c'est partiiiii i*/
455 for(i
=0; i
<Nb_sit
; i
++)
458 printf("---------\nTest de la situation de départ %i\n-----------\n",i
) ;
459 resoudre(situations_depart
[i
]) ;
462 printf("Nombre de cas testés au total : %i\n",nb_tests
) ;