Nao résout le Rubik’s cube

Piste verte 4 janvier 2016  - Rédigé par  Aurélien Alvarez Voir les commentaires (5)

Nao est un petit robot humanoïde de 58 cm entièrement programmable. Ses capteurs et ses moteurs lui permettent d’interagir avec son environnement : il peut bien sûr se lever, marcher, parler et beaucoup plus encore [1]. Mais sait-il résoudre un Rubik’s cube ? C’est ce que nous allons lui apprendre ; ce qui nous amènera à parler d’un très bel algorithme et d’un théorème tout récent. [2]

Le Rubik’s cube ? Un casse-tête inter-planétaire s’il en est ! Casse-tête qui n’en finit pas de passionner amateurs et mathématiciens comme nous le verrons. Présentation du phénomène en quelques lignes.

  • Ce casse-tête fut inventé par Ernö Rubik en 1974. Pour la petite histoire (d’après Wikipédia) :

    L’idée initiale d’Ernö Rubik était de construire le cube afin d’amener ses étudiants à deviner quel était son mécanisme interne, comment les petits cubes pouvaient tourner suivant trois axes tout en restant solidaires, et ainsi de les faire s’intéresser à la géométrie à 3 dimensions. Ce n’est qu’ensuite qu’il eut l’idée (sur la suggestion d’un ami) de colorer chaque face d’une couleur différente, constatant alors qu’après mélange, l’ordre initial du cube s’avérait extrêmement difficile à retrouver. Il eut alors l’idée de le commercialiser en tant que « casse-tête » mathématique.

  • L’objet est constitué de $26 = 3^3 -1$ petits cubes (le mécanisme étant caché dans le petit cube central).
  • Le nombre de positions possibles pour le cube est de $43 \, 252 \, 003 \, 274 \, 489 \, 856 \, 000$. Ça fait beaucoup ! Plus de 43 milliards de milliards [3]. Une multiplication et une division plus loin pour en déduire que si vous explorez une position du cube à chaque seconde, il vous faudra environ 100 fois l’âge de l’univers pour toutes les passer en revue...

Comment arrive-t-on à ce nombre gigantesque ?

Ce nombre gigantesque s’écrit aussi $12! \times 8! \times 3^7 \times 2^{10}$. On l’obtient en raisonnant sur les permutations possibles du cube. Rappelons que le Rubik’s cube, comme tout cube, a six faces, huit sommets (ce qui définit huit coins, c’est-à-dire huit petits cubes) et douze arêtes (ce qui définit douze petites arêtes qui sont les tiers centraux des véritables arêtes du cube).

  1. On peut permuter toutes les arêtes comme on veut, ce qui donne $12!$ possibilités pour positionner les arêtes.
  2. De même on peut échanger comme on veut les coins, soit $8!$ possibilités.
  3. On a trois orientations possibles pour chaque coin. Mais on ne peut pas retourner un unique coin : l’orientation du dernier coin est donc fixée par les autres, ce qui donne $3^7$ possibilités d’orientation des coins.
  4. On a deux orientations possibles pour chaque arête. De même que précédemment on ne peut pas changer l’orientation d’une unique arête : l’orientation de toutes les arêtes fixe l’orientation de la dernière. Cela donne donc $2^{11}$ possibilités d’orientation pour les arêtes.
  5. Enfin il existe un problème de parité : on ne peut pas échanger seulement deux coins ou seulement deux arêtes (mais on peut interchanger deux coins et deux arêtes). La position des arêtes et des premiers coins fixe donc la position des deux derniers coins : il faut donc diviser le nombre de positions possibles calculées jusque-là par deux.

Les records de résolution

Le record actuel est détenu depuis le 26 avril 2015 par Collin Burns en 5,25 secondes.

La vidéo suivante montre un aperçu des derniers championnats du monde qui ont eu lieu l’été dernier à São Paulo. Attention, ça va vite !

Pas mal ! Mais peut-on faire plus rapide ? Réponse : oui ! Le record du monde absolu est détenu depuis le 15 mars 2014 par Cubestormer 3 en 3,253 secondes. Le cerveau de ce robot ARM-Powered est un Galaxy Samsung S4 et ses bras sont faits en LEGO. Attention, ça va très vite !

