Comment résoudre n'importe quel puzzle de type “Rubik”

Cette page est la version Web de mes articles "Comment résoudre n'importe quel puzzle de type Rubik" parus dans la revue Math Jeunes. Si vous en avez la possibilité, je vous recommande vivement de charger ces fichiers PostScript.et de les imprimer sur une imprimante couleur. Dans le cas contraire, cette page est pour vous. Pour plus d'informations sur l'‘historique’ de cette méthode et pour quelques liens intéressants, veuillez lire la page d'introduction.

Cet article présente une procédure de résolution du Cube de Rubik 3x3x3, alias le Cube, ce célèbre casse-tête apparu vers la fin des années 70. La méthode que nous décrivons ici est également applicable à la plupart des variations du Cube (Impossiball, Megaminx, Cube 5x5x5, Pyraminx, Skewb et Square One, illustrés ci-dessus).

Nous allons montrer qu'il est humainement possible de transformer ceci en ceci tout en comprenant la procédure à suivre...

Les pré-requis nécessaires à l'application de cette méthode sont minimaux: il suffit en effet d'être capable de résoudre une face du cube.

Cet article est divisé en deux parties. La première se limite à exposer la méthode de résolution. Elle se développera principalement autour d'un exemple.
La seconde vise à “démontrer” l'efficacité de la méthode. Son contenu est plus mathématique, mais n'utilise que des notions intuitives de Théorie des Groupes.

Il me faut néanmoins insister sur le point suivant: c'est bien une méthode qui sera exposée ici, et non un algorithme. En d'autre termes, il y aura encore une recherche à effectuer pour mener à bien la résolution. Nous transformons simplement un casse-tête quasi insoluble en un puzzle presque à la portée de tous.

En général, les gens qui connaissent une méthode pour résoudre le Cube de Rubik connaissent un long algorithme en plusieurs étapes. Par exemple, il peut leur être demandé de successivement:

D'habitude, chacune de ces étapes requiert la connaissance de deux ou trois ‘formules’ (c'est-à-dire des séquences de mouvements) à appliquer dans le but de placer correctement certaines pièces sans détruire ce qui a déjà été mis en place. Au total, cela fait beaucoup de formules à retenir ! De plus, la provenance de ces formules n'est en général pas très claire. De ce fait, elles ne peuvent pas être facilement réutilisées pour d'autres puzzles de type Rubik.

Afin de reconstruire le Cube progressivement, posons-nous la question suivante: quelles sont les opérations les plus simples possibles (visuellement parlant) que nous pourrions désirer faire subir au Cube ? Elles sont au nombre de deux, à savoir:

tout en laissant le reste du cube inchangé.

Malheureusement, ces opérations ne sont pas réalisable avec un cube 3x3x3. En effet, chaque fois qu'une pièce est tournée (un bord ou un coin), au moins une autre pièce du même type est également tournée. De même, si deux pièces sont échangées, un autre échange doit être effectué ailleurs.
En conséquence, les mouvements les plus simples que nous pouvons espérer faire subir à un Cube 3x3x3 sont:

• deux rotations, chacune d'une pièce,
  

• deux échanges, de deux pièces chacun.

De plus, dans le dernier cas, si une même pièce est impliquée dans les deux échanges, alors on obtient une permutation de 3 pièces.

Bien sûr, il se pourrait que les différentes pièces que nous voulions tourner ou échanger ne se trouvent pas sur une seule et même face, comme dans les trois exemples ci-dessous...

Nous allons montrer que toutes ces opérations sont réalisables, et que l'on peut “facilement” trouver des séquences de mouvements qui les réalisent. Il est ensuite facile de montrer que le cube entier peut être résolu à l'aide de telles opérations (il suffit de soigneusement choisir les pièces à tourner ou échanger).
Le problème consiste donc simplement à trouver comment ne tourner que 2 pièces, comment n'échanger que 2 paires de pièces et comment n'en permuter que 3, sans modifier le reste du Cube.

Et tout le secret réside dans la formule

que nous allons maintenant expliquer sur un exemple...

Supposons que nous voulions tourner deux pièces de bord de la tranche supérieure.

Nous commençons par chercher une suite de mouvements X qui renverse la pièce supérieure droite, qui conserve le reste de la tranche supérieure mais qui peut détruire une partie voire l'entièreté du reste du cube.

