20 est le nombre de Dieu… au Rubik’s Cube
C’était il y a trente ans. Sous le sapin du Noël 1980 m’attendait un cadeau infernal : un cube à 6 faces de couleurs différentes, chacune décomposée en 9 pastilles carrées. Le cube du Hongrois Ernö Rubik venait de faire son entrée dans mon existence, tout comme il allait hanter des centaines de millions de foyers à la surface du globe. Je n’eus pas la ténacité de ce Britannique qui employa vingt-six années de sa vie à résoudre ce casse-tête sans la moindre aide et la solution me fut donnée par mon prof de maths de quatrième, sous la forme de quelques pages découpées dans une revue scientifique. Certes, il me fallut apprendre des formules absconses par cœur mais ce n’était pas si difficile que cela, surtout si l’on mettait en regard de cet effort l’aura que me valut le pouvoir presque magique de refaire ce maudit cube… Et puis, comme dans Toy Story 3, le jouet finit par me tomber des mains et rejoindre les jolis fantômes de mon enfance.
Puisque le temps passe, lorsque j’ai eu à mon tour des enfants, un Rubik’s Cube est réapparu chez moi. Bien sûr, j’avais oublié les deux tiers de mes formules. Il a donc fallu que je me documente pour, de nouveau, passer pour un dieu, cette fois aux yeux de mes fils. Ce qui m’a permis de découvrir des méthodes de résolution plus simples que la mienne ainsi que… les maths cachées derrière ce casse-tête. Surtout, j’ai appris qu’une énigme plus forte que le Rubik’s Cube lui-même résistait depuis des années aux chercheurs : quel était le nombre maximum de mouvements à effectuer pour reconstituer le cube, quelle que soit la position de départ ? Cette question pourra sembler complètement futile mais il s’agit en réalité d’un défi sérieux posé à une branche des mathématiques appelée théorie des groupes.
Pendant trente ans, elle a tenté de trouver la valeur de ce nombre maximal, surnommé le nombre de Dieu. Et elle vient d’y parvenir. Il faut dire que le travail était titanesque. Imaginez-vous qu’il y a exactement 43.252.003.274.489.856.000 positions de départ possibles. Si vous avez du mal à lire des nombres aussi longs, c’est plus de 43 milliards de milliards de positions. A côté de cela, le nombre de combinaisons à Euro Millions est ridiculement petit : 76.275.360, soit 567 milliards de fois moins… Evidemment, pour les chercheurs qui s’intéressaient au nombre de Dieu, pas question de vérifier les possibilités une par une.
Il leur fallait donc surmonter deux obstacles : le premier, purement mathématique, consistait à réduire le nombre de positions pertinentes (beaucoup de positions sont les miroirs des autres) et à élaborer un algorithme capable de calculer le nombre de mouvements nécessaire pour recomposer le cube ; le second, purement technique, à trouver assez de “temps d’ordinateur” pour faire tourner l’algorithme. Le mathématicien Morley Davidson, l’ingénieur John Dethridge, le professeur de mathématiques Herbert Kociemba et le programmeur Tomas Rokicki viennent d’y parvenir. Le nombre de Dieu est 20. Quelle que soit la position de départ du cube, il faut, en théorie, au maximum 20 coups de poignet pour que les six faces retrouvent leur uniformité de couleur. En réalité, de 16 à 19 mouvements suffisent la plupart du temps mais, pour 100 à 300 millions de positions, 20 sont nécessaires.
Pour obtenir ce résultat, le quatuor cité plus haut a divisé les quelque 43 milliards de milliards de combinaisons en 2.217.093.120 ensembles contenant chacun 19.508.428.800 positions. Puis, ils ont réduit le nombre d’ensembles à 55.882.296, en exploitant les symétries et les recouvrements d’ensembles. Ils ont ensuite écrit un programme qui parvenait à résoudre un ensemble en 20 secondes environ sur un bon ordinateur portable (4 cœurs, 2,8 GHz, pour les puristes qui ne manqueront pas de me le demander si je ne leur fournis pas ce détail). Mais il y avait comme un hic. Comme un rapide calcul le montre, même en ne prenant que 20 secondes pour chaque ensemble de 19,5 milliards de positions, avec 55.882.296 ensembles, il faut… 35 ans pour faire le tour de la question ! C’est là que John Dethridge a été utile. Il faut préciser que cet homme est ingénieur chez Google et que sa société possède beaucoup, mais alors beaucoup, d’ordinateurs. En répartissant la tâche sur plusieurs machines, le temps de calcul a été ramené à quelques semaines.
Il n’est pas sûr que ces travaux soient très utiles, en pratique, aux champions du Cube. D’autant que ceux-ci se sont déjà empiriquement rapprochés de Dieu. Les techniques actuelles de résolution nécessitent une trentaine de mouvements, voire moins. Le record du monde de rapidité est un époustouflant 7,08 secondes, réalisé par le Néerlandais Eric Akkersdijk en 2008. A savourer ci-dessous, même si la vidéo est de piètre qualité.
Pierre Barthélémy
16 commentaires pour “20 est le nombre de Dieu… au Rubik’s Cube”
Abonnement aux flux
N’est-ce pas plutôt le nombre +minimum+ de mouvements nécessaires pour résoudre le cube ?
En ce qui me concerne, je peux faire des centaines de mouvements, et je ne résous toujours rien.
Et il est facile de rajouter des mouvements inutiles pour rendre leur nombre infini.
Tout dépend évidemment de la manière dont on voit les choses… Le but du jeu est de trouver le chemin le plus rapide vers la solution. Dans cette optique, le maximum de mouvements est 20.
Non non, il s’agit bien du nombre “maximal” de mouvement.
Il faut le comprendre comme ceci : “Quelque soit la configuration de départ, une personne ou un ordinateur qui résout le puzzle en le nombre minimum de mouvements fera au maximum 20 mouvements”.
Ce chiffre ne dépend pas de la personne qui le résout puisqu’on sait qu’il fera toujours le nombre minimum de mouvements, mais bien de la configuration de départ.
Pour prendre un exemple plus simple, ou plus compréhensible :
Supposons que vous vouliez ouvrir votre porte dont le verrou est apparent (c’est important).
Dans cette situation, vous êtes très à l’aise (une sorte de champion imbattable d’ouverture de porte 😉 ) :
– Si le verrou est fermé, vous le voyez et vous l’ouvrez avant de tirer la poignée (2 mouvements).
– S’il est ouvert vous tirez simplement la poignée (1 mouvement seulement).
Le nombre maximum de mouvements nécessaires à l’ouverture de la porte est donc de 2 quelque soit la configuration de départ (verrou ouvert ou verrou fermé).
Pour le Rubiks cube, la grosse difficulté est l’immensité des configurations de départ.
J’espère que c’est plus clair pour vous. 🙂
“programmateur Tomas Rokicki” : on dit programmeur, les programmateurs sont pour les machines à laver.
La réponse était bien évidemment….. 42 !!!!!
Le nombre de dieu, la réponse ultime à la Grande Question de la VIe, de l’Univers et du Reste est 42, pas 20.
N’importe quoi, ces chercheurs en carton….
En réalité, les deux s’emploient ( cf http://atilf.atilf.fr/dendien/scripts/tlfiv5/advanced.exe?8;s=3125108385; ), mais il est vrai que “programmeur” prête moins à confusion. J’ai donc corrigé.
“Quelle que soit la position de départ du cube, il faut, en théorie, au maximum 20 coups de poignet pour que les six faces retrouvent leur uniformité de couleur.”
Je pense que c’est clair
Moi j’ai toujours demonté mon Rubik’s cube pour le finir.
Ca prend environ une minute, il faut une outil type tourne vis et sans doute pas plus de 20 manipulations…
CQFD
[…] …AFPLe Rubik's Cube peut être résolu en 20 coups ou moinsGizmodoAbondance (Blog) -Slate.fr -nouvo.ch27 autres […]
bb
Soit C une configuration du cube. Soit X(C) le nombre de coups minimums pour finir le cube.
X(C) est majoré par 20 et la majoration est atteinte pour certaines configurations..
C’est ce qu’ils ont prouvé informatiquement
L’explication de la porte est super claire : il manque juste le mot “nécessaires” dans le paragraphe 2 de l’article (quel était le nombre maximal de mouvements nécessaires) pour qu’on puisse comprendre à la première lecture.
Merci en tous cas pour cet article très évocateur de nos pérégrinations rubistikes !!!!
Bonjour,
Jamais pu finir ce foutu carré, moins matheux, plus illogique que moi tu meurs….
Merci pour cet article je pense avoir compris
sauf que dieu n’existe pas donc 20=0 cqfd !
Wouarf… Je n’ai jamais réussi à m’intéresser à ce truc ch*** comme la pluie. Il y a tellement de choses mille fois plus passionnantes à faire! :oD
Mais en plus appeler ça “le nombre de dieu”… ça relève vraiment de la folie des grandeurs (megalomania maxima!) hahaha!!!
Tous des gamins, ces matheux ! :oP
Merci Pierre pour l’explication sur le minimum et le maximum, je comprends mieux.
Mais in fine, en quoi le nombre maximum du minimum est-il plus “intéressant” que le minimum du minimum, qui est (à mon avis de béotien qui n’est pas foutu de faire une seule face en moins de 40 mouvements) beaucoup plus parlant ?
(ma parole, je découvre au passage que je ne suis pas loin d’être un champion d’ouverture de porte)(sauf que j’ai souvent un troisième coup avant les deux autres : j’essaie d’abord d’ouvrir la porte et je constate alors qu’elle est fermée…) :•)