Eternity II : 2 000 000 $, mais à quel prix ?
Vous êtes ici : Accueil / Articles / Formations en Algorithmique
Qu’est-ce qu’Eternity II
Eternity II est un jeu de puzzle créé par Christopher Monckton, dont la résolution entraîne une récompense de 2 000 000 $ au premier qui la trouvera.
Le puzzle est composé de 256 pièces avec divers motifs. Il faut réussir à créer un carré de 16 pièces par 16 avec une correspondance des motifs.
Le grand argument commercial du jeu est son accessibilité à tout le monde : n’importe qui peut trouver la solution. En effet, il lui suffit d’arriver à poser chaque pièce au bon endroit. Il existe même des milliers de solutions.
Pourtant, malgré la simplicité de ses apparences, il apparaît rapidement que ce jeu nécessite des compétences en mathématiques, en algorithmique et en informatique.
Un peu de dénombrement...
Pour savoir à quoi l’on s’engage, il est nécessaire d’avoir préalablement estimé le pourcentage de chances de réussites. Quelques calculs mathématiques ne tarderons pas à nous renseigner :
Nous disposons de 256 pièces, que nous pouvons positionner dans 4 orientations différences chacune.
Pour poser la première pièce, nous aurons 
solutions possibles. Pour la seconde, 
( la 256ème pièce ayant déjà été posée ). Nous voyons donc clairement que le nombre total de combinaisons est
où ! signifie la factorielle. Le résultat est
11 501455 970687 482978 298441 855589 188472 895357 340951 272684 430125 523610 016220 906942 793907 867076 793100 926389 379381 434261 416478 269087 586750 169406 787981 182826 309991 100282 450226 986376 790065 980826 771352 447149 852163 096272 169781 850274 729686 973259 777192 684170 955424 317990 375850 768358 283328 930609 312491 673026 631857 012057 959935 704204 380176 289796 896791 328839 235834 992649 908036 710612 680895 565575 778805 513082 266092 563606 109355 222363 716489 595650 750572 911297 305667 668195 883200 401491 094208 054978 465610 034146 265769 803158 933291 635166 357023 361314 365890 301804 659414 182975 634197 604255 209345 432109 134179 376903 261036 117753 856000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
Il va sans dire qu’un amateur n’aura qu’un nombre minime de chances de trouver la solution. Il est humainement impossible de la trouver sans avoir recours aux mathématiques et à l’informatique.
Les limites de l’informatique
Les ordinateurs sont toujours plus performants et les calculs sont de plus en plus court. Cependant, pour un nombre de combinaisons de cette ampleur, il est impensable de tester les solutions par de la force brute.
Il existe d’autres algorithmes permettant de réduire considérablement le nombre d’essais, notamment le backtracking. Bien qu’améliorant considérablement les performances, même en calcul distribué, cette solution a encore très peu de chances d’aboutir devant la puissance de calcul que cela représente.
Les mathématiques entrent en jeu
Pour pallier aux limites de l’informatique, il est alors nécessaire de se tourner vers des solutions mathématiques. Ce jeu est basé sur "deux aspects plutôt obscurs des mathématiques" (Christopher Monckton) : l’analyse combinatoire et les probabilités.
L’idéal serait bien évidemment de trouver une solution mathématique qui mène droit vers les solutions. Il n’existe à ce jour aucun moyen de résolution directe et il faudra attendre probablement longtemps avant d’en obtenir un, s’il existe.
Il faut donc se rabattre sur un objectif plus accessible : trouver une astuce mathématique qui réduise suffisamment le nombre d’essais pour que cela devienne exécutable par un ordinateur en un temps raisonnable.
Mais alors, inutile de chercher ?
Si les chances de trouver une solution "à la main" sont minimes, elles ont du moins le mérite d’exister. Les algorithmes actuels permettent d’augmenter la probabilité de trouver, mais elle reste encore petite face aux nombres de combinaisons possibles. Enfin, en dehors de l’appas du gain, il est toujours agréable de chercher des solutions pour le plaisir.