Une telle séquence X est relativement facile à trouver: quiconque est capable de résoudre une face du cube est en mesure d'effectuer cet échange.
Le Cube de Rubik est un casse-tête réversible: si nous appliquions maintenant la séquence inverse de X (les mouvements inverses dans l'ordre inverse), ce que nous notons X^-1, le cube reviendrait à sa position initiale.

Nous aurons à appliquer cette séquence inverse X^-1, mais pas immédiatement. Il sera donc nécessaire de se souvenir de cette séquence X afin de l'inverser.

Mais avant d'appliquer la séquence X^-1, tournons la tranche supérieure de manière à ce que la seconde pièce que nous voulons retourner se mette à son tour sur le bord supérieur droit (c'est-à-dire à la place de la pièce que nous venons de retourner). Désignons cette rotation par s. Il est crucial de ne pas tourner le Cube lui-même, mais seulement la tranche supérieure: les centres des différentes faces doivent rester inchangés.

Maintenant seulement, appliquons X^-1, la séquence inverse de X.

Remarquons que non seulement la seconde pièce a à son tour été retournée, mais le reste du cube a aussi été rétabli !
Enfin, il n'y a plus qu'à ramener la tranche supérieure en appliquant s^-1.

Nous avons bien retourné deux arêtes sans détruire le reste du cube.

La série de mouvements que nous avons effectués est

Ce exemple illustre la propriété suivante:

Cette propriété est démontrée dans la seconde partie.

Notre raisonnement montrera en fait que la même méthode peut être appliquée pour tourner les coins ou réaliser des échanges de pièces: si l'on peut trouver une suite de mouvements X qui tourne un coin ou échange deux bords ou coins de la tranche supérieure, sans la modifier d'avantage, mais en détruisant peut-être le reste du cube (et de telles suites de mouvements ne sont pas difficiles à trouver), alors en appliquant la suite XsX^-1s^-1, il est possible de tourner deux coins ou d'échanger 3 (ou 4) bords ou coins de la tranche supérieure sans détruire le reste du cube.

Bien sûr, nous sommes libres de choisir n'importe quelle tranche comme tranche supérieure, pour autant que nous ne changions pas ce choix durant l'application de la séquence XsX^-1s^-1.

Mais que faut-il faire si les pièces que l'on veut tourner ou échanger sont sur des tranches différentes, comme dans les trois exemples donnés plus haut ?

C'est simple: il suffit de les y amener par une suite de mouvements P, puis d'appliquer la formule précédente pour un certain X, et enfin d'effectuer P^-1 pour restaurer le cube dans sa configuration initiale, mais avec les pièces tournées ou échangées.

Et c'est cela le secret de la formule

Dans la première partie, nous avons annoncé qu'il suffisait d'être en mesure de résoudre une face du Cube pour être capable de le résoudre entièrement. Nous allons maintenant démontrer ce fait.

Rappelons que notre méthode se base sur la formule suivante: XsX^-1s^-1 où X est une suite de mouvement qui tourne une pièce ou échange deux pièces de la tranche supérieure, sans la modifier d'avantage, et s est une rotation de cette tranche supérieure.
Nous avons prétendu que la suite de mouvements XsX^-1s^-1 tourne deux pièces ou échange trois ou quatre pièces de la tranche supérieure, tout en laissant le reste du cube intact.
Nous avons illustré ceci sur un exemple. Nous allons réutiliser cet exemple afin de démontrer l'efficacité de cette méthode.

Examinons d'un peu plus près ce qui s'est passé durant la manipulation décrite dans l'article précédent...

Nous allons nous intéresser à l'action des séquences de mouvements X et s sur le cube, c'est-à-dire au résultat de ces opérations comme permutations des étiquettes du cube (il y en a 9 par face). Une permutation des étiquettes pourra donc être considérée comme le résultat d'un décollage puis d'un recollage de ces étiquettes.

Bien sûr, certaines permutations des étiquettes ne peuvent pas être obtenues comme résultat d'une suite de mouvements réels (par exemple si l'on se retrouve avec plusieurs centres de la même couleur).

Ces permutations sont des applications bijectives de l'ensemble des étiquettes sur lui-même.

Elles peuvent donc être composées (nous notons la composition de la gauche vers la droite), inversées, etc... L'ensemble de ces permutations forme donc un groupe pour l'opération de composition. L'ensemble des permutations qui résultent d'une suite de mouvements du Cube en forme un sous-groupe.

