Analyse mathématique du Rubik's cube

Le Rubik's Cube, c'est quoi ? Un jouet, un casse-tête, ou un objet mathématique ??

A première vue, c'est tout bête : un cube de 56 mm de côté, formé de 27 de cubes colorés. A chacune des faces, on peut faire subir une rotation, mélanger ainsi en quelques secondes et inextricablement toutes les couleurs. Inoffensif ? Méfiez-vous ... Quand vous l'aurez pris, vous ne pourrez plus lâcher. Et ses 43 milliards de milliards de combinaisons ont de quoi vous faire perdre la boule !

L'objet n'a l'air de rien : un cube de plastique tout simple ; 6 faces, 9 carrés de couleur sur chaque face ; tous les carrés peuvent changer de position, à l'exception de ceux qui occupent le centre de chaque face. Au départ, chaque face est unicolore. Mais attention ! Il suffit de quelques rotations effectuées au hasard sur les faces pour transformer ce bel ordre en un inextricable fouillis de couleurs. Le but du jeu étant, bien sûr, de rétablir l'ordre initial.

Voilà pour l'invention. L'inventeur ? Ernö Rubik, hongrois, sculpteur et architecte, professeur à l'Ecole des Arts décoratifs de Budapest. Signes particuliers : grand amateur d'échecs, n'est pas particulièrement doué pour les mathématiques ...

Mais qu'a-t-il donc de spécial ce cube ?

D'abord son mécanisme, aussi simple qu'ingénieux. Chaque face peut tourner sur elle-même, autour d'un axe passant par son centre. De sorte que le carré central d'une face occupe toujours la même position par rapport aux autres faces (même s'il pivote sur lui-même). En revanche, les quatre petits cubes qui forment les coins d'une face, tout comme les quatre qui forment ses bords (les arrêtes) sont déplacés à chaque rotation de la face.

Toutes les transformations que l'on peut faire subir au Rubik's Cube sont basées sur le même mouvement élémentaire : une rotation de 90 degrés soit un quart de tour, dans le sens des aiguilles d'une montre ou dans le sens contraire, imprimée à l'une quelconque des six faces. Comme chacun de ces mouvements élémentaires modifie la configuration du cube, et que l'on peut réaliser des séries de tels mouvements aussi longues que l'on veut, le nombre de configurations possibles est immense.

Combien exactement ? Pour le savoir, il faut introduire quelques notions mathématiques. Tout d'abord, appelons permutation toute manipulation que l'on peut effectuer sur le cube, c'est-à-dire toute suite finie de rotations élémentaires. D'une manière générale, une permutation est une opération qui modifie l'ordre d'un ensemble fini d'objets : écrire les lettre de l'alphabet à l'envers (z, y, x, w ... ), battre un jeu de cartes, par exemple. Les permutations sur un ensemble donné forment ce que l'on appelle un groupe. En mathématiques, les groupes de permutations jouent un rôle essentiel pour certains problèmes : c'est, par exemple, en s'appuyant sur leurs propriétés qu'Evariste Galois a pu démontrer, au 19 ème siècle, que l'équation du cinquième degré n'était pas soluble par radicaux.

Remarquons maintenant que calculer le nombre de configurations possibles du Rubik's Cube revient à calculer le nombre de permutations. Précision : si deux suites distinctes de rotations élémentaires produisent le même effet, elles définissent la même permutation ; il est évident qu'il y a une infinité de telles suites, mails il est tout aussi évident que le cube ne peut prendre qu'un nombre fini de configurations (puisqu'il y a un nombre fini de faces, un nombre fini de petits carrés (les facettes) sur chaque face, un nombre fini de couleurs pour chaque facettes).

Permutations et transpositions

Considérons le cube dans sa position de départ. Pour chacune de ses configurations possibles, il existe une permutation qui fait passer le cube de sa position initiale à cette configuration. Inversement, chaque permutation est parfaitement définie par l'effet qu'elle produit sur la position de départ. Il y a donc exactement autant de permutations que de configurations accessibles à partir de la position de départ (la « permutation identique », en abrégé I, est celle qui laisse le cube inchangé).

Pour calculer le nombre de permutations du Rubik's Cube, il faut regarder d'un peu plus près ce qui se passe lorsqu'on fait tourner les faces colorées. La première idée qui vient à l'esprit est qu'exception faite des facettes centrales (entendons par facette chacun des petits carrés qui constituent une face), toutes les facettes se meuvent indépendamment les unes des autres et peuvent donc prendre n'importe quelle couleur. La réalité est un peu plus subtile.

