Combien faut-il de mouvements pour résoudre un cube ?

Si résoudre les cubes de dimension 3 consiste à utiliser la force brutale, alors le Sphinx joue au cube et s'est cassé le nez !

La théorie

Pour passer d'une position à la suivante, il y a 18 possibilités : horaire, anti-horaire et double tour pour les 6 faces. On ne compte pas le mouvement des couches du milieu pour éviter les invariances par rotation.

• R = right, droite
• L = left, gauche
• F = front, face
• B = back, arrière
• U = up, dessus
• D = down, dessous

PS: 18 moins le coup opposé à celui qu'on vient de faire, mais on peut se tromper...

Mathématiquement, il faut 23 mouvements au plus pour résoudre un cube traditionnel. Dans la pratique, il suffit souvent de 18 mouvements. Cela représente donc 18^18^ mouvements, autrement écrit 4.10^22^.

Attention, il ne s'agit pas du dénombrement des combinaisons visuelles possibles du cube. Il existe des mouvements qui s'annulent, donc certaines combinaisons peuvent ne pas être testées.

Des algorithmes de résolution existent, dont celui de Herbert Kociemba implémenté dans le logiciel Cube Explorer 4.64 qui fonctionne très bien.

Pour autant, la méthode brutale reste utile. Supposons qu'on ne sache pas résoudre le cube à la main. En implémentant un algorithme brutal, on peut deviner bêtement quelles sont les formules magiques pour passer d'un état A à B : 8 coups en général, soit 11 milliards de possibilités.

Exemple simple

Mélange : L2 F2 R2 B2 F2 R2 F2 R2 Résolution : R2 F2 R2 F2 B2 R2 F2 L2

Exemple compliqué

Mélange : B2 F2 L2 U2 F2 D B' U2 L2 D' U2 F' R' F L D L' U Résolution : U' L D' L' F' R F U2 D L2 U2 B D' F2 U2 L2 F2 B2

L'utilisation de la méthode humaine donne entre 60 et 100 coups. Ceci est la majoration de la réponse à la question soulevée dans ce billet.

Posté par admin le 11 juin 2010 à 18:50 - Sciences
Texte soumis à la licence du site, sauf mention contraire
Rechercher plus d'informations

Commentaires

Evaluer l'article :

Ajouter un commentaire