Afin de décrire ces permutations, donnons un nom à toutes les étiquettes du cube (ces noms sont inspirés de l'anglais: F-Front, B-Back, L-Left, R-Right, G-Ground, T-Top).

Examinons la permutation résultat de l'opération X que nous avons utilisé dans la première partie de cet article. Rappelons que notre but était de retourner deux pièces de bord de la tranche supérieure, à savoir les pièces T6-R2 et T8-F2.

La suite de mouvements X a été choisie de sorte que

1.   elle permute les étiquettes T6 et R2, et laisse inchangées les autres étiquettes de la tranche supérieure,
   

2.   elle mélange les autres étiquettes du cube.

Nous pouvons donc décomposer X en deux parties: X=(T6 R2)•Y où (T6 R2) est la permutation qui correspond à l'action (1.), et Y est la permutation qui agit sur les étiquettes autres que celles de la tranche supérieure conformément à l'action (2.) (elle n'agit donc pas non plus sur les étiquettes latérales de cette tranche supérieure).

Nous n'aurons en fait pas besoin de décrire la permutation Y. Néanmoins, si nous désirions le faire, nous pourrions utiliser une ‘décomposition en cycles’ du style Y=(F5 R5 B5 L5)(R8 F4)(G6 L6)(B6 L4), ce qui signifie que l'étiquette en position F5 est déplacée en position R5, que celle en position R5 est déplacée en B5, elle-même déplacée en L5, elle-même finalement renvoyée en F5, et que les étiquettes en position R8 et F4 sont permutées, ainsi que celles en position G6 et L6, puis B6 et L4.

Rappelons que, dans tout groupe, étant donné deux éléments a et b, l'inverse du produit a•b, noté (a•b)^-1, est le produit b^-1•a^-1.
Ceci étant également vérifié pour notre groupe de permutations, nous en déduisons que X^-1=Y^-1•(T6 R2), où Y^-1 est la permutation inverse de Y.

En vertu du même principe, pour le Y donné ci-dessus, Y^-1 serait la permutation (L4 B6)(L6 G6)(F4 R8)(L5 B5 R5 F5).

Appelons s la permutation des étiquettes du cube lorsque l'on tourne la tranche supérieure.

Voici maintenant LA propriété qui fait tout fonctionner:

La preuve de cette proposition est intuitive: si nous désirons appliquer permutation a sur un ensemble A, et permutation b sur un ensemble B disjoint de A, alors nous pouvons effectuer a d'abord et b ensuite ou le contraire, le résultat final sera le même.

(C'est le même principe qui veut que mettre ses chaussures, puis mettre ses gants donne le même résultat que mettre ses gants puis ses chaussures. Par contre, l'ordre dans lequel on enfile ses chaussettes et l'on met ses chaussures fait certainement une différence ! Formaliser cette preuve `mathématiquement' serait cependant un petit peu plus long !)

Rappelons-nous que, par choix de X et définition de Y, la permutation Y n'agit pas sur les étiquettes de la tranche supérieure.
Quant à elle, la permutation s n'agit que sur les étiquettes de la tranche supérieure.

Donc Y et s commutent !

Ainsi, la permutation complète que nous avons effectuée est

Ceci signifie qu'appliquer la suite de mouvements XsX^-1s^-1 a le même effet qu'appliquer la permutation (T6 R2)s(R2 T6)s^-1. Remarquons maintenant qu'appliquer cette permutation consiste (au niveau du déplacement des étiquettes) en

1. échanger les étiquettes du bord supérieur droit (permutation (T6 R2))

   (celles de la première pièce que nous voulons retourner)

2. tourner la tranche supérieure (permutation s)
   

3. échanger les étiquettes du bord supérieur droit (permutation (R2 T6) )

   (celles de la seconde pièce que nous voulons retourner)

4. remettre la tranche supérieure à sa position initiale (permutation s^-1).

et ceci fournit exactement le résultat que nous voulions obtenir: la permutation ci-dessus échange retourne bien deux pièces sans modifier le reste du cube.

En résumé, nous avons montré que:

• si X est une suite de mouvements qui retourne un bord de la tranche supérieure et conserve le reste de cette tranche mais mélange tout le reste du cube,
  

• et si s est une rotation de la tranche supérieure,

alors la suite de mouvements XsX^-1s^-1 retourne deux bords de la tranche supérieure et conserve le reste du cube.

Il faut remarquer que, dans notre raisonnement, nous n'avons pas eu besoin de connaître la permutation Y. En appliquant X^-1, la permutation Y^-1 reconstruit ‘naturellement’ ce que X avait détruit.

Cette indépendance par rapport à Y montre que la suite de mouvements X peut réellement être choisie librement, pour autant que seule une pièce de la tranche supérieure soit modifiée par X.

Mais il est bien plus intéressant encore de remarquer que le même raisonnement montre que, si l'on peut trouver une suite de mouvements X qui tourne un coin ou échange deux bords ou coins de la tranche supérieure, sans la modifier d'avantage, mais en détruisant peut-être le reste du cube, alors en appliquant la suite XsX^-1s^-1, il est possible de tourner deux coins ou d'échanger 3 (ou 4) bords ou coins de la tranche supérieure sans détruire le reste du cube.

De plus, comme nous l'avons déjà expliqué, si les pièces que l'on veut tourner ou échanger ne sont pas sur la tranche supérieure, il suffit de trouver une suite de mouvements P qui les y amène, et d'appliquer la formule PXsX^-1s^-1P^-1.

Vous voici maintenant capables de résoudre le Cube de Rubik 3x3x3.

Enfin, nous n'avons en fait jamais réellement utilisé le fait que ce c'était un Cube 3x3x3 que nous manipulions. Nos arguments peuvent tout aussi bien s'appliquer au Cube 5x5x5 ou à la plupart de leurs variantes ! La difficulté ne consiste plus qu'à trouver les permutations X.

Bien sûr, c'eût été trop beau si cela avait vraiment été si simple...

Supposons que vous commenciez la résolution de votre Cube par la mise en place des coins par rapport aux centres. Tout à coup, vous remarquez qu'il ne faut plus en échanger que deux !
Bien qu'il ne soit pas possible de n'échanger que 2 pièces du Cube, une telle situation peut se produire, et est due au fait que tous les bords ne sont pas encore en place (autrement dit, un échange de bords devra aussi avoir lieu).

Dans le cas présent, nous sommes confrontés à un problème de parité: chaque fois que nous appliquons la suite PXsX^-1s^-1P^-1, nous effectuons un nombre pair de mouvements. Mais P permute autant de pièces que P^-1 , et de même pour X et X^-1, ainsi que s et s^-1. Nous ne pouvons donc réaliser qu'un nombre pair d'échanges de pièces semblables. Notre méthode ne permet donc pas de n'échanger que deux coins.

Afin de résoudre ce problème de parité, il suffit de tourner une tranche (par exemple la tranche supérieure) une seule fois. Au lieu d'avoir deux coins mal placés, il n'y en a maintenant trois. Mais il n'y a alors plus qu'à échanger deux fois une paire de coins à l'aide de notre méthode comme illustré ci-dessous.

Lorsque vous maîtriserez cette méthode, vous remarquerez qu'elle n'est pas très ‘économique’ quant au nombre de mouvements nécessaires à la résolution du Cube ! Ceci s'explique par le fait que nous nous efforçons de conserver tout le cube sauf 2, 3 ou 4 pièces, même si il n'y a en réalité rien à conserver...

Cependant, par rapport aux ‘pros du Cube’ qui sont capables de le résoudre en une dizaine de secondes, sans pouvoir résoudre ses nombreuses variantes, nous sommes en mesure d'aborder sereinement (quasi) tous les puzzles de type Rubik. En effet, notre méthode s'y applique sans peine, pour autant que nous soyons à même de résoudre une face de ceux-ci. Nous n'avons pas d'algorithme à retenir, nous sommes capables de le construire nous-mêmes.

Pour ma part, je m'attaque à ces casse-têtes avec une méthode mixte: il est en général possible de compléter une ou plusieurs faces sans trop devoir réfléchir (une seule face pour le Cube 3x3x3, mais à peu près toutes pour le Dodécahèdre), et je n'applique la méthode exposée ici que pour terminer l'objet.

Pour terminer cet article, voici quelques problèmes que je vous invite à résoudre:

• La méthode fonctionne-t-elle toujours si, plutôt que de considérer la tranche supérieure, vous considérez la tranche centrale (qui contient les 4 centre des faces latérales) ? Comment se formule-t-elle ?
  

• Pouvez-vous montrer qu'il n'est pas possible de n'échanger que 2 pièces d'un Cube de Rubik 3x3x3 ?
  
• Pouvez-vous montrer qu'il n'est pas possible de ne faire tourner qu'une seule pièce d'un Cube 3x3x3 ?
  
• Pouvez-vous montrer qu'il est possible de n'échanger que 2 pièces d'un Pyraminx (la pyramide) ?
  
• Est-il possible de ne faire tourner qu'une seule pièce d'un Pyraminx ? Si oui, laquelle (ou lesquelles) ?

Enfin, sachez que si vous n'avez pas (ou plus) de Cube de Rubik à votre disposition, il vous est possible de jouer avec un ‘cube virtuel’ sur Internet. Je vous invite à aller lire ma page rubik.htm. Vous y trouverez également quelques liens et adresses en rapport avec le sujet. Enfin, si vous avez des questions à poser, ou des commentaires à formuler, sur cette page, n'hésitez pas à m'envoyer un petit message...

Bon amusement !

Retour à ma page de bienvenue...
Cette page a déjà été lue (au moins) fois.