Les mathématiques du rubik's cube

Dénombrement

Calcul du nombre de combinaisons possibles pour un rubik's cube

Le rubik's cube est composé de 12 arêtes et 8 coins et de 6 centres. On va prendre les centres comme point de repère, de plus une rotation sur lui même d'un centre n'a aucune conséquence sur le cube, on ne va donc pas les considérer.

  • Les 12 arêtes peuvent chacunes s'orienter dans deux directions. La direction de la dernière arête est fixée par la direction des arêtes précédentes, cela nous donne donc 211 possibilités d'orientations des arêtes.
  • Les 8 coins peuvent chacun s'orienter dans trois directions. La direction du dernier coin est fixée par la direction des coins précédents, cela nous donne donc 37 possibilités d'orientations des coins.
  • Les 12 arêtes peuvent se répartir dans 12 emplacements. Cela nous donne donc 12! possibilités de placement des arêtes.
  • Les 8 coins peuvent se répartir dans 8 emplacements. Cela nous donne donc 8! possibilités de placement des coins. Mais il n'est pas possible d'échanger 2 coins ou deux arêtes seulement (mais il est possible d'échanger deux coins ET deux arêtes seulement), les derniers deux coins n'ont donc pas deux solutions pour se placer mais une seule et le resultat est divisé par deux. On va répercuter cette division par deux dans le 211 qui va devenir 210 .

On arrive donc a un total de 12!*8!*37 *210 = 479 001 600 * 40 320 * 2 187 * 1 024 = 43 252 003 274 489 856 000
Pour info, la décomposition en facteurs premier donne : 227 *314 *53 *72 *11 = 134 217 728 * 4 782 969 * 125 * 49 * 11 = 43 252 003 274 489 856 000
En francais, ce nombre est : quarante-trois milliards deux-cents cinquante-deux millions trois-mille deux-cents soixante-quatorze de milliards quatre-cents quatre-vingts-neuf millions huit-cents cinquante-six mille.

Certains rubik's cubes ont des dessins sur les faces. L'orientation des centres devient alors importante et il faut multiplier le resultat précédent par 2*45 = 211 = 2 048 car l'orientation du dernier centre est fixée par celle des autres centres au demi-tour près. On arrive donc à 12!*221 *8!*37 = 479 001 600 * 2 097 152 * 40 320 * 2 187 = 88 580 102 706 155 225 088 000

Calcul du nombre d'algorithmes en n coups

Le rubik's cube possède 6 faces qui peuvent être tournées dans un sens, dans l'autre, et faire des demis tours. Cela nous fait donc 6*3 = 18 coups existants. Mais lorsqu'on a tourné une face, on aboutit à rien si on retourne cette face. Il faut donc qu'après le premier coup, on se limite à 18-3 = 15 possibilités de rotations. Le nombre d'algorithmes en n coups est donc de 18*15 n . Autant dire que l'arrivée des ordinateurs dans le monde du rubik's cube a permis une très nette avancée dans la découverte des algorithmes intéressants. Il est aussi à noter que beaucoups de ces algorithmes peuvent revenir au même, notamment les algorithmes de periode 2 et leur inverse et tous les algorithmes dans lesquels ils sont inclus et les algorithmes équivalents. Ce calcul n'a donc aucun lien avec le nombre de positions différentes que vous atteindrez en n coups, mais le nombre de façons différentes que vous aurez à votre disposition pour les atteindre.

 

Notions mathématiques sur les algorithmes

Périodicité des algorithmes

TOUS les algorithmes quels qu'ils soient sont periodiques. La periode d'un algorithme est le nombre de fois que vous devez faire cet algorithme pour revenir à votre position de départ. La periode d'un algorithme ne dépend que de l'algorithme.

La notion de periodicité va prendre tout sont intérêt combinée avec la notion d'inversibilité. Le fait que tous les algorithmes soient periodiques vient du fait que le rubik's cube a un nombre fini de possibilités (voir partie dénombrement).

Exemple d'algorithme de periode 2. On voit bien que quand cet algorithme est appliqué deux fois, on revient à la position de départ.


Inversion des algorithmes

Ici aussi, tous les algorithmes sont inversibles. Un algorithme est l'inverse d'un autre, si quand on effectue les deux à la suite, on retombe sur sa position de départ. On peut donc noter que les algorithmes de periode deux sont inverses d'eux mêmes, mais ceci est un cas particulier.

Tous d'abord, avant ces explications, mettons nous d'accord sur les notations. si a est un algorithme, a' est sont inverse. Si a et b sont deux algorithmes, on note ab le fait de faire ces deux algorithmes à la suite. On peut écrire les proprietés suivantes :

  1. a'' = a, a est donc l'inverse de a'.
  2. L'inversion des mouvements de base est la suivante : (L)' = L' (d'ou la notation), L''=L (voir proprieté 1) et L2' = L2 (voir dernière 6, L2 est de periode 2).
  3. ab diffère de ba. Prenons comme exemple a = R et b = F pour faire simple. RF diffère de FR. Ceci revient à dire que l'ordre dans lequel vous tournez les faces a de l'importance.
  4. (ab)' = b'a', ceci revient à dire que si vous avez fait RF, il vous faudra faire F'R' pour revenir à votre point de départ.
  5. On déduis des deux précédentes que (ab)' est different de a'b'
  6. Si a est de periode n, a n-1 = a'

