| Un bref rappel du jeu : |
On dispose de 6 nombres ou chiffres tirés au hasard parmi :
On tire au hasard un nombre compris entre 100 et 999.
Le but est alors d'atteindre ce nombre en utilisant les 6 nombres précédents avec les quatre opérations arithmétiques élémentaires :
C'est tout, enfin tout le monde connaît j'imagine...
| Applet JAVA (pour jouer en ligne) : |
| Résolution du jeu : |
En 1994, je me suis intéressé comment résoudre ce célèbre jeu complètement : c'est a dire sans omettre la moindre solution quelque soit le nombre de chiffre utilisé dans la résolution.
Par exemple, on peut utiliser les 6 chiffres ou nombres pour atteindre une solution mais 4 ou 5 sont souvent suffisants.
Parfois même, on a une solution en utilisant 5 nombres uniquement mais aucune en utilisant 6 nombres : cas rares je dois dire mais qui sont déjà tombés dans le jeu télévisé lui-même.
A cette époque, je regardais sur mon ordinateur les tirages du jeu télévisé
qui posaient problème aux candidats et même à Bertrand Renard le
spécialiste du jeu.
Conclusion : Rares sont les tirages du jeu télévisé sans solution.
Il existe plusieurs algorithmes pour obtenir des solutions :
| Premier Algorithme (récursif) : |
On dispose de 6 plaques {p1,p2,p3,p4,p5,p6}, on choisit 2 plaques parmi ces 6 plaques :
Il y a donc 
= 6x5/2 = 15 combinaisons :
{(p1,p2),(p1,p3),(p1,p4),(p1,p5),(p1,p6),(p2,p3),(p2,p4),(p2,p5),(p2,p6),(p3,p4),(p3,p5),(p3,p6),(p4,p5),(p4,p6),(p5,p6)}
Pour chacun des couple (pi,pj), on dispose des 4 opérations arithmétiques.
La soustraction et la division n'étant pas commutative, il faut aussi penser à l'inverse :
pi - pj et aussi pj - pi
pi / pj et aussi pj / pi
Remarque :
p1 + p2 = p2 + p1 (commutativité de l'addition)
p1 x p2 = p2 x p1 (commutativité de la multiplication)
En y regardant de plus près, seules les valeurs positives nous intéressent :
Hors si p1 - p2 > 0 alors p2 - p1 < 0
Et si p1 - p2 > 0 alors p1> p2 et p2 / p1 n'existe pas (valeur non entière).
On peut donc tester le couple (pi,pj) et faire ensuite la soustraction
qui est positive :
pi - pj ou pj - pi.
Si la soustraction est nulle, on peut éliminer le calcul, la valeur nulle ne pouvant nous
aider dans la recherche de solutions.
On fait de même la division pi / pj ou pj / pi suivant le test.
Ce qui ramène le couple (pi,pj) à quatre opérations arithmétiques (la multiplication
et surtout la division étant les plus coûteuses).
Si pi ou pj dans la multiplication (ou la division) est de valeur 1, alors pi x pj = pi ou pj
(pi / pj = pi si pj = 1) et donc
ces opérations ne font pas avancer le calcul et la recherche de solutions :
On peut donc éliminer ces cas également.
Si la division n'existe pas dans N, ce qui est très fréquent, on évite une opération de plus, ce qui
donne en tout moins de 4 opérations en moyenne par couple (pi,pj).
On a donc 15 couples (pi,pj), et au plus 4 opérations pour chacun de ces couples, soit au plus 60 opérations pour les 2 premières plaques.
Supposons l'opération pi + pj :
La valeur calculée peut être considéré comme une nouvelle plaque.
On se retrouve alors avec le même problème mais avec 5 plaques et non plus avec 6 (2 plaques remplacées par le résultat de l'opération entre ces 2 plaques).
C'est donc là que la récursivité intervient :
On dispose désormais de 5 plaques, on choisit 2 plaques parmi ces 5 plaques :
il y a donc 
= 5x4/2 = 10 combinaisons.
Si par exemple p1 et p2 étaient les 2 premières plaques utilisées et si p1 devenait le résultat de la première
opération de p1 et p2, on a ces 10 combinaisons :
{(p1,p3),(p1,p4),(p1,p5),(p1,p6),(p3,p4),(p3,p5),(p3,p6),(p4,p5),(p4,p6),(p5,p6)}
On fait le même raisonnement avec 4 plaques, 3 plaques, puis 2 plaques.
Dès qu'il ne reste plus qu'une seule plaque, on remonte dans l'algorithme récursif.
A chaque niveau de récursion, on vérifie si le résultat de l'opération faite au niveau de récursion précédent n'est pas le résultat qu'on cherche (simple test sur la nouvelle plaque issue des 2 anciennes : si p1 est toujours le résultat de l'opération précédente, on teste simplement si p1 est le résultat qu'on cherche).
On peut calculer la complexité de cet algorithme dans le pire des cas :
x 4 x x 4 x 
x 4 x 
x 4 x 
x 4 = 15 x 4 x 10 x 4 x 6 x 4 x 3 x 4 x 1 x 4 = 15 x 10 x 6 x 3 x 45 =
En plus, l'expérience par le calcul montre même que
Ces suppressions d'opérations dans la recherche divisent presque par trois la recherche dans certains cas
(les meilleurs) !
Le pire des cas tel qu'il est envisagé est en plus très improbable, même inexistant vu les critères mis en jeu !
Graphe de l'algorithme :
Ce graphe illustre le fonctionnement de l'algorithme récursif :
Programme en c :
Source (DOS/Windows/Linux 16/32 bits) : compte.c
Exécutable (DOS/Windows 16/32 bits) : compte.exe
Version plus rapide avec un chronomètre intégré :
Source (Windows 32 bits) : wcompte.c
Exécutable (Windows 32 bits) : wcompte.exe
Remarque :
On peut facilement enlever la récursivité de l'algorithme pour l'optimiser un peu
en faisant simplement un parcours en profondeur du graphe de manière non récursive.
| Deuxième Algorithme : |
On va ici envisager plusieurs cas :
Avec 2 plaques :
Si on ne dispose que de 2 plaques, on ne peut faire que l'opération :
pi * pj = R1 (PP)
* 
{+, x, -, /}
i,j {1,2,3,4,5,6}
PP signifie : Plateau * Plateau (opération sur 2 nouveaux plateaux)
RP signifie : Plateau * Résultat (opération sur un nouveau plateau avec le résultat précédent)
RR signifie : Résultat * Résultat (opération sur les 2 résultats précédents)
Remarque :
Pour simplifier (cf. premier algorithme), on traite (i,j) et (j,i) en même temps, c'est à dire que c'est
pi - pj ou pj - pi (respectivement pi / pj ou pj / pi) qui sont calculés :
On s'intéresse donc aux couples (i,j) avec = 6x5/2 = 15 couples (i,j),
Cette remarque est valable pour les autres cas (3 plaques, 4 plaques, 5 plaques ou 6 plaques) :
Dès qu'une opération entre 2 plaques pi * pj intervient, on s'intéresse aux couples (i,j)
qui vérifient
On reprend également les remarques du premier algorithme
sur les multiplications et divisions avec au moins une opérande à 1 et les soustractions nulles : on les évite.
La complexité de ce premier cas ou schéma de calcul est donc de 15 x 4 =
Avec 3 plaques :
Le (seul) schéma est le suivant :
pi * pj = R1 (PP)
R1 * pk = R2 (RP)
On choisit 2 plaques parmi les 6 :
= 15 couples (i,j)
pk peut prendre une des valeurs des 6 - 2 = 4 plaques restantes.
La complexité dans le pire des cas de ce schéma de calcul est donc de 15 x 4 x 42 =
Avec 4 plaques :
Il existe deux schémas avec 4 plaques :
= 15 couples (i,j) = 6 couples (k,l) = 15 couples (i,j)
La complexité dans le pire des cas de ces deux schémas de calcul est donc de
Avec 5 plaques :
Il existe trois schémas avec 5 plaques :
= 15 couples (i,j) = 3 couples (l,m) = 15 couples (i,j) = 6 couples (k,l) = 15 couples (i,j)
La complexité dans le pire des cas de ces trois schémas de calcul est donc de
Avec 6 plaques :
Il existe six schémas avec 6 plaques :
= 15 couples (i,j) = 6 couples (k,l) = 1 couple (m,n) = 15 couples (i,j) = 3 couples (l,m) = 15 couples (i,j) = 3 couples (l,m) = 15 couples (i,j) = 1 couples (m,n) = 15 couples (i,j) = 6 couples (k,l) = 15 couples (i,j)
La complexité dans le pire des cas de ces six schémas de calcul est donc de
Chaque cas pourra être traité comme dans le premier algorithme de manière récursive, les deux algorithmes étant alors assez proche. On suit les schémas précédents pour chacun des cas.
La complexité dans le pire des cas de ce deuxième algorithme est donc de :
60 + 960 +
Comparées au
L'expérience montre que le nombre d'appels à la fonction récursive
du deuxième algorithme est environ deux fois moins grand que le nombre d'appels à la fonction récursive
du premier algorithme :
Les fonctions récursives de ces deux algorithmes étant assez proches, le temps d'exécution est environ deux fois moins grand pour le deuxième algorithme.
Programme en c :
Source (DOS/Windows/Linux 16/32 bits) : compte2.c
Exécutable (DOS/Windows 16/32 bits) : compte2.exe
Version plus rapide avec un chronomètre intégré :
Source (Windows 32 bits) : wcompte2.c
Exécutable (Windows 32 bits) : wcompte2.exe
Remarque :
Comme pour le premier algorithme, on peut facilement enlever la partie récursive de l'algorithme
pour l'optimiser un peu en faisant simplement un parcours en profondeur du graphe de manière non récursive.
| Programme : |
Mon programme COMPTE résout ce jeu intégralement.
Il est basé sur le deuxième algorithme.
Il peut bien-sûr résoudre d'autres cas que ceux présentés dans le jeu télévisé : à savoir n'importe quel tirage à trouver compris entre 1 et 65535 avec n'importe quel nombre compris entre 1 et 255 en utilisant les 4 opérations.
Ce programme datte un peu : 1995 mais il a été entièrement écrit en assembleur (TASM) et fait moins de 9 KO.
La vitesse de résolution est donc impressionnante sur des
Intel Pentium III et autres processeurs récents en comparaison avec mon
Intel 486 DX 33 que j'utilisais entre 1992 et 1996 : le programme tournait déjà rapidement
alors maintenant...
Il fonctionne sur DOS et donc aussi sur WIN95,WIN98 et WINME :
Mode d'emploi :
Malgré l'interface sur DOS, je ne penses pas qu'on puisse faire beaucoup
plus simple
:
est rouge :
vous indiquent quelle solution vous souhaitez changer.
où le 7 indique qu'il y a 7 solutions distinctes en utilisant 6 nombres
(ou plaquettes). 
Vous pouvez recommencer un autre tirage en appuyant sur ESCAPE.
Quitter le programme en réappuyant sur ESCAPE.
| Conclusion : |
Voila bonne utilisation...
Vos remarques sont les bienvenues à : eternitygames@free.fr
Je ferais bientôt un applet JAVA basé sur
le deuxième algorithme (plus rapide) pour que cela fonctionne aussi en ligne.
Mise à jour Septembre 2001 : l'applet JAVA est en ligne,
vous pouvez maintenant jouer sur la page directement !
