solutions_ismael rajoutée
[perso/Denise/cube.git] / cube.c
CommitLineData
e52adcc3
D
1#include <stdio.h>
2#include <stdlib.h>
3
2275e97a 4#define N 4 /* Taille du cube */
e52adcc3
D
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 */
2275e97a
D
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 */
e52adcc3
D
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 ! */
14
15#define V 0 /* Mode verbeux (attention les zyeux) */
16
17/* Pour changer la taille : changer N, changer la séquence des longueurs (en dessous),
18et changer l'initialisation (voir le main) */
19
2275e97a 20// nombre de situations testées
e52adcc3
D
21static int nb_tests = 0 ;
22
23/* La séquence des longueurs : spécifique au cube */
24/* N = 3 */
2275e97a
D
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 } ;
e52adcc3
D
27
28
29/* N = 2 */
30/*int sequence[N*N*N] =
31{ 2, 0, 1, 1, 1, 1, 1, 1} ;
32*/
33/* N = 4 */
2275e97a 34
e52adcc3
D
35/*
36int sequence[Taille] =
37{
384, 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,
391, 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
40} ;
41*/
42
2275e97a
D
43// Cube d'Ismael
44
45int sequence[Taille] =
46{
473, 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,
482, 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,
493, 0, 0, 1
50} ;
51
52
e52adcc3
D
53/* La liste des orientations possibles */
54int orientations[2*D][D] =
55{
56{0, 0, 1}, {0, 0, -1}, { 0, 1, 0}, {0, -1, 0},
57{1, 0, 0}, {-1, 0, 0}
58} ;
59
60
61
62
63/*** Structure ***/
64
65
66typedef 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 */
69 int Y ;
70 int Z ;
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 */
73} t_sit ;
74
75int taillesituation=sizeof(struct Situation) ;
76
77
78/*********************************************/
79/*** Affichage ***/
80
81/* Affichage du cube */
82void affiche_cube(int (*cube)[N][N][N])
83{
84 int i, j, k ;
85 for(k=0;k<N; k++)
86 {
87 printf("*** z=%i :\n", k) ;
88 for(j=0;j<N;j++)
89 {
90 for(i=0;i<N; i++)
91 printf("%i\t", (*cube)[i][j][k]) ;
92 printf("\n") ;
93 }
94 //printf("\n") ;
95 }
96}
97
98/* Affichage d'une situation */
99void affiche_situation(t_sit* situation)
100{
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]) ;
107
108 return ;
109}
110
111/********************************************/
112/*** Fonctions d'initialisation diverses ***/
113
114/* Vérifie que la séquence a la bonne taille */
115int verif_sequence(int* seq)
116{
117 int somme=0 ;
118 int i ;
119
120 for(i=0; i<Taille; i++)
121 {
122 somme+=sequence[i] ;
123 }
124 // test de la taille
125 if(somme != Taille)
126 {
127 printf("verif_seq : somme = %i, Taille = %i\n", somme, Taille) ;
128 return 0 ;
129 }
130
131 //test des zéros bien placés
132 int j ;
133 j=0 ;
134 for(i=0; i<Taille; i++)
135 {
136 if(seq[i] !=0)
137 {
138 if(j !=0) //raté
139 {
140 printf("verif_seq : j=%i, i=%i, seq[%i] = %i\n", j, i, i, seq[i]) ;
141 return 0 ;
142 }
143 j=seq[i] ;
144 }
145 j-- ;
146 }
147 return 1 ;
148}
149
150/* Prépare une situation initialisée */
151t_sit * initialise_sit()
152{
153 int i, j, k ;
154
155 t_sit * situation ;
156 situation = malloc(taillesituation) ;
157
158 // le cube
159 for(i=0; i<N; i++)
160 for(j=0; j<N; j++)
161 for(k=0; k<N; k++)
162 situation->Cube[i][j][k] = 0 ;
163
164 // l'orientation : rien pour le moment
165 for(i=0; i<D; i++)
166 {
167 situation->Orientation[i] = 0 ;
168 }
169 // le reste
170 situation->X = 0 ;
171 situation->Y = 0 ;
172 situation->Z = 0 ;
173 situation->Num = 0 ;
174
175 return situation ;
176
177}
178
179
180/* Effectue une copie de la situation. */
181void copie_sit(t_sit *originale, t_sit *nouvelle)
182{
183 int i, j, k ;
184 // copie du cube
185 for(i=0; i<N; i++)
186 for(j=0; j<N; j++)
187 for(k=0; k<N; k++)
188 nouvelle->Cube[i][j][k] = originale->Cube[i][j][k] ;
189
190 // copie de l'orientation
191 for(i=0; i<D; i++)
192 {
193 nouvelle->Orientation[i] = originale->Orientation[i] ;
194 }
195 // copie du reste
196 nouvelle->X = originale->X ;
197 nouvelle->Y = originale->Y ;
198 nouvelle->Z = originale->Z ;
199
200 nouvelle->Num = originale->Num ;
201
202 return;
203}
204
205
206
207/* Prépare une situation de départ : on donne un point de départ du cube et l'orientation,
208et la fonction "place" la première séquence dans le cube */
209/* depart est censée être une situation déjà initialisée */
210int prepare(t_sit * depart, int x, int y, int z, int* orientation)
211{
212 int longueur, i, xp, yp, zp ;
213
214 // la longueur de la première séquence
215 longueur = sequence[0] ;
216
217 if(V)
218 printf("Initialisation : longueur de la première séquence : %i\n", longueur) ;
219
220 // coordonnées du cube à mettre
221 xp = x ;
222 yp = y ;
223 zp = z ;
224
225 for(i=0; i<longueur; i++)
226 {
227 // coordonnées valides ? (pas hors du cube)
228 if(hors_cube(xp, yp, zp) )
229 {
230 printf("Initialisation : les coord sont hors du cube ! Pas normal !\n") ;
231 return 0 ;
232 }
233 depart->Cube[xp][yp][zp] = i+1 ;
234 if(i != longueur -1)
235 {
236 xp += orientation[0] ;
237 yp += orientation[1] ;
238 zp += orientation[2] ;
239 }
240 }
241 if(V)
242 printf("Initialisation : cubes placés\n") ;
243
244 depart->Num = longueur ;
245 // copie de l'orientation
246 for(i=0; i<D; i++)
247 depart->Orientation[i] = orientation[i] ;
248
249 // la position du dernier cube
250 depart->X = xp ;
251 depart->Y = yp ;
252 depart->Z = zp ;
253
254 return 1 ;
255}
256
257/***********************************************/
258/*** Manipulation du cube ***/
259
260// Est-ce que les coordonnées sont hors du cube ?
261int hors_cube(int x, int y, int z)
262{
263 return (x<0 || x>=N || y<0 || y>=N || z<0 || z>=N) ;
264}
265
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)
268int valide_orientations(int* orient1, int* orient2)
269{
270 return (abs(orient1[0]) != abs(orient2[0])
271 || abs(orient1[1]) != abs(orient2[1])
272 || abs(orient1[2]) != abs(orient2[2]) ) ;
273}
274
275
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 */
278t_sit * tester_cas(t_sit * situation, int * nouvelle_orientation)
279{
280 int i, longueur ;
281 int x, y, z, num ;
282
283 // incrémentation du nombre de tests
284 nb_tests++ ;
285
286 // copie de la situation actuelle
287 t_sit *situation2 ;
288 situation2 = malloc(taillesituation) ;
289 copie_sit(situation, situation2) ;
290
291 if(V)
292 {
293 printf("Tester_cas : situation actuelle : \n") ;
294 affiche_situation(situation) ;
295 printf("-----\n") ;
296
297 }
298 // quelle est la longueur de la prochaine séquence ?
299 longueur = sequence[situation->Num] ;
300
301 if(V)
302 printf("Tester_cas : longueur de la séquence à appliquer : %i\n", longueur) ;
303 if(longueur ==0)
304 {
305 printf("Tester_cas : problème >_< : la séquence à appliquer est de longueur nulle...\n") ;
306 printf("Situation obtenue :\n") ;
307 affiche_situation(situation) ;
308 }
309
310 x = situation2->X ;
311 y = situation2->Y ;
312 z = situation2->Z ;
313 num = situation2->Num ;
314
315 for(i=0; i<longueur; i++)
316 {
317 // calculer les nouvelles coordonnées
318 x += nouvelle_orientation[0] ;
319 y += nouvelle_orientation[1] ;
320 z += nouvelle_orientation[2] ;
321
322 if(hors_cube(x,y,z) || situation2->Cube[x][y][z]>0)
323 {
324 if(V)
325 {
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) ;
329 }
330 situation2->Num = -1 ;
331 return situation2 ;
332 }
333 // c'est bon !
334 if(V)
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 ;
339
340 }
341
342 if(V)
343 printf("Tester_cas : tout bon\n") ;
344
345 // tout a été bon jusque là, on remet dans la structure
346 situation2->X = x ;
347 situation2->Y = y ;
348 situation2->Z = z ;
349 situation2->Num = num ;
350
351 // copier la nouvelle orientation
352 for(i=0; i<D; i++)
353 situation2->Orientation[i] = nouvelle_orientation[i] ;
354
355 if(V)
356 {
357 printf("Nouvelle situation : \n") ;
358 affiche_situation(situation2) ;
359 printf("-----\n") ;
360 }
361
362 return situation2 ;
363}
364
365/********** La résolution **********/
366
367
368int resoudre(t_sit * situation)
369{
370 int i ;
371 int reussi ;
372 t_sit *retour ;
373
374 // si on est arrivé à la fin de la séquence
375 if(situation->Num == Taille)
376 {
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) ;
381 if(STOP)
382 return 1 ;
383 else
384 return 0 ;
385 }
386
387 for(i=0; i<6; i++)
388 {
389 // est-ce que cette orientation est valide ?
390 if(valide_orientations(situation->Orientation, orientations[i]))
391 {
392 if(V)
393 printf("Test de l'orientation : %i, %i, %i\n",
394 orientations[i][0], orientations[i][1], orientations[i][2]) ;
395
396 // tester ce cas précis
397 retour = tester_cas(situation, orientations[i]) ;
398 if(retour->Num ==-1)
399 {
400 if(V)
401 printf("Test échoué ! On passe à la suite\n") ;
402 }
403 else
404 {
405 // on récurre
406 reussi = resoudre(retour) ;
407 if(reussi)
408 return 1 ;
409 // si pas réussi, il faut tester d'autres orientations !
47716201 410
e52adcc3 411 }
47716201
D
412 // libérer la situation qu'on a testée
413 free(retour) ;
e52adcc3
D
414 }
415 }
416 if(V)
417 printf("Toutes les orientations sont testées.\n") ;
418 return 0 ;
419}
420
421
422
423/****************************************************/
424
425int main(argc, argv)
426{
427 int i ;
428
429 if(!verif_sequence(sequence))
430 {
431 printf("La séquence des cubes n'est pas valide, c'est mal barré !\n") ;
432 return 1 ;
433 }
434
435 // Créer les situations de départ
436
437 /* Situations de départ */
438 t_sit * situations_depart[Nb_sit] ;
439
440 for(i=0; i<Nb_sit; i++)
441 {
442 situations_depart[i] = initialise_sit() ;
443 }
444
445
446 int orX[D] = {1,0,0} ;
447 /* Spécifique à la taille N donnée */
448 /* N = 3 */
2275e97a 449/*
e52adcc3
D
450 prepare(situations_depart[0], 0, 0, 0, orX) ;
451 prepare(situations_depart[1], 0, 1, 0, orX) ;
452 prepare(situations_depart[2], 0, 1, 1, orX) ;
2275e97a 453*/
e52adcc3
D
454 /* N = 2 */
455// prepare(situations_depart[0], 0, 0, 0, orX) ;
2275e97a
D
456
457 /* N= 4, cube d'ismael */
458 prepare(situations_depart[0], 0, 0, 0, orX) ;
459 prepare(situations_depart[1], 0, 1, 0, orX) ;
460 prepare(situations_depart[2], 0, 1, 1, orX) ;
461
462 prepare(situations_depart[3], 1, 0, 0, orX) ;
463 prepare(situations_depart[4], 1, 1, 0, orX) ;
464 prepare(situations_depart[5], 1, 1, 1, orX) ;
465
466
e52adcc3
D
467
468 /* Fin spécifique taille N donnée */
469
470 if(V)
471 {
472 for(i=0; i<Nb_sit; i++)
473 {
474 printf("-- Situation de départ %i --\n", i) ;
475 affiche_situation(situations_depart[i]) ;
476 }
477 printf("----------\n") ;
478 }
479 /* Et c'est partiiiii i*/
480
481 for(i=0; i<Nb_sit; i++)
482 {
483 if(V)
484 printf("---------\nTest de la situation de départ %i\n-----------\n",i) ;
485 resoudre(situations_depart[i]) ;
486
487 }
488 printf("Nombre de cas testés au total : %i\n",nb_tests) ;
489 return 0 ;
490}