Programmation autours d'un jeu

[lepatagon]

Bonjour,
Je recherche un programmeur qui pourrait m’aider a faire tourner un ptit programme au sujet d’un jeu.
Ce jeu se nomme KHALOU et est disponible gratuitement sur Itunes pour Iphone et Ipad.
https://itunes.apple.com/fr/app/khalou/id589404904?mt=8
Je vous laisse en lire les règles. Voici mes requêtes :
Il existe pour ce jeu 2^16 = 65536 positions différentes.
Les jetons de ce jeu peuvent se retourner de différentes façons. Je cherche un petit script a faire tourner qui pourrait me donner :
*Pour chacune des positions : le nombre de retournement minimum pour rendre le damier du jeu tout blanc (le but du jeu). Cela est toujours faisable en 5 retournements minimum (démontré via théorie des groupes).
*Trouver ainsi le nombre totale de positions résolvables en : 1, 2, 3, 4 et 5 retournements minimum.

Qui pourrait m’aider pour cette programmation ?
****************************

Regles : Le Khalou est un jeu de plateau 4X4 comportant des jetons bifaces (noires et blanches).

Le principe du jeu est le suivant :

*Le jeu débute par une répartition aléatoire des jetons (et de leurs faces visibles) sur le plateau
*Le but est de parvenir en une succession de mouvements différents à un plateau de jeu tout blanc (tous les jetons avec leurs faces visibles blanches).

*2 Types de mouvements principaux sont autorisés :

*Retournement des faces visibles sur une ligne, colonne, ou grande diagonale. Dans ce cas chacun des 4 jetons sur toute la ligne, colonne ou diagonale sélectionnée voit sa face visible changer de couleur.




*Retournement des faces visibles sur « un coude » : le coude est une position en « L » impactant 3 jetons dans n’importe quelle direction. Chacun des 3 jetons sélectionnés par ce retournement voit ainsi sa face visible changer de couleur.


Le but du jeu du Khalou est donc de rendre blancs tous les jetons uniquement grâce à ces types de retournements. Cela est toujours possible en 5 retournements maximum.

**************************************

Idee d'algorithme :

Il existe 2^16-1 positions = 65.535. En effet on ne compte pas la position avec jetons tout blancs.
*On peut représenter chaque position par un nombre de 16 chiffres composé de 0 ou de 1 (0 = blanc et 1 = noir) et faire tourner toutes les possibilités. En ne comptant pas celle composée de 16 chiffres 0.
*Il existe 46 mouvements possibles. Chaque mouvement permet de changer 3 ou 4 chiffres du nombre désignant la position initial. Par exemple si les couleurs des 16 jetons sont représentées dans le chiffres de gauche a droite et de haut en bas alors le retournement de la ligne du haut change les 4 premiers chiffres du nombre a 16 chiffres représentant la position d’origine.
Ainsi si la position d’origine est : 1000.1100.0001.1010 retourner la première ligne aboutit à la position notée : 0111.1100.0001.1010
Ou si la position d’origine est : 1000.1100.0001.1010 retourner le premier coude aboutit à la position notée : 0100.0100.0001.1010
Le but étant avec un minimum de retournements d’aboutir au chiffre : 0000.0000.0000.0000
*Il suffit alors de faire tourner les 65.535 positions et pour chacune d’elles de modifier le chiffre de cette position avec les 46 puis 46^2 puis 46^3 puis 46^4 retournements possibles.
Quand le chiffre 0000.0000.0000.0000 apparait (cela arrivera plusieurs fois souvent) on note le nombre de retournements minimum utilisés. Sinon c’est qu’il eut fallu 5 retournements.
Ce n’est de loin pas le meilleur algorithme mais selon moi le plus simple.

D’autres idées ????

[Lolo78]

Alors, à vue de nez, sur une position de départ donnée, il y a 5 puissance 46 parties possibles. C'est énorme (environ 1,4 x 10 puissance 32), il n'est sans doute pas possible d'examiner toutes les parties possibles dans un temps raisonnable. L'approche force brute ne marche donc sans doute pas. Il faut donc trouver des moyens d'élaguer rapidement et à chaque étape les mouvements non rentables, pour que l'arbre des possibilités reste raisonnable.

Mais il faut se méfier, il semble très possible que, dans certains cas, la solution optimale passe par une augmentation initiale du nombre des pions noirs, en vue de les réorganiser pour rendre les coups suivants plus efficaces. Un peu comme le joueur de dames qui donne des pions "à manger" à son adversaire pour mieux le surprendre en fin de compte, ou comme les très bons joueurs de Rubik's Cube qui développent des stratégies "non progressives" (quatre coups avant la fin, on n'a pas vraiment l'impression d'avoir progressé).