Pratiquons un peu car ces considérations mathématiques doivent vous paraitre abstraites. Prenons par exemple l'algorithme a = R2U2R2U2. Cet algorithme est de periode 3. On a donc a2 = R2U2R2U2R2U2R2U2 = a'. Mais, en inversant cet algorithme avec la propriété 4, on obtient a' = U2R2U2R2, qui aura le même effet que R2U2R2U2R2U2R2U2, mais sera bien plus vite executée.
Cette propriété est très utilisée en speedcubing, nottament avec certainnes PLL.


Algorithmes mirroirs ou symétriques

Le rubik's cube, comme son nom l'indique,est un cube, et a donc de nombreux axes de symétrie. Trois symétries vont nous intéresser ici, d'autres existent, mais ne sont pas intéressante humainement parlant, de plus, la méthode sera la même pour ces symétries, donc si vous vous y intéressez ce document devrait être suffisant.

Symetrie selon X
Symetrie selon Y
Symetrie selon Z

De plus, on peut noter que la symétrie X peut facilement se convertir en symétrie Y de la façons suivante :

Position de base

La position de base.

Symetrie selon X

La position mirroir selon X.

Symetrie selon X transformé en symetrie selon Y

Revient à la position mirroir selon Y si l'on fait un demi-tour de 180°.


Les algorithmes symétriques ont deux utilitées. Si la position est déjà symétrique, faire l'algorithme symétrique revient au même résultat. Cela sert en speedcubing à exécuter les algorithmes des cas symétriques avec la main la plus rapide. Une deuxième utilité est de pouvoir résoudre deux cas symétriques en n'apprenant qu'un seul algorithme.

Tout ça c'est bien beau, mais comment crée-t-on un algorithme mirroir ? Les néophites pourront se référer au tableau ci-dessous, mais très vite, cela vous semblera intuitif (normalement).

Faces UU'U2 RR'R2 LL'L2 FF'F2 BB'B2 DD'D2
 
Symétries XU'UU2R'RR2L'LL2B'BB2F'FF2D'DD2
YU'UU2L'LL2R'RR2F'FF2B'BB2D'DD2
ZU'UU2F'FF2B'BB2R'RR2L'LL2D'DD2

Comment ce tableau est-il remplis ? Ca n'est pas compliqué, il y a deux règles pour trouver la face qu'on va tourner et dans quel sens. Concernant le sens, c'est très facile : c'est toujours dans le sens inverse au sens d'origine. Concernant la face à tourner, c'est un peu plus délicat, c'est la face qu'on obtient par symétrie par rapport à l'axe choisis, mais je vous conseille de regarder comment ça se passe sur votre cube, c'est beaucoup plus simple à comprendre qu'une tartine de texte.

A gauche, deux algorithmes symétriques selon Z. La situation est symétrique, on va donc choisir l'un ou l'autre en fonction de la rapidité avec laquelle on va l'exécuter. Ceci n'a d'intérêt qu'en speedcubing.

A droite, deux algorithmes symétriques selon Y. Ils permettent de résoudre deux cas symétriques. Savoir faire le mirroir d'un algorithme permet de ne pas avoir à en apprendre trop.


NB : Dans la methode de Fridrich ou de Petrus, les réflexions selon Z servent lors de la résolution des deux premières couronnes, alors que les réflexions selon X et Y servent à faire la dernière face.

NB : Le cas d'une symétrie par rapport à une droite n'est pas traité ici, mais il est déductible : une symétrie par rapport à une droite est en fait une symétrie par rapport à un plan, puis par rapport à un autre. Enfin, la symétrie par rapport à un point est une symétrie par rapport à une droite et par rapport à un plan dans lequel la droite n'est pas contenu.

Conservativité des algorithmes.

Ca y est, on sort les mots barbares. En fait ça n'est pas très compliqué. La conservativité d'un algorithme est ce qu'il ne va pas changer dans le cube. On va donc chercher à n'utiliser que des algorithmes conservatif de ce qu'on a déjà construit dans le cube quand on va le résoudre. Par exemple, tous les algorithmes utilisée lors de la dernière étape de la méthode Fridrich sont conservatifs de l'orientation des cubes, mais non de leur position.

En général, plus un algorithme est conservatif, plus il est long. C'est pourquoi on va utiliser des algorithmes qui ne sont conservatif que de ce qu'on a déjà construit dans le cube. En blindfold, le problème est différent. Comme on ne peut pas regarder le cube entre chaques étapes de la résolution, on se doit d'utiliser des algorithmes qui sont conservatifs de tout, sauf de ce qu'on veut leur faire faire en particulier.

Les deux algorithmes ci-contre ont le même effet sur l'orientation des coins. L'un est conservatif de la position, l'autre non. L'algorithme conservateur est utilisé en blindfold, il existe d'autres algorithmes qui ont le même effet et qui sont conservateurs en moins de mouvement, mais ils sont plus difficiles à exécuter les yeux fermés.