1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
| //mingw32 sur W7 gcc 4.8.1
//gcc -Wall -Wextra -std=c99 -march=native -Ofast -flto -fomit-frame-pointer -pipe -o Solitaire.exe Solitaire.c && Solitaire.exe
#include <stdio.h>
#include <string.h>
#include <windows.h>
#define TRUE 1
#define FALSE 0
#define VIDE 0
#define BILLE 1
#define INTERDIT 2
//
#define USESYM 1 //Utilisation des symétries
#define INFINI 1 //Arrêt ou non dès qu'une solution est trouvée
//#define PRINT 0 //Ecritures ou non Résultats
//#define PRINTDEP 0//10000000000
unsigned long long DEPLACEMENTS=0; //Nombre total de déplacements
unsigned long long MULTDEP=0; //Multiple de PRINTDEP déplacements
unsigned long long SOL1=0; //Nombre de solutions avec le nb souhaité de billes restantes et la position finale souhaitée
unsigned long long SOL2=0; //Nombre de solutions avec le nb souhaité de billes restantes sans la position finale souhaitée
unsigned long long SYMETRIES=0; //Nombre de symétries
#define DIM 7 //Dimension du plateau de jeu depuis l'indice 1
#define DIMm1 (DIM - 1) //Dimension du plateau de jeu depuis l'indice 0
#define DIMdemi 4 //Demi Dimension du plateau de jeu depuis l'indice 1
#define DIMdemim1 (DIMdemi-1) //Demi Dimension du plateau de jeu depuis l'indice 0
#define BILLESWIN 1 //Nombre souhaité de billes restantes
#define LWIN 3 //Ligne finale souhaitée (si 1 bille restante)
#define CWIN 3 //Colonne finale souhaitée (si 1 bille restante)
/*
// Solitaire Anglais
//40 861 647 040 079 968 Solutions
short P[DIM][DIM]={ {2,2,1,1,1,2,2},
{2,2,1,1,1,2,2},
{1,1,1,1,1,1,1},
{1,1,1,0,1,1,1},
{1,1,1,1,1,1,1},
{2,2,1,1,1,2,2},
{2,2,1,1,1,2,2} };
*/
// Grande Pyramide
short P[DIM][DIM]={ {2,2,0,0,0,2,2},
{2,2,0,1,0,2,2},
{0,0,1,1,1,0,0},
{0,1,1,1,1,1,0},
{1,1,1,1,1,1,1},
{2,2,0,0,0,2,2},
{2,2,0,0,0,2,2} };
/*
// Petit Diamant
short P[DIM][DIM]={ {2,2,0,0,0,2,2},
{2,2,0,1,0,2,2},
{0,0,1,1,1,0,0},
{0,1,1,0,1,1,0},
{0,0,1,1,1,0,0},
{2,2,0,1,0,2,2},
{2,2,0,0,0,2,2} };
// Fire Place
short P[DIM][DIM]={ {2,2,1,1,1,2,2},
{2,2,1,1,1,2,2},
{0,0,1,1,1,0,0},
{0,0,1,0,1,0,0},
{0,0,0,0,0,0,0},
{2,2,0,0,0,2,2},
{2,2,0,0,0,2,2} };
// Cross
short P[DIM][DIM]={ {2,2,0,0,0,2,2},
{2,2,0,1,0,2,2},
{0,0,1,1,1,0,0},
{0,0,0,1,0,0,0},
{0,0,0,1,0,0,0},
{2,2,0,0,0,2,2},
{2,2,0,0,0,2,2} };
// Plus
short P[DIM][DIM]={ {2,2,0,0,0,2,2},
{2,2,0,1,0,2,2},
{0,0,0,1,0,0,0},
{0,1,1,1,1,1,0},
{0,0,0,1,0,0,0},
{2,2,0,1,0,2,2},
{2,2,0,0,0,2,2} };
*/
//Affichage du plateau de jeu
void Draw(short billes) {
int i=0,j=0;
for (i=0;i<DIM;i++) {
for (j=billes;j>1;j--) {printf(" ");}
for (j=0;j<DIM;j++) {
switch(P[i][j]) {
case VIDE : printf(" "); break;
case BILLE : printf("O"); break;
case INTERDIT: printf("/"); break;
}
}
if(!i) {printf(" %i",billes);}
printf ("\n");
}
}
//Jouer un plateau de jeu
short Jouer(short billes) {
int i=0,j=0;
int imax=DIM,jmax=DIM,jstart=0,jstop=DIM;
int symv=0,symd1=0,symh=0,symd2=0;
short gagnant=0; //etat du coup courant
short billes2=0; //Nombre suivant de billes
short balayees=0; //Nombre de billes balayées
// if(PRINTDEP) {
// //Affichage du nombre courant de déplacement tous les PRINTDEP
// if(DEPLACEMENTS>=PRINTDEP) {
// DEPLACEMENTS=DEPLACEMENTS-PRINTDEP;
// ++MULTDEP;
// printf("%llu deplacements testes (%llu/%llu)\n",MULTDEP*PRINTDEP+DEPLACEMENTS,SOL1,SOL2);
// fflush(stdout);
// }
// }
//Recherche de Symétries
if(0 || USESYM) {
//Recherche d'une symétrie selon l'axe vertical
symv=1;
for(i=0;i<DIM;++i){
for(j=0;j<DIMdemim1;++j){
if(P[i][j]!=P[i][DIMm1-j]) {
symv=0;
break;
}
}
if(!symv) break;
}
//Recherche d'une symétrie selon la diagonale NO
symd1=1;
for(i=0;i<DIMm1;++i){
for(j=i+1;j<DIM;++j){
if(P[i][j]!=P[j][i]) {
symd1=0;
break;
}
}
if(!symd1) break;
}
//Recherche d'une symétrie selon l'axe horizontal
symh=1;
if(!(symv&&symd1)) {
for(i=0;i<DIMdemim1;++i){
for(j=0;j<DIM;++j){
if(P[i][j]!=P[DIMm1-i][j]) {
symh=0;
break;
}
}
if(!symh) break;
}
}
//Recherche d'une symétrie selon la diagonale NE
symd2=1;
if(!(symv&&symd1)) {
for(i=0;i<DIMm1;++i){
for(j=0;j<(DIM-(i+1));++j){
if(P[i][j]!=P[DIMm1-j][DIMm1-i]) {
symd2=0;
break;
}
}
if(!symd2) break;
}
}
//Recenssement des symétries
SYMETRIES+=symv+symd1+symh+symd2;
//Bornes du plateau à balayer
if(symh || (symd1&&symd2)) imax=DIMdemi;
if(symv) jmax=DIMdemi;jstop=jmax;
}
//Balayage plateau à DIM lignes DIM colonnes
for (i=0;i<imax;++i) {
//Bornes du plateau à balayer
if(USESYM){
if(symd1) jstart=i;
if(symd2) jstop=min(DIM-i,jmax);
}
for (j=jstart;j<jstop;++j) {
if(P[i][j]==BILLE) { //bille présente
//Ouest
if(j-2>-1 && !(symd1&&j==i) && P[i][j-1]==BILLE && P[i][j-2]==VIDE) {//Test déplacement à effectuer
billes2=billes-1;
++DEPLACEMENTS;
//Test si le coup est gagnant
gagnant=0;
if(billes2==BILLESWIN) {
gagnant=2;
++SOL2;
if(BILLESWIN==1 && LWIN==i && CWIN==j-2) {
gagnant=1;
++SOL1;
} //fin position souhaitée
// if(PRINT) {
// printf("%llu/%llu solution(s) trouvee(s) a %llu deplacements\n",SOL1,SOL2,DEPLACEMENTS);
// //Déplacement
// P[i][j]=VIDE; P[i][j-1]=VIDE; P[i][j-2]=BILLE;
// //affichage
// Draw(billes2);
// //Retour au plateau précédent
// P[i][j]=BILLE;P[i][j-1]=BILLE;P[i][j-2]=VIDE;
// }
//coup non gagnant
}else{
//Déplacement
P[i][j]=VIDE; P[i][j-1]=VIDE; P[i][j-2]=BILLE;
//Nouveau plateau à jouer
gagnant=Jouer(billes2);
//affichage
// if(PRINT && gagnant!=0) {Draw(billes2);}
//Retour au plateau précédent
P[i][j]=BILLE;P[i][j-1]=BILLE;P[i][j-2]=VIDE;
}
if(!INFINI&&gagnant==1) {return(gagnant);} //arrêt de la recherche
} //fin Ouest
//Sud
if(i+2<DIM && !((symd1&&j==i)||(symh&&i==DIMdemim1)||(symd2&&j==DIMm1-i)) && P[i+1][j]==BILLE && P[i+2][j]==VIDE) {//Test déplacement à effectuer
billes2=billes-1;
++DEPLACEMENTS;
//Test si le coup est gagnant
gagnant=0;
if(billes2==BILLESWIN) {
gagnant=2;
++SOL2;
if(BILLESWIN==1 && LWIN==i+2 && CWIN==j) {
gagnant=1;
++SOL1;
} //fin position souhaitée
// if(PRINT) {
// printf("%llu/%llu solution(s) trouvee(s) a %llu deplacements\n",SOL1,SOL2,DEPLACEMENTS);
// //Déplacement
// P[i][j]=VIDE; P[i+1][j]=VIDE; P[i+2][j]=BILLE;
// //affichage
// Draw(billes2);
// //Retour au plateau précédent
// P[i][j]=BILLE;P[i+1][j]=BILLE;P[i+2][j]=VIDE;
// }
//coup non gagnant
}else{
//Déplacement
P[i][j]=VIDE; P[i+1][j]=VIDE; P[i+2][j]=BILLE;
//Nouveau plateau à jouer
gagnant=Jouer(billes2);
//affichage
// if(PRINT && gagnant!=0) {Draw(billes2);}
//Retour au plateau précédent
P[i][j]=BILLE;P[i+1][j]=BILLE;P[i+2][j]=VIDE;
}
if(!INFINI&&gagnant==1) {return(gagnant);} //arrêt de la recherche
} //fin Sud
//Est
if(j+2<DIM && !((symv&&j==DIMdemim1)||(symd2&&j==DIMm1-i)) && P[i][j+1]==BILLE && P[i][j+2]==VIDE) {//Test déplacement à effectuer
billes2=billes-1;
++DEPLACEMENTS;
//Test si le coup est gagnant
gagnant=0;
if(billes2==BILLESWIN) {
gagnant=2;
++SOL2;
if(BILLESWIN==1 && LWIN==i && CWIN==j+2) {
gagnant=1;
++SOL1;
} //fin position souhaitée
// if(PRINT) {
// printf("%llu/%llu solution(s) trouvee(s) a %llu deplacements\n",SOL1,SOL2,DEPLACEMENTS);
// //Déplacement
// P[i][j]=VIDE; P[i][j+1]=VIDE; P[i][j+2]=BILLE;
// //affichage
// Draw(billes2);
// //Retour au plateau précédent
// P[i][j]=BILLE;P[i][j+1]=BILLE;P[i][j+2]=VIDE;
// }
//coup non gagnant
}else{
//Déplacement
P[i][j]=VIDE; P[i][j+1]=VIDE; P[i][j+2]=BILLE;
//Nouveau plateau à jouer
gagnant=Jouer(billes2);
//affichage
// if(PRINT && gagnant!=0) {Draw(billes2);}
//Retour au plateau précédent
P[i][j]=BILLE;P[i][j+1]=BILLE;P[i][j+2]=VIDE;
}
if(!INFINI&&gagnant==1) {return(gagnant);} //arrêt de la recherche
} //fin Est
//Nord
if(i-2>-1 && P[i-1][j]==BILLE && P[i-2][j]==VIDE) {//Test déplacement à effectuer
billes2=billes-1;
++DEPLACEMENTS;
//Test si le coup est gagnant
gagnant=0;
if(billes2==BILLESWIN) {
gagnant=2;
++SOL2;
if(BILLESWIN==1 && LWIN==i-2 && CWIN==j) {
gagnant=1;
++SOL1;
} //fin position souhaitée
// if(PRINT) {
// printf("%llu/%llu solution(s) trouvee(s) a %llu deplacements\n",SOL1,SOL2,DEPLACEMENTS);
// //Déplacement
// P[i][j]=VIDE; P[i-1][j]=VIDE; P[i-2][j]=BILLE;
// //affichage
// Draw(billes2);
// // c=getchar();
// //Retour au plateau précédent
// P[i][j]=BILLE;P[i-1][j]=BILLE;P[i-2][j]=VIDE;
// }
//coup non gagnant
}else{
//Déplacement
P[i][j]=VIDE; P[i-1][j]=VIDE; P[i-2][j]=BILLE;
//Nouveau plateau à jouer
gagnant=Jouer(billes2);
//affichage
// if(PRINT && gagnant!=0) {Draw(billes2);}
//Retour au plateau précédent
P[i][j]=BILLE;P[i-1][j]=BILLE;P[i-2][j]=VIDE;
}
if(!INFINI&&gagnant==1) {return(gagnant);} //arrêt de la recherche
} //fin Nord
++balayees;
if(balayees==billes) {return(gagnant);} //arrêt anticipé du balayage s'il ne reste plus de billes à balayer
} //fin bille
} //fin lignes
} //fin colonnes
return(gagnant);
}//fin Jouer
//Routine principale
//int main(int argc, char *argv[]) {
int main() {
int i=0,j=0;
short billes=0; //Nombre courant de billes
short gagnant=0; //etat du coup courant
SYSTEMTIME str_t;
LARGE_INTEGER freq, time1,time2;
double time;
//Calcul nb de billes
for (i=0;i<DIM;i++) {
for (j=0;j<DIM;j++) {
if(P[i][j]==BILLE) {billes++;}
}
}
GetSystemTime(&str_t);
printf("Le %2d-%2d-%4d %c %dh%d \n",str_t.wDay,str_t.wMonth,str_t.wYear,133,(str_t.wHour+2),str_t.wMinute); //Affichage de l'heure courante
printf("Resolution du plateau suivant avec %i billes\n",billes);
if(BILLESWIN==1) {printf("Pour %i bille restante en %i,%i\n",BILLESWIN,LWIN,CWIN); }
else {printf("Pour %i billes restantes\n" ,BILLESWIN); }
Draw(1); //Affichage du plateau de jeu
fflush(stdout);
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&time1);
//Résolution
gagnant=Jouer(billes);
QueryPerformanceCounter(&time2);
time = (double) (time2.QuadPart - time1.QuadPart) / (double)(freq.QuadPart);
//Calcul du nombre de déplacements
//if(PRINTDEP) {DEPLACEMENTS=MULTDEP*PRINTDEP+DEPLACEMENTS;}
if(SOL2==0) {printf("Aucune solution trouvee\n");}
else{
//if(PRINT) {Draw(billes);}
printf("%llu/%llu solution(s) trouvee(s)\n",SOL1,SOL2);
}
printf("%llu deplacements analyses en %f s (%e par s)\n",DEPLACEMENTS,time,(double) DEPLACEMENTS/time);
return 0;
} |
Aide/Conseils optimisations implémentation résolution Solitaire
Répondre avec citation
Partager