Hmmm, le sujet me paraît intéressant, et il y a même peut-être des aspects théoriques à creuser, mais je n'ai pas trop le temps de travailler sur ce genre de truc en-dehors des week-ends.

[lepatagon]

Je ne suis pas d'accord, je dirais plutot 46 puissance 5.
Et en partant du principe nque 2 retournements identiques s'annulent il faut au max 46*45*44*43*42 retournements.

De plus comme on sait que tout est resoluble en 5 retournements max il ne faut pour chacune des 64.000 positions traiter que 46*45*44*43 enchainements possibles et retenir celui qui occasionne le moins de retournements.

[Lolo78]

Envoyé par lepatagon

Je ne suis pas d'accord, je dirais plutot 46 puissance 5.

Exact, je me suis misérablement planté.

Mais ça fait tout de même presque 206 millions de possibilités.

Envoyé par lepatagon

Et en partant du principe nque 2 retournements identiques s'annulent il faut au max 46*45*44*43*42 retournements.

Deux retournements identiques ne s'annulent réellement que s'ils sont consécutifs. Ils ne s'annulent pas si une ou plusieurs pièces concernées ont été retournées entre temps pa.

Envoyé par lepatagon

De plus comme on sait que tout est resoluble en 5 retournements max il ne faut pour chacune des 64.000 positions traiter que 46*45*44*43 enchainements possibles et retenir celui qui occasionne le moins de retournements.

[Lolo78]

Envoyé par lepatagon

Je ne suis pas d'accord, je dirais plutot 46 puissance 5.

Exact, je me suis misérablement planté.

Mais ça fait tout de même presque 206 millions de possibilités (pour chacune des 65-k positions de départ).

Envoyé par lepatagon

Et en partant du principe nque 2 retournements identiques s'annulent il faut au max 46*45*44*43*42 retournements.

Deux retournements identiques ne s'annulent réellement que s'ils sont consécutifs. Ils ne s'annulent pas si une ou plusieurs pièces concernées ont été retournées entre temps par un autre coup.

Envoyé par lepatagon

De plus comme on sait que tout est resoluble en 5 retournements max il ne faut pour chacune des 64.000 positions traiter que 46*45*44*43 enchainements possibles et retenir celui qui occasionne le moins de retournements.

46*45*44*43 enchainements possibles? Pourquoi pas 46*45*44*43*42? Il est tout de même utile de savoir quel(s) enchaînement(s) conduisent à une solution, non? De plus, si l'on ne trouve pas de solution pour une position de départ donnée, alors on sait que le programme a un bug, ce qui n'est pas inutile à savoir. En revanche, il est vrai que l'on peut arrêter le parcours de l'arbre s'il reste plus de 4 pions noirs après le quatrième coup (ou plus de 8 après le troisième coup), ce qui peut alléger assez nettement le nombre de solutions à tester.

L'algorithme peut être très simple en principe, la seule chose un peu casse-pieds est de coder la liste des coups possibles.

Mais je persiste à penser qu'il faut penser à des stratégies d'optimisation pour réduire le nombre de solutions à visiter.

[Philou67430]

Cependant, les 206 millions de combinaisons ne seront pas appliquées pour toutes les grilles, puisqu'un certains nombre ne nécessiterons que 1, 2, 3 ou même 4 retournements (206M est un max)

La force brute se programme facilement : si le temps est trop long pour obtenir le résultat, il est possible d'envisager des heuristiques ou des stratégies de recherche (comme prioriser certains mouvement pouvant mener plus vite au résultat, notamment par exemple, choisir tout de suite le bon retournement pour des matrices où seul un retournement est nécessaire, ce qui élague des tas de cas/sous cas).

[Philou67430]

Bon, après quelques essais, la force brute trouve bien des résultats, mais les premiers trouvés ne sont pas optimaux... Si l'on ne veut donc pas parcourir toutes les combinaisons comme je l'indiquais dans mon post précédent, il est donc impératif d'utiliser une stratégie particulière pour trouver les mouvements minimaux.

Donc j'ai dit n'importe quoi. Je suppose qu'il s'agit d'un exercice de math ou d'algorithmique ?

[trex7g2]

Une façone diminuer drastiquement le nombre de solutions dans ce jeu est de supprimer toutes les situations équivalentes par symétrie... Par exemple :