Considérons, pour commencer, une rotation élémentaire appliquée à la face supérieure du cube, disons un quart de tour dans le sens des aiguilles d'une montre. Qu'advient-il des coins ? Appelons A l'un quelconque des coins de la face supérieure, B, C et D les autres (toujours dans le sens des aiguilles d'une montre). La rotation d'un quart de tour déplace le petit cube qui occupait la position A en B, le coin B en C, C en D, D en A. Mais, chose importante, les coins restent des coins. Pour les bords, on a un mouvement analogue : si ces bords sont notés A', B', C', D', ils deviennent B', C', D', A'. Si l'on avait opéré la rotation inverse (sens contraire aux aiguilles d'une montre), les coins A, B, C, D seraient devenus D, C, B, A, avec le mouvement analogue pour les bords. Morale de l'histoire : les coins restent des coins et les bords des bords.

Cela reste valable, non seulement pour une rotation élémentaire, mais pour n'importe quelle permutation du Rubîk's Cube. La raison en est que toutes les permutations sont des suites de rotations élémentaires. D'ailleurs, il suffit de manipuler le cube quelque temps pour se convaincre de la chose. Impossible, donc, d'amener l'une des huit pièces qui forment les coins dans la position de l'un des douze bords, ou inversement.

La décompostion en éléments simples

Nous pouvons déduire de la manipulation élémentaire ci-dessus un autre résultat : c'est que la permutation totale qu'elle opère sur les coins et les bords est paire. Qu'est-ce que cela signifie ? Qu'elle se décompose en un nombre pair de transpositions. Qu'est-ce qu'une transposition ? C'est une permutation qui échange deux éléments sans toucher aux autres. Par exemple, la transposition (A, B) transforme les quatre coins A, B, C, D en B, A, C, D. Toute permutation peut être décomposée sous la forme d'une série de transpositions. La rotation considérée plus haut, qui transforme les coins A, B, C, D en B, C, D, A peut être obtenue en appliquant successivement les trois transpositions (A, B), (A, C), (A, D). De la même façon, l'application successive des trois transpositions (A', B'), (A', C'), (A', D') transforme A', B', C', D' en B', C', D', A',

Au total, la permutation qui consiste à faire tourner une face du cube d'un quart de tour se décompose donc en six transpositions, dont trois portent sur les coins et trois sur les bords. C'est une permutation paire. Le raisonnement a été explicité ici pour la rotation dans le sens des aiguilles d'une montre, mais il est exactement le même dans l'autre sens.

Comme toutes les permutations du Rubik's Cube sont des suites de rotations élémentaires (on dit aussi des produits), il en résulte qu'elles sont toutes paires : le produit de deux permutations paires est pair, tout simplement parce que la somme de deux nombres pairs est encore un nombre pair.

Calcul du nombre de combinaison du Rubik's Cube : un vrai casse-tête !

Nous pouvons calculer maintenant le nombre de configurations du Rubik's Cube. Les huit coins peuvent être permutés ensemble de n'importe quelle manière, ce qui donne 8! possibilités (8! - qui se prononce « factorielle huit » - est égal à 8 x 7 x 6 x 5 X 4 X 3 X 2 X 1) ; en effet, le premier coin peut occuper n'importe laquelle des huit positions, soit huit choix possibles ; lorsque ce choix est fait, il reste sept possibilités pour un second coin ; ce qui donne 8 X 7 possibilités ; pour le troisième coin, il n'y a plus que six possibilités, et ainsi de suite.

En raisonnant de la même manière sur les douze bords, on arrive à la conclusion qu'à chacune des 8! dispositions des coins, correspondent 12! choix possibles pour les bords, ce qui conduit à 8! X 12! dispositions possibles pour l'ensemble des pièces, coins et bords. En fait, il faut diviser ce nombre par deux, car les permutations doivent être paires, comme il a été vu plus haut. Or, dans n'importe quel groupe de permutation, il y a autant de permutations paires que d'impaires.

Jusqu'ici, nous n'avons considéré que la dispositon des pièces, sans tenir compte de leur orientation. Or chaque coin possède trois orientations, puisqu'il a trois facettes colorées. Les bords possèdent, eux, deux orientations. Par des manipulations appropriées, il est possible de faire « basculer » les bords ou de faire « tourner » les coins, de sorte que l'on peut orienter à volonté coins et bords. A une restriction près : lorsque l'on a choisi l'orientation de 7 coins, celle du huitième est imposée ; de même., une fois fixée l'orientation de onze bords, celle du douzième est déterminée (cela résulte de la construction du cube).

Si l'on tient compte des orientations, il y a [ (8!x12!)/2 ] x (3^8/3) x (2^12/2) configurations possibles du Rubik's Cube, soit très exactement :
43 252 003 274 489 856 000 possibilités (plus de 43 000 quintillons) !

Le numérateur représente le nombre total de manières dont on peut assembler le cube (en le démontant éventuellement). Le dénominateur 12 exprime qu'il y a 12 orbites distinctes de configurations (une orbite est l'ensemble des configurations accessibles, à partir d'une situation initiale donnée, par application de notre groupe de permutations). Il est impossible de passer d'une orbite à une autre par simple permutation, sans démonter le cube,

Un ordinateur qui énumérerait les configurations à raison d'une par microseconde mettrait la bagatelle de 1,4 million d'années à les compter toutes... Cela n'empêche pas les champions du Rubik's Cube (dont je fais partie) de reconstituer le cube en moins de 2 minutes, et sans l'aide d'aucune machine.

Par où commencer pour reconstituer le Rubik's Cube ?

Prévenons toutefois les masochistes qui seraient tentés de se lancer sans plus de précaution dans l'aventure : si le cube est vraiment en désordre, deux semaines semblent être le temps moyen nécessaire pour trouver la solution, à condition de travailler dur et d'être plutôt doué.

Il est donc recommandable de s'entraÎner d'abord sur des manipulations simples. Commencez par reconstituer une face à une seul couleur. Avec un peu d'entraînement, vous en obtiendrez deux, puis trois ou quatre. Il n'est pas plus difficile de reconstituer les six face que d'en reconstituer trois ou quatre. Attention les facettes centrales ne pouvant pas bouger les unes par rapport aux autres, pour réaliser une face, il faut installer les huit autres facettes de la même couleur autour de l'élément central.

On peut également s'entraîner, pour commencer, à mettre en place les 8 coins dans leur position finale, sans se préocuper des arrêtes. Sur chaque face on voit alors 5 facettes de la même couelurs : le centre et les 4 coins. Dans cette configuration, chaque face du Rubik's cube ressemblent à la face 5 d'un dé à jouer.

Un point important : toutes les permutations peuvent être inversées. Même après 150 mouvements, il est possible de revenir à la situation initiale : il 'suffit de reproduire exactement les mêmes mouvements, mais dans l'ordre inverse et en sens inverse.

Et maintenant, à vous de jouer !