Mais il se pourrait bien que ce record du monde vole rapidement à son tour en éclat si l’on en croit les prouesses que semble réaliser le robot de Jay Flatlandia et Paul Rose.

Peut-on imaginer faire encore plus rapide ?

J’en ai aussitôt parlé à mon copain Nao [4]. On a travaillé dur... mais sans succès !!! Par contre on s’est bien amusé :-).

Nao, c’est donc ce petit robot humanoïde construit par la société Aldebaran Robotics [5]. Comme Nao a des petits doigts, il est difficile d’imaginer qu’il tienne lui-même le cube, encore moins qu’il puisse faire lui-même les mouvements. Par contre, contrairement à ce qu’on pourrait croire en regardant le film, Nao n’est pas aussi dur de la feuille qu’il n’y paraît ! Simplement il faut lui parler bien en face, compte-tenu de la position de ses quatre microphones qui ne sont pas dans les oreilles, mais sur la tête ! En fait Nao parle par les oreilles !

Que fait exactement Nao dans la vidéo ?

  1. Il commence par regarder chacune des six faces du cube et, pour chacune d’elles, il détecte les neuf couleurs présentes. Pour cela il commence par repérer les contours noirs entre les neuf facettes de la face qu’il regarde, et ensuite les couleurs des facettes en question [6]. Quand il a détecté les neuf couleurs présentes sur la face, il annonce la couleur de la facette centrale : on peut alors tourner [7] le cube pour lui montrer une autre face [8].
  2. Ensuite il fait le calcul qui permet de résoudre le cube [9].
  3. Enfin Nao dicte les mouvements à effectuer, il y en six possibles : haut (Up), bas (Down), gauche (Left), droite (Right), devant (Front), derrière (Back). Et pour chacun d’eux, il faut préciser de combien de quarts de tour tourner dans le sens des aiguilles d’une montre (à savoir 1, 2 ou 3) : par exemple, U2 signifie qu’il faut tourner la face du dessus de deux quarts de tour dans le sens horaire, c’est-à-dire d’un demi-tour (dans n’importe quel sens !). Il ne reste alors plus qu’à écouter et exécuter machinalement les consignes données par Nao. Sans réfléchir, comme un vrai robot !

Comment résoudre un Rubik’s cube ?

Tout ce vous avez toujours voulu savoir sur le cube sans jamais oser le demander est contenu dans un livre dont Michèle Audin parlait dans ce billet. Je vous y renvoie donc sans détour !

Le Rubik’s cube, sur le plan mathématique, c’est un superbe chapitre de théorie des groupes [10]. J’imagine cependant que la plupart des gens qui savent résoudre le cube ne pensent pas nécessairement le problème en termes de groupes, sous-groupes distingués et groupes-quotients mais sait-on jamais... Quoi qu’il en soit, l’algorithme que Nao exécute sur la vidéo précédente et que nous allons maintenant décrire dans les grandes lignes est dû à Morwen Thistlethwaite.

L’algorithme de Thistlethwaite donc est apparu au début des années 80 : il est remarquable en ce sens qu’il permet de résoudre n’importe quel cube en moins de 52 mouvements. À l’époque, ce fut une petite révolution. La mauvaise nouvelle par contre, c’est qu’il est essentiellement impossible pour un humain de l’exécuter car il engendre beaucoup trop de calculs [11]. Mais pour un ordinateur standard, ce n’est vraiment pas un problème.

JPEG - 191.3 ko
Morwen Thistlethwaite