1010
0010
0110
0101

est la même chose que :

0001
1100
0111
1000

qui est la même chose que :
1000
0011
1110
0001

etc...

pour chaque plateau, on peu le tourner de 90°, ou faire des symétries horizontales et verticales.

ça doit diminuer drastiquement ton nombre de cas.

Dans le même genre, je me demande ce qui serait le plus rentable entre
1/ tester tous les coups possibles afin de résoudre une étape
2/ avoir en mémoire toutes les possibilités à 1 coups en mémoire

Par exemple si tu as toutes les possibilités après un coup, tu n'as plus "qu'à atteindre une de ces possibilités en 4 coups etc...

Tu as dis que tu avais très peu de coups possibles. Il me sembles assez facile de comparer 40 nombres.

[lepatagon]

la deuxieme option me semble bien plus interessante

[Lolo78]

Je verrais bien une attaque en sens inverse. Recenser (dans un hash, par exemple) toutes les situations solubles en un coup. Puis toutes les situations permettant d'arriver à ces situations en un coup, et ainsi de suite. Ainsi une heuristique des meilleurs coups pour chaque situation.

[trex7g2]

De manière générale il me semble que deux approches sont possibles pour la résolution de cet algorithme :

La première serait de partir de la solution, de faire tous les mouvements possibles, recenser les solutions dans une hash, puis faire un deuxième mouvement. La difficulté serait ici de minimiser le nombre de mouvements que l'on tente aux tours suivants le premier. La hash permettrait par exemple de "mémoriser" les coups menant a cette solution. L'avantage, c'est que l'on a au maximum 65k arrangements au tour 4, donc 65k*42 opérations à faire pour analyser les arrangements au tour 5 (on a moins de 1 million d'opérations à faire au final, ce qui est acceptable je pense... Et ça peut se programmer assez salement )

Une deuxieme approche serait un peu plus combinatoire. En gros l'idée serait d'utiliser les symétries des différents mouvements pour diminuer les calculs. Par exemple, tous les coups ont un correspondant en faisant une symétrie à 90°

Ensuite il "suffit" de faire une matrice avec les différents mouvements, et de résoudre toutes les combinatoires etc... Ca n'est probablement pas très dur à programmer, et surement assez rapide, mais l'algo derrière demande des connaissances qui me dépassent un peu...

[Lolo78]

Trouver des situations symétriques (ou équivalentes d'une autre façon) à une situation existante n'est pas trop difficile, détecter que deux situations données sont symétriques ou équivalentes est à mon avis plus ardu. C'est du moins ce que j'avais bien vite constaté quand j'avais eu le même problème à résoudre pour un solveur de Sudoku que je m'étais amusé à faire il y a quelques années. Les modélisations "computionellement" efficaces pour analyser les situations et parcourir les arbres de possibilités ne se prêtent généralement pas si facilement à l'étude des symétries et autres équivalences de situations. Mais il est peut-être possible de trouver une modélisation plus efficace que celles auxquelles j'ai pensé.

Je reste sur l'idée que remonter depuis la solution vers les 65-k situations de départ doit je pense éviter l'explosion exponentielle d'autres méthodes envisageables.

[Lolo78]

Je pense qu'il faut travailler en vrai binaire (et non avec des chaînes de caractères de 0 et de 1), le travail est bien plus simple. Comme on ne manipule pas trop souvent le binaire en Perl, voici quelques astuces obtenues après quelques essais.

Les situations de départ possibles peuvent être simplement modélisées par les 2^16 premiers nombres. Exemple avec seulement les 32 premiers nombres:

Code :

printf "%05b ", $_ foreach 0..31;

Ce qui imprime:

Code :

00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111

Pour afficher "proprement" avec 16 chiffres binaires, il suffit de remplacer "%05b " par "%016b ", ce qui donne:

Code :

0000000000000000 0000000000000001 0000000000000010 0000000000000011 0000000000000100 (etc.)

Les coups possibles doivent également être codés en binaire.

Par exemple, les retournements de la première rangée, de la seconde, de la troisième et de la quatrième peuvent être respectivement codés ainsi:

Code :

1
2
3
4
$coup[1] = 0b1111000000000000; # ou 61440
$coup[2] = 0b0000111100000000; # ou 3840
$coup[3] = 0b0000000011110000; # ou 240
$coup[4] = 0b1111; # ou 15

Si maintenant je prends la position 0000000000000100 (soit 4 en décimal) et que je lui applique le coup 3 ci-dessus, ceci se fait simplement en faisant un ou exclusif entre la position d'origine et le coup:

Code :

$resultat = 0b0000000000000100 ^ $coup[3];

Ce que je peux aussi bien écrire:

Code :

$resultat = 4 ^ 240;

Ce qui me donne dans ce cas la position 244:

Code :

printf  "%016b", $resultat;

Soit:

Code :

0000000011110100

.

L'utilisation du ou exclusif est très intéressante puisque, outre sa rapidité, on peut l'utiliser aussi bien pour descendre l'arbre des coups que pour le remonter: si j'ai une position et un coup, le ou exclusif me donne aussi bien le résultat du coup sur la position donnée que la position de départ pour laquelle le coup donné me donnera la position donnée.

Donc, si je pars de la solution (0000000000000000) et veux trouver toutes les positions d'origine pour lesquelles les quatre coups listés ci-dessus mènent à la solution, il me suffit de faire quelque chose comme cela:

Code :

printf "%016b\n", $solution ^ $_ foreach @coup

;

ce qui m'imprime:

Code :

1
2
3
4
1111000000000000
0000111100000000
0000000011110000
0000000000001111

ce qui paraît tout-à-fait correct.

Pour moi, une fois ces menues difficultés techniques clarifiées, la solution est maintenant évidente.

Il faut encore:
- coder le tableau des 46 coups possible (et pas seulement 4 comme ci-dessus); c'est sans doute ce qu'il y a de plus pénible, mais pour 46 coups, ça devrait aller;
- Implanter un tableau des 65k+ positions possibles, afin de marquer au fur et à mesure toutes celles déjà trouvées (pour ne pas se répéter et s'arrêter à chaque fois dès que possible)
- Implanter un tableau de tableaux pour répertorier la série de coups nécessaire pour chaque position de départ
- Mettre en œuvre un algo de parcours en largeur d'abord de l'arbre des coups possibles.

L'avantage de la solution est que l'on parcourt certes les 206 millions de possibilités, mais on ne le fait qu'une seule fois (et non 65.000 fois). C'est donc tout-à-fait jouable dans un temps très limité.

Voilà, j'ai toutes les cartes en main, et vous aussi, pour coder la solution. A vue de nez, à part la définition des coups possible, ça tient facilement en moins de 30 lignes de code.

Il se fait tard et j'arrête pour ce soir. Je n'aurai sans doute pas le temps de me pencher à nouveau là-dessus avant sans doute demain soir. Que celle ou celui qui veut proposer une solution basée sur mes propositions ci-dessus soit bienvenu(e), je n'ai pas de copyright là-dessus (ce que j'écris ici est du domaine public) et j'ai fait ce post dans le seul but d'aider celle ou celui qui désire s'y mettre. Si personne ne le fait, j'espère proposer la solution dès que j'aurais le temps de m'y remettre. A mon avis, une ou deux heures de codage devraient suffire, mais, bon, pas sûr, je suis parfois trop optimiste sur ce genre d'estimations.

[Lolo78]

Je poursuis sur les opérations et les affichages, avec cette fois 10 coups (rangées, colonnes et diagonales).

Code :

1
2
3
4
5
my @coup =  (0b1111000000000000, 0b0000111100000000, 0b0000000011110000, 0b1111); # rangées
push @coup, (0b1000100010001000, 0b0100010001000100, 0b0010001000100010, 0b0001000100010001); #colonnes
push @coup, (0b1000010000100001, 0b0001001001001000); # diagonales 
my @results;
push @results, sprintf  "%016b\n", $solution ^ $_ foreach @coup;

Ce qui me donne:

Code :

1
2
3
4
5
6
7
8
9
10
1111000000000000
 0000111100000000
 0000000011110000
 0000000000001111
 1000100010001000
 0100010001000100
 0010001000100010
 0001000100010001
 1000010000100001
 0001001001001000

Je peux obtenir un affichage plus "parlant" des positions obtenues avec un peu de reformatage:

Code :

foreach (@results) {  s/(\d{4})/$1\n/g ; print}

Ce qui me donne:

Code :

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
1111
0000
0000
0000
 
0000
1111
0000
0000
 
0000
0000
1111
0000
 
0000
0000
0000
1111
 
1000
1000
1000
1000
 
0100
0100
0100
0100
 
0010
0010
0010
0010
 
0001
0001
0001
0001
 
1000
0100
0010
0001
 
0001
0010
0100
1000

[Lolo78]

Voici maintenant les 46 coups codés en binaire:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
my @coup =  (0b1111000000000000, 0b0000111100000000, 0b0000000011110000, 0b1111); # rangées
push @coup, (0b1000100010001000, 0b0100010001000100, 0b0010001000100010, 0b0001000100010001); #colonnes
push @coup, (0b1000010000100001, 0b0001001001001000); # diagonales
push @coup, (0b1100100000000000, 0b1100010000000000, 0b0110010000000000, 0b0110001000000000, 
		     0b0011001000000000, 0b0011000100000000); # L avec centre première rangée
push @coup, (0b1000110000000000, 0b0100110000000000, 0b0100011000000000, 0b0010011000000000, 
		     0b0010001100000000, 0b0001001100000000); # L avec centre deuxième rangée, vers haut
push @coup, (0b0000110010000000, 0b0000110001000000, 0b0000011001000000, 0b0000011000100000, 
		     0b0000001100100000, 0b0000001100010000); # L avec centre deuxième rangée, vers bas
push @coup, (0b0000000011001000, 0b0000000011000100, 0b0000000001100100, 0b0000000001100010, 
		     0b0000000000110010, 0b0000000000110001); # L avec centre troisième rangée, vers bas
push @coup, (0b0000100011000000, 0b0000010011000000, 0b0000010001100000, 0b0000001001100000, 
		     0b0000001000110000, 0b0000000100110000); # L avec centre troisième rangée, vers haut
push @coup, (0b0000000010001100, 0b0000000001001100, 0b0000000001000110, 0b0000000000100110, 
		     0b0000000000100011, 0b0000000000010011); # L avec centre dernière rangée, vers haut

Un affichage du tableau trié et en décimal me permet de vérifier que je n'ai pas de doublons:

Code :

1
2
15 19 35 38 49 50 70 76 98 100 140 196 200 240 304 560 608 784 800 1120 1216 1568 1600 2240 3136 3200 3840 4369 4680 4864 8738 8960 
9728 12544 12800 17476 17920 19456 25088 25600 33825 34952 35840 50176 51200 61440

Soit dit en passant, maintenant que j'ai l'expression décimale des 46 coups possibles, il est plus facile d'initialiser les 46 coups possibles:

Code :

1
2
3
@coup = qw /15 19 35 38 49 50 70 76 98 100 140 196 200 240 304 560 608 784 800 1120 1216 
             1568 1600 2240 3136 3200 3840 4369 4680 4864 8738 8960 9728 12544 12800 17476 
             17920 19456 25088 25600 33825 34952 35840 50176 51200 61440 /;

Si je fais un affichage plus "parlant" de mes 46 coups":

Code :

1
2
@e = map { sprintf "%016b\n", $_} @coup;
s/(\d{4})/$1\n/g and print foreach @e;

cela me donne:

Code :

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
0000
0000
0000
1111
 
0000
0000
0001
0011
 
0000
0000
0010
0011
 
0000
0000
0010
0110
 
0000
0000
0011
0001
 
0000
0000
0011
0010
 
0000
0000
0100
0110
 
0000
0000
0100
1100
 
0000
0000
0110
0010
 
0000
0000
0110
0100
 
0000
0000
1000
1100
 
0000
0000
1100
0100
 
0000
0000
1100
1000
 
0000
0000
1111
0000
 
0000
0001
0011
0000
 
0000
0010
0011
0000
 
0000
0010
0110
0000
 
0000
0011
0001
0000
 
0000
0011
0010
0000
 
0000
0100
0110
0000
 
0000
0100
1100
0000
 
0000
0110
0010
0000
 
0000
0110
0100
0000
 
0000
1000
1100
0000
 
0000
1100
0100
0000
 
0000
1100
1000
0000
 
0000
1111
0000
0000
 
0001
0001
0001
0001
 
0001
0010
0100
1000
 
0001
0011
0000
0000
 
0010
0010
0010
0010
 
0010
0011
0000
0000
 
0010
0110
0000
0000
 
0011
0001
0000
0000
 
0011
0010
0000
0000
 
0100
0100
0100
0100
 
0100
0110
0000
0000
 
0100
1100
0000
0000
 
0110
0010
0000
0000
 
0110
0100
0000
0000
 
1000
0100
0010
0001
 
1000
1000
1000
1000
 
1000
1100
0000
0000
 
1100
0100
0000
0000
 
1100
1000
0000
0000
 
1111
0000
0000
0000

Un coup d'oeil rapide semble indiquer que tous les coups sont bien légaux. Donc, a priori, pas d'erreur dans l'initialisation des coups.

Soit dit en passant, ces 46 coups représentent aussi accessoirement les 46 positions solubles en un seul coup.

[Lolo78]

@Lepatagon: deux petites questions.

1. Voilà plus de trois jours que l'on ne t'a pas revu ici. Ça ne t'intéresse déjà plus?

2. Tu veux vraiment explorer le jeu, ou c'est un devoir scolaire qui a été donné?

Les réponses aux deux questions sont d'ailleurs peut-être liées. Tu devais peut-être rendre le devoir pour jeudi ou vendredi, du coup ça ne t'intéresse plus?

Bien sûr, je me trompe peut-être complètement (et je souhaite que je me trompe), mais bon, admets qu'il y a lieu de se poser ces questions...

[Lolo78]

Hum, bon, toujours pas de nouvelles ni de réponse du Patagon...

Donc, en l'absence de réponse, je vais m'abstenir pour l'instant de fournir le code de ma solution, mais me contenterai de donner mes résultats:

Code :

1
2
3
4
5
6
il y a 1 positions solubles en 0 coups.
il y a 46 positions solubles en 1 coups.
il y a 987 positions solubles en 2 coups.
il y a 10680 positions solubles en 3 coups.
il y a 39067 positions solubles en 4 coups.
il y a 14755 positions solubles en 5 coups.

Ce qui donne bien au total 65.536 solutions solubles entre 0 et 5 coups (y compris la solution triviale déjà résolue, soluble en 0 coup). L'algorithme utilisé garantissant que chaque position répertoriée est différente, tout indique que le programme est correct et qu'il confirme que toutes les positions de départ sont bien solubles en 5 coups maximum.

Le programme s'exécute en moins de 3 secondes sur mon PC portable (pas une bête de course et pas un modèle particulièrement récent puisqu'il date de mi 2008), la solution retenue est donc largement assez efficace, me semble-t-il. Une méthode partant en sens inverse de toutes les positions de départ possibles aurait sans doute nécessité deux ou trois jours de calcul, je pense.

Si l'on met de côté les initialisations et les déclarations initiales, la partie du programme exécutant l'ensemble des calculs comprend trois boucles imbriquées et tient en 11 lignes de code Perl (sans aucun effort de rendre le code particulièrement concis, au contraire, j'ai recherché la clarté).

J'avais annoncé une ou deux heures de codage en précisant que j'étais peut-être optimiste; ben oui, j'étais optimiste puisque ça m'a pris environ 3 heures à cause de deux petites erreurs stupides qu'il m'a fallu du temps à corriger. A regarder la simplicité de la solution finale, franchement, j'ai un peu honte d'avoir pris autant de temps: en réfléchissant bien et en étant bien concentré, ça doit pouvoir être fait en moins d'une heure, je pense. En même temps, j'ai travaillé dessus en deux jours après 23h30 (et après, dans les deux cas, deux ou trois bons verres de vin au dîner). Le matin à jeun en une seule fois, ça aurait sans doute été plus efficace). ;-)

