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