Sur le plan théorique, l’algorithme de Thistlethwaite est vraiment un bel objet qui est resté pendant longtemps la méthode de résolution nécessitant le moins de mouvements possibles (52 donc). Les algorithmes de résolution du Rubik’s cube [12] les plus simples procèdent bien souvent en opérant sur chacun des trois étages du cube, étage par étage [13], ou alors opèrent en plaçant d’abord les coins. Ici la stratégie est bien différente et contrairement aux algorithmes les plus standards, il est difficile de se convaincre qu’on est bien en train de résoudre le cube presque jusqu’à la fin ! L’algorithme de Thistlethwaite se décompose en quatre étapes : le sel de l’affaire, c’est de restreindre progressivement les mouvements que l’on s’autorise ! Curieuse idée a priori...

  1. Tous les mouvements U, D, L, R, F, B sont autorisés.
  2. Seuls les mouvements U, D, L, R, F2, B2 sont autorisés. Autrement dit, on ne peut plus tourner les faces devant et derrière que par des demi-tours.
  3. Les mouvements autorisés sont U, D, L2, R2, F2, B2. C’est au tour des faces gauche et droite de ne plus être manipulables que par des demi-tours.
  4. On ne s’autorise plus que des demi-tours sur toutes les faces (mouvements possibles : U2, D2, L2, R2, F2, B2).

À la fin de la quatrième étape, le cube est résolu [14].

On trouve sur le web de nombreux sites et vidéos qui donnent tous les détails et permettent de bien comprendre comment fonctionne précisément l’algorithme, jusqu’à pouvoir l’implémenter dans son langage de programmation préféré. On trouve même des vidéos décortiquant la version humaine de l’algorithme, comme par exemple celle-ci.

Par ailleurs, le Rubik’s cube a des grands frères mais aussi un petit frère, le Pocket Cube, que l’on peut facilement tenir dans sa poche et qui est beaucoup plus facile à résoudre bien sûr. Cependant, c’est déjà un challenge passionnant que d’écrire un programme de résolution comme le propose Laurent Théry dans cet article publié sur Interstices.

Il est assez éclairant de formuler cela en terme de groupes et sous-groupes.

C’est quoi un groupe ? C’est d’abord un concept fondamental en mathématiques, devenu omniprésent et je vous encourage à chercher ce mot dans le moteur de recherche de ce site, les articles sur les groupes ne manquent pas !

Pour la suite, il nous suffira de savoir que c’est un ensemble de transformations d’un objet géométrique, ici notre Rubik’s cube. Dans notre cas, les transformations sont donc les rotations d’un quart de tour U, D, L, R, F, B, et toutes les transformations que l’on peut combiner à partir de ces six-là : par exemple U3D1L2 est une transformation de notre groupe, L5B7 en est une autre (qui est d’ailleurs égale à L1B3 car faire quatre fois une rotation d’un quart de tour, c’est comme ne rien faire !).

Et un sous-groupe ? C’est simplement quand on se restreint à certaines transformations. Par exemple le sous-groupe engendré par U est un sous-groupe tout petit : il ne contient que quatre transformations, à savoir U1, U2, U3 et U0 (la transformation qui ne transforme rien du tout !).

Nous en savons désormais suffisamment pour reformuler les étapes de l’algorithme de Thistlethwaite dans ce langage. Si on désigne par $G_0$ le groupe du Rubik’s cube (ce fameux groupe à 43 milliards de milliards d’éléments), ce dernier est par définition engendré par les six mouvements U, D, L, R, F, B. Notons alors

  • $G_1$ le sous-groupe engendré par U, D, L, R, F2, B2 ;
  • $G_2$ celui engendré par U, D, L2, R2, F2, B2 ;
  • $G_3$ celui engendré par U2, D2, L2, R2, F2, B2.

D’où la suite de sous-groupes suivantes
\[ G_0 > G_1 > G_2 > G_3.\]

Chaque étape de l’algorithme calcule la suite de mouvements à effectuer pour arriver dans le sous-groupe suivant. Dans la première étape donc, tous les mouvements sont autorisés : on se déplace dans le groupe $G_0$ jusqu’à arriver à une position du cube appartenant au sous-groupe $G_1$. On passe alors à la deuxième étape où on n’utilise plus que des mouvements de $G_1$ pour arriver dans $G_2$. Troisième étape vous avez compris, on n’utilise que des mouvements de $G_2$ pour arriver dans $G_3$. Dernière étape : les mouvements de $G_3$ permettent de résoudre le cube.