Bien sûr, je fournirai sans problème mon code à quiconque inscrit sur ce forum avant la mi-février de cette année me le demande.

[trex7g2]

Jolie solution! La mienne était un peu plus sale vu que je n'ai pas l'habitude de faire du binaire... Je restais en décimal et je faisais un tr/2/0/.

Tu as déjà fourni une bonne partie du code, et presque toute la réflexion qu'il y a derrière. Lepatagon devrait s'en sortir si c'était un projet sur plusieurs semaines .

[Lolo78]

Le truc qui me satisfait réellement dans l'algorithme de ma solution, c'est qu'en remontant depuis la solution (tous les pions blancs, ou 0) vers les positions de départ possibles, je peux éliminer rapidement toutes les solutions non optimales (par exemple, si j'arrive à une position donnée en deux coups, pas besoin de voir si un autre chemin menant à cette même position en 3 coups a de l'intérêt pour la suite, je peux l'éliminer très tôt dans le processus et ne plus m'y intéresser). Résultat: sur les 206 millions de groupes de 5 coups possibles, mon algorithme n'en examine réellement que 2.335.926 (ce n'est pas un calcul théorique, j'ai ajouté un compteur pour le vérifier). Et, au final, l'algo n'examine réellement jusqu'au bout que 65535 chemins.

L'algorithme élimine donc très efficacement le risque d'explosion combinatoire (malgré ses trois boucles imbriquées).

[Philou67430]

Bien joué, je dirais