Penser en terme de groupes comme dans le bloc dépliant ci-dessus quand on cherche des méthodes pour résoudre un problème comme le Rubik’s cube est une idée tout à fait précieuse, avec tout un arsenal de méthodes géométriques et algébriques alors à disposition. C’est infiniment plus efficace comme on s’en doute que de chercher des combinaisons et des astuces un peu au hasard... [15] [16]

Ceci étant, en réfléchissant un peu sur des mouvements très simples, il est tout à fait possible d’inventer son propre algorithme de résolution dès l’âge de 11 ans, comme l’explique Burkard Poster (Mathologer) dans cette vidéo remarquablement claire.

Ce que font les quatre étapes de l’algorithme de Thistlethwaite.

Voici schématiquement ce qui se cache derrière chacune des étapes de l’algorithme.

  • Étape 1 : on commence par fixer les orientations des arêtes, ce qui ne sera plus possible quand les mouvements F1, F3, B1, B3 seront interdits. Le quotient $G_0/G_1$ est de cardinal $2^{11}$.
  • Étape 2 : on fixe les orientations des coins et on place les arêtes de la couche du milieu. Le quotient $G_1/G_2$ est de cardinal $3^7 \times \frac{12!}{8! 4!}$.
  • Étape 3 : on place les arêtes des faces haut et bas, les coins sont tous mis au bon endroit, et on règle les problèmes de parité sur les arêtes. Le quotient $G_2/G_3$ est de cardinal $(\frac{8!}{4!4!})^2 \times 2 \times 3$.
  • Étape 4 : on termine le travail, facile !

Sur cette page (en anglais), on peut lire une lettre écrite par Thistlethwaite et datée du 13 juillet 1981 où il décrit son algorithme. Il est amusant de lire dans les premiers paragraphes :

« I should perhaps point out that this strategy isn’t easy to perform (even John Conway finds it quite hard !), for two reasons [...] » [17]

Nous sommes donc avertis que ce n’est pas évident de comprendre tous les rouages de cet algorithme. Car John Conway, ses collègues mathématiciens le savent bien, c’est plutôt un garçon malin dont il était d’ailleurs question dans l’article récent Des jeux aux nombres surréels de Lisa Rougetet.

Le nombre de Dieu est 26

Quand on joue à un jeu comme le Rubik’s cube et qu’on finit par résoudre le cube, une question qui vient assez naturellement à l’esprit, c’est : « aurais-je pu le résoudre en moins de coups ? ». Dit autrement, s’il m’a fallu 60 mouvements pour résoudre le cube, pouvait-on le résoudre plus efficacement, disons en 30 coups ?

Petite précision : il faut maintenant dire ce qu’on entend exactement par un mouvement. En fait, il y a deux écoles... l’une est née sur la côte ouest des États-Unis avec les mathématiciens de Stanford [18] et l’autre sur la côte est avec les mathématiciens du MIT [19] :

  • l’école du demi-tour : les rotations d’un quart de tour ou d’un demi-tour (ou de trois-quarts de tour) sont considérées comme un seul mouvement ;
  • l’école du quart de tour : seules les rotations d’un quart de tour (dans un sens ou l’autre) sont considérées comme un mouvement. Une rotation d’un demi-tour correspond donc à deux mouvements.

Cette petite subtilité étant éclairée, décidons pour la suite de cet article qu’on se rallie à l’école du quart de tour : notre question initiale est désormais bien posée.

Pour les amateurs de théorie des groupes, on peut reformuler cette question à l’aide d’un graphe, c’est-à-dire d’un ensemble de sommets et d’arêtes :

  • les sommets de ce graphe sont les 43 milliards de milliards de configurations possibles pour le cube. Le cube résolu correspond à l’un des sommets et nous imaginerons que ce sommet est colorié en vert ;
  • deux sommets sont reliés par une arête si on peut passer d’une configuration à l’autre par un seul mouvement.

C’est donc un graphe gigantesque ! Je suis sûr que Poincaré n’aurait pas hésité à écrire...

« On sera frappé de la complexité de cette figure, que je ne cherche même pas à tracer. »

Quelques remarques sur ce graphe...

  • Une arête relie toujours deux sommets distincts, puisque partant d’une configuration du cube, un mouvement amène forcément à une configuration différente.
  • Partant de n’importe quel sommet, on trouve toujours des chemins constitués de quatre arêtes qui reviennent au sommet de départ, puisque faire subir au cube quatre rotations d’un quart de tour suivant le même axe et dans le même sens le laisse inchangé.
  • Le graphe est hautement symétrique : si on regarde ce qui se passe dans les voisinages de deux sommets (même très éloignés), on voit la même distribution d’arêtes et de sommets.

Le graphe que nous avons ainsi décrit porte un nom ; c’est le graphe de Cayley du groupe $G_0$ (engendré par les six mouvements U, D, L, R, F, B) [20]. Ce graphe est naturellement équipé d’une distance [21] sur les sommets : il suffit de compter le nombre d’arêtes minimal reliant les deux sommets en question. On peut alors changer légèrement notre question initiale pour la reformuler ainsi :

Quelle est la distance la plus grande possible au sommet vert ? [22] Autrement dit, quels sont les cubes « les plus mélangés » et à quelle distance sont-ils ?

PNG - 52.7 ko

En août 1998, Michael Reid a démontré que la configuration du cube ci-contre, connue sous le nom de « superflip plus fourspot », est à distance 26. Depuis lors on savait que la réponse à la question précédente était un entier plus grand que 26 [23]. Par ailleurs, puisqu’il n’y a qu’un nombre fini de configurations (43 milliards de milliards), une stratégie évidente consiste alors à considérer chaque configuration du cube et à essayer de la résoudre en moins de 26 coups. Simple sur le plan théorique... mais en pratique la remarque faite en début d’article sur « 100 fois l’âge de l’univers » est toujours d’actualité...

Malgré tout, c’est bien par la voie calculatoire que la réponse est arrivée tout récemment (août 2014) grâce aux efforts et à l’ingéniosité de Tomas Rokicki (programmeur à Palo Alto) et Morley Davidson (mathématicien à Kent State University).

Théorème

Les cubes « les plus mélangés » dans la métrique du quart de tour sont exactement à distance 26 [24].

26 ?? Incroyable car c’est...

  • le seul nombre entier qui est coincé entre un carré $25 = 5^2$ et un cube $27 = 3^3$ (voir ici pour une démonstration) ;
  • exactement le nombre de groupes sporadiques !

Quel est le rapport entre ces trois incarnations du nombre 26 ?! Probablement aucun... fin du bloc dépliant donc !

Quelle stratégie ont-ils adopté pour démontrer ce théorème ?

Diviser pour régner !

  1. Ils ont commencé par diviser astucieusement l’ensemble des 43 252 003 274 489 856 000 positions en 2 217 093 120 ensembles de 19 508 428 800 positions chacun.
  2. Avec des arguments de symétrie, ils ont réduit le nombre d’ensembles à 55 882 296.
  3. Pour chaque ensemble précédent, ils ont cherché les solutions de longueur de moins de 26 avec l’aide d’un programme, ce qui prend environ 17 secondes.
  4. Ils ont enfin utilisé la puissance de calcul d’un super-calculateur (Ohio Supercomputer Center) pour faire tourner le programme de 17 secondes sur les 55 882 296 ensembles, ce qui aurait donc pris environ 30 ans sur un seul processeur.

Le tableau ci-dessous est extrait de

http://www.cube20.org/qtm

la page web de Davidson et Rokicki concernant le théorème précédent. Elle contient d’ailleurs un historique sur les progrès accomplis autour de cette question au fil des années, de l’algorithme de Thistlethwaite (qui assurait une résolution de tout cube en moins de $104 = 2 \times 52$ mouvements dans la métrique du quart de tour) à leur théorème qui assure donc que 26 coups sont toujours suffisants.

PNG - 73.9 ko

Remarquons que la plupart des configurations du cube sont entre 19 et 22 coups. Par ailleurs, il n’y a semble-t-il qu’une seule configuration (et deux autres symétriques) à distance 26 exactement, et deux configurations à distance 25 (et leurs symétriques). Le nombre exact n’est pas encore complètement connu.

Quid de toute cette histoire dans la métrique californienne du demi-tour ? Eh bien, dans ce cas, le nombre de Dieu est de 20 [25]. C’est un théorème à peine plus vieux (juillet 2010) dû à Tomas Rokicki, Herbert Kociemba, Morley Davidson et John Dethridge. À l’époque c’est Google qui avait prêté ses gros bras pour calculer en temps raisonnable l’équivalent de 35 ans de CPU. Dans la vidéo (en anglais) ci-dessous, Morley Davidson raconte l’aventure de cette quête du nombre de Dieu ; quant à la page web du projet c’est par ici.

Post-scriptum :

Pour plein de petites vidéos sympas avec Nao, la chaîne YouTube d’Alexandre Mazel est excellente pour ça. Merci aux relecteurs dont les pseudonymes sont lafrizi et B !gre, ainsi qu’à Serge Cantat pour ces précieux conseils.

Notes

[1Du fait de sa petite taille, Nao ne peut évidemment pas tout faire. Cela étant, avec 25 degrés de liberté, quatre microphones, deux caméras HD, des senseurs tactiles et infrarouges, deux haut-parleurs... pas mal de choses sont envisageables, d’autant plus qu’il est livré avec un kit de logiciels de développement complet et compatible avec divers langages parmi lesquels Python et C++.

[2L’article est piste verte mais attention aux passages dans les blocs dépliants qui sont plutôt de type piste rouge-noire...

[3Pour mémoire, la dette de la France est, dit-on, autour de 2 000 milliards d’euros. En regard du nombre de combinaisons du Rubik’s cube, c’est vraiment pas grand-chose ;-) !

[4Un grand merci à David Filliat et au laboratoire de robotique de l’ENSTA de m’avoir prêté un robot pour l’occasion.

[5Si vous avez la possibilité de passer par Issy-les-Moulineaux, il est possible de rencontrer et jouer en vrai avec Nao ou son grand frère Pepper.

[6Avouons-le dans cette note de bas de page, c’est la partie « la moins robuste » du programme car les caméras du robot (qui ne sont pas dans les yeux - j’espère que vous l’aviez deviné - mais dans la bouche et sur le front !) sont très sensibles aux variations de lumière. Lorsque l’on calibre les couleurs, c’est bien entendu sous une certaine lumière et avec un certain cube. Dès que la lumière est sensiblement différente, la détection des couleurs n’est pas toujours évidente... C’est l’occasion pour moi de remercier Alexandre Mazel qui m’a donné un coup de main salvateur sur ce coup.

[7N’importe comment ? Pas si sûr... les faces lui sont en fait montrées dans un ordre bien déterminé.

[8La partie traitement d’images a essentiellement été réalisée via la bibliothèque OpenCV.

[9En vrai, il se connecte à un serveur (qui peut être un ordinateur sur son réseau local ou une autre machine quelque part sur internet), lui transmet la configuration du cube et attend quelques instants que la réponse soit calculée. Le calcul prend à peine quelques secondes sur un ordinateur standard mais l’algorithme qui est exécuté est hautement récursif. L’accès à la mémoire sur le robot étant plutôt lent (le processeur et la mémoire du robot n’ont pas été conçus pour faire de lui un super-calculateur), il vaut mieux éviter de lui demander de faire le calcul lui-même (au risque de devoir patienter plusieurs heures...).

[10Wikipédia illustre d’ailleurs son article sur les groupes par un Rubik’s cube.

[11Ryan Heise a proposé une version pour humain de l’algorithme, voyez ici.

[12voir la page Wikipédia du cube pour une liste des plus classiques

[13On fait très facilement un premier étage sans aucune formule, c’est déjà un premier exercice pour qui tient un Rubik’s cube mélangé la première fois dans ses mains...

[14On peut vérifier que les règles précédentes sont vérifiées dans la séquence filmée ci-dessus puisque le robot dicte : R2 - U1 - D1 - B1 - B2 - R1 - L1 - F2 - U1 - B2 - U3 - B2 - R1 - U2 - B2 - U1 - L2 - U3 - F2 - U1 - F2 - U1 - R2 - B2 - R2 - F2 - U2 - F2 - U2 - B2 - R2 - D2 - L2.

[15Dans cette direction, on pourra lire l’article Un peu de géométrie des groupes de Gilbert Levitt paru dans les temps préhistoriques d’Images des maths.

[16On me tweete dans l’oreillette qu’un MOOC intitulé Groupes finis : les mathématiques du Rubik’s cube proposé par Pierre Guillot et Viktoria Heu commencera le 22 février prochain. Le public concerné est large : étudiants en licence scientifique, lycéens motivés en terminale S, amateurs de puzzles en tout genre — et même les mathématiciens confirmés désireux d’apprendre à utiliser le logiciel GAP.

[17« Je devrais mentionner que cette stratégie n’est pas facile à mettre en œuvre (même John Conway la trouve difficile !), pour deux raisons [...] »

[18un peu rebelles forcément !

[19rigoureux comme il se doit !

[20Le groupe $G_0$ opère naturellement dans ce graphe, ce qui explique que ce dernier soit hautement symétrique.

[21invariante par l’action du groupe $G_0$

[22Dans son jargon, un groupiste (i.e. un théoricien des groupes), se serait demandé : « quel est le diamètre de ce graphe ? »

[23Remarque importante : pour montrer qu’un cube est résoluble en moins de 26 coups, il « suffit » de trouver un enchaînement de 26 coups qui le résout. Par contre, calculer la distance au cube non mélangé (le sommet vert), c’est beaucoup plus difficile car si vous avez résolu le cube en 22 coups, il se pourrait très bien qu’on puisse le résoudre en 17 coups peut-être...

[24Dans les jeux mathématiques comme les casse-têtes combinatoires, il semble courant de parler de nombre de Dieu ou algorithme de Dieu pour faire référence à un nombre de coups minimal ou à l’algorithme le plus efficace. On peut cependant émettre quelques doutes sur le choix de cette terminologie...

[2520 $\leq$ 26, tout va bien :-)

Partager cet article

Pour citer cet article :

Aurélien Alvarez — «Nao résout le Rubik’s cube» — Images des Mathématiques, CNRS, 2016

Commentaire sur l'article

  • Nao résout le Rubik’s cube

    le 4 janvier à 17:31, par ROUX

    43252003274489856000 vaut, à mieux que 5% près, 71,7 micromoles.
    Pour un chimiste, ce n’est vraiment rien : 71,7micromoles de silicium (tiens, mais pourquoi donc le silicium :) ?) ont une masse de 2,02 milligrammes.
    Pfouiouffff...

    Répondre à ce message
    • Nao résout le Rubik’s cube

      le 14 janvier à 10:01, par Lhooq

      Pour un informaticien ça fait :

      $100101100000111101111110111101000110111000000000000000000000000000$

      alors que $2^{64}$ c’est :

      $10000000000000000000000000000000000000000000000000000000000000000$

      Donc $2^{64} - 1$ :

      $1111111111111111111111111111111111111111111111111111111111111111$

      Donc on ne peut même pas le représenter avec les entiers des architectures modernes sur 64 bits.

      On parle vraiment de micromoles :D

      Répondre à ce message
  • Nao résout le Rubik’s cube

    le 18 janvier à 13:17, par Mateo_13

    Bonjour,

    je vous signale la publication d’une vidéo de Burkard Polster (Mathologer) sur une solution du Rubik’s cube et les groupes finis, accessible à un enfant de 11 ans (plus ou moins) :
    https://youtu.be/-NL76uQOpI0

    Amicalement,
    — 
    Mateo.

    Répondre à ce message
    • Nao résout le Rubik’s cube

      le 18 janvier à 13:57, par Aurélien Alvarez

      Merci beaucoup pour cette vidéo. Je n’ai pas résisté à la rajouter à mon article car on m’a demandé plusieurs fois des vidéos élémentaires pour résoudre un cube, sans que je sache en donner d’aussi plaisantes que celle-ci.
      Bien cordialement, Aurélien.

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM