Rubik's Cube

Le Rubik’s Cube (ou, beaucoup plus rarement, Cube de Rubik) est un casse-tête inventé en 1974 par le Hongrois Ernő Rubik, et qui s’est rapidement répandu sur toute la planète au cours des années 1980.
Il s'agit d'un casse-tête géométrique à trois dimensions composé de 26 petits cubes (il n'y a pas de cube central) qui, à première vue, paraissent pouvoir se déplacer sur toutes les faces et ont l’air libres de toute attache sans tomber pour autant. Un système d’axes, dont le mécanisme a été breveté par son auteur, Ernő Rubik, se cache au centre du cube.

Histoire

Les différents modèles de rubik's cube sont : Le pocket cube (2×2×2), Le rubik's cube (3×3×3), Le Rubik's revenge (4×4×4) et le Professor's cube (5×5×5).
Le Rubik’s Cube est inventé en 1974 par Ernő Rubik1, un sculpteur et professeur d’architecture hongrois, qui s’intéresse à la géométrie et à l’étude des formes en 3D. Ernő Rubik obtient en 1975 le brevet hongrois HU170062 pour le Magic Cube, mais ne demande pas de brevet international. Le produit est testé en 1977, et les premiers cubes se vendent peu après dans les boutiques de jouets de Budapest.
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 donc de les amener à réfléchir en 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.
En Hongrie, le cube gagne en popularité par le bouche-à-oreille, et est bientôt connu dans toute l’Europe. En septembre 1979, à l'instigation de Bernard Farkas2, un accord est signé avec Ideal Toys pour distribuer le cube mondialement. Ideal Toys renomme alors le cube « Rubik’s Cube » et les premiers exemplaires sont exportés de Hongrie vers mai 1980, en direction de Londres, de New York et de Paris.
Aujourd’hui le Rubik’s Cube est distribué sous licence par de nombreux distributeurs par le monde. Il est distribué par Winning Moves en France et par Jumbo en Belgique.
Le Rubik’s Cube atteint son maximum de popularité au début des années 1980. Plus de 100 millions de cubes sont vendus entre 1980 et 19823,h 1. Le « Rubik’s Cube » gagne le prix des distributeurs de jouets britanniques en 1980 et de nouveau en 19814. De nombreux jeux similaires sont distribués peu de temps après le Rubik’s Cube, notamment le « Rubik's Revenge », une version 4×4×4 du Rubik’s Cube. Il existe aussi une version 2×2×2 et 5×5×5 (connus respectivement sous les noms de « Pocket Cube » et de « Professor’s Cube »), et des versions dans d’autres formes, comme la pyramide ou le dodécaèdre régulier. Depuis juin 2008, la marque V-Cube vend des modèles 6×6×6 et 7×7×7.

En 1981, Patrick Bossert, écolier britannique de douze ans, publie sa solution détaillée. You can do the cube se vend à 1,5 million d’exemplaires à travers le monde1, dans 17 éditions différentes. Il est numéro 1 des best-sellers du Times et du New York Times en 1981.

Description.

Le Rubik’s Cube est un cube dont chaque face est divisée en neuf cubes miniatures qui peuvent tourner indépendamment des autres. En fait le cube est composé d’un axe central portant les centres des 6 faces, de 8 cubes de coin à 3 faces visibles et de 12 cubes d’arête à 2 faces visibles. À l’état final, chaque face du cube de Rubik est d’une couleur homogène et différente des autres, mais la rotation indépendante de chaque face provoque un mélange des petits cubes de coin et d’arête.
Le but du jeu est, après avoir mélangé les six faces, de manipuler le cube pour tenter de lui rendre son apparence d’origine, avec les six faces de couleurs unies. Les couleurs des faces du cube original sont : blanc en face de jaune, vert en face de bleu, orange en face de rouge. Sur les versions non originales, les positions relatives des faces de couleurs et même parfois les couleurs peuvent changer.

Il en est sorti de nombreuses variantes de forme et de décoration (voir la section Variantes plus loin dans cet article).
La pratique du Rubik’s Cube est le speedcubing et consiste à la résolution du cube en un temps le plus court possible. En utilisant la méthode la plus simple, on peut y arriver en moins d'une minute avec suffisamment d’entraînementh 2. Les meilleurs le font en moins de quinze secondes.
Il existe différentes techniques, consistant à réaliser des séquences comportant une dizaine de mouvements. Les techniques les plus utilisées consistent à construire la « croix » d’une face avant de finir cette face. On termine ensuite les arêtes de la tranche intermédiaire. Puis on résout la dernière face en orientant puis permutant les cubes qui la constituent. Ces méthodes sont nommées pour « couche par couche » .

Résolution

Combinatoire du problème

Le nombre de positions différentes est supérieur à 43 trillions. Ainsi, en passant en revue un milliard de combinaisons différentes par seconde, il faudrait plus de 1 200 ans pour toutes les épuiser. Ou encore, on pourrait recouvrir plus de 275 fois la surface de la Terre avec des Rubik's classiques (57 millimètres de côté), chacun dans une configuration différente.

Plus précisément, il y a 8! × 37 × 12! × 210 = 43 252 003 274 489 856 000 combinaisons, ce qui se calcule comme suith 3 :
Il y a deux orientations possibles pour chaque arête. Étant donné qu’on ne peut pas changer l’orientation d’une arête seule, l’orientation de toutes les arêtes fixe l’orientation de la dernière. Cela donne 211 possibilités d’orientation des arêtes.
Il y a trois orientations possibles pour chaque coin. De même, on ne peut pas retourner un coin seul, l’orientation du dernier coin est donc fixée par les autres. Cela donne 37 possibilités d’orientation de coins.
Les arêtes peuvent s’interchanger entre elles, ce qui donne 12! possibilités de positionnements pour les arêtes.

Les coins peuvent s’interchanger entre eux. Cela fait 8! possibilités.
Mais il existe un problème dit de parité : on ne peut échanger juste deux coins ou 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 et il faut donc diviser le résultat par deux.
Les centres ne sont pas considérés dans ce calcul, car ce sont eux qui nous servent de points de repère.

Des versions modifiées du cube original, par exemple avec un motif imprimé sur ses surfaces, nécessitent, elles, une position spécifique de ces carrés centraux qui nous oblige à considérer l’orientation des centres. Chaque centre a quatre orientations possibles, l’orientation du dernier est comme d’habitude fixée par celle des précédents (à un demi-tour près) et il faut donc multiplier le nombre de positions du Rubik’s cube par 2×45 = 2048.

Méthodes de résolution.

On peut tenter de chercher la solution au hasard, mais étant donnée l’espérance de vie humaine, ce n’est pas une solution viable. Si l'on admet qu'un être humain peut passer en revue en moyenne une combinaison par seconde, il lui faudrait en moyenne un temps cent fois supérieur à l'âge actuel de l'Univers (environ 5×1017 secondes) pour réussir à trouver toutes les combinaisons du cube seulement grâce au hasard (4,3×1019 secondes) : autrement dit absolument rien de physiquement réalisable. Il a donc fallu inventer des méthodes pour résoudre le cube. La légende veut qu’Ernő Rubik lui-même y ait passé plus d'un mois5.

On peut manipuler le cube méthodiquement, selon des séquences de mouvements prédéfinies qui permettent de remonter le cube progressivement, c’est-à-dire de déplacer et d’orienter les petits cubes par étapes, sans perdre les fruits de son travail préalable. Voici plusieurs exemples de méthodes :

Première méthode, dite « méthode couche par couche »

C’est la plus intuitive et la plus simple à mettre en œuvre. La résolution nécessite en moyenne un peu plus de 110 mouvements :
Réaliser une face, par exemple la face supérieure blanche, en prenant bien soin de placer correctement la couronne (placer les cubes entourant cette face) et les cubes centraux (jaune, orange, blanc et rouge),
puis la deuxième couronne (la rangée horizontale à mi-hauteur),
déplacer les cubes-arête de la face du bas à leur place et les orienter correctement,
déplacer les cubes-sommet à leur place, enfin les orienter. Chaque opération (tourner une arête ou un sommet, échanger deux arêtes ou deux sommets) pourra être réalisée deux fois, après avoir placé les cubes concernés sur la même face, et en prenant soin de ne pas modifier cette face pendant l'opération. La première exécution mélange le reste du cube, mais en tournant alors la face d'un quart ou d'un demi-tour pour placer le(s) sujet(s) de la deuxième opération au même endroit relativement au reste du cube et en refaisant l'opération à l'envers, on réalisera la deuxième opération tout en remettant le reste du cube en place.

Méthode d’Ofapel

Une autre méthode intuitive :
Réaliser une face, par exemple la face rouge.
Réaliser la face opposée à celle déjà correcte (ici la face orange), pour cela il faut d’abord placer correctement tous les coins, puis les orienter correctement, et enfin mettre les arêtes.
Par échanges, amener chaque arête restante à sa place (à ce stade il ne reste plus que 4 arêtes à placer).
Enfin placer, puis orienter ces 4 arêtes correctement.

Méthode de Lars Petrus.

C’est une approche différente des deux premières : elle est moins automatisée, mais a l’avantage de conserver au maximum les cubes bien placés. La résolution nécessite en moyenne 60 mouvements :
Réaliser un « petit cube » de dimensions 2×2×2 (constitué de 3 couleurs).
Étendre ce « petit cube » à un parallélépipède 2×2×3 (constitué de 4 couleurs), sans jamais détruire le « petit cube ».
Orienter les arêtes restantes, de façon à pouvoir les placer orientées correctement en utilisant deux faces.
Étendre l’objet 2×2×3 à un objet 2×3×3 (c’est-à-dire deux couches du cube complet), sans jamais détruire ce qui a été fait auparavant.
Placer et orienter les 4 coins restants.
Et enfin, placer les 4 arêtes restantes.

Méthode de Jessica Fridrich

C’est encore une approche différente qui, comme celle de L. Petrus, nécessite environ 60 mouvements. Cette méthode est très utilisée en speedcubing car systématique :
Réaliser une croix sur une face.
Réaliser les F2L c'est-à-dire de placer les coins de la face blanche en même temps que la deuxième couronne.
Réaliser l’OLL (orientate last layer), c’est-à-dire orienter les cubes de la dernière face.
Réaliser la PLL (permute last layer), c’est-à-dire replacer les cubes de la dernière face.
Cette méthode est utilisée par les plus grands champions mais nécessite l’apprentissage de nombreuses séquences :
42 pour les F2L (les F2L ne nécessitent cependant pas d'être appris par coeur, il peuvent être effectués de manière intuitive)
57 pour l’OLL
21 pour la PLL
Des méthodes alternatives permettent d’apprendre moins de séquences, comme l’OLL ou la PLL en deux étapes.

Méthodes corners first (Guimond, Ortega, Waterman)

Une approche encore différente et assez intuitive consiste à commencer par les coins ; l'avantage d'une telle méthode est qu'il est ensuite facile de résoudre les arêtes en gardant les coins bien placés. Ces méthodes étaient très utilisées dans les années 1980. Elles sont devenues plus rares aujourd'hui. La résolution nécessite 60 à 70 mouvements (une cinquantaine seulement si on compte un mouvement de tranche centrale comme un seul mouvement et non deux) :
Placer et orienter les coins (plusieurs approches sont possibles pour cela).
Placer et orienter les arêtes de deux couronnes opposées.
Résoudre la couche intermédiaire.

Les Cubes 4x4x4, 5x5x5, etc.

Pour un supercube, la méthode la plus simple (et la plus longue) reprend quelques algorithmes de la méthode couche par couche pour un 3x3x3 :
Former la face inférieure et sa couronne
Placer les coins de la couche supérieure
Placer les arêtes de la face supérieure
Placer les arêtes intermédiaires sur leurs couches respectives
Orienter correctement les arrêtes intermédiaires
Placer les centres.
On peut facilement placer les arêtes de la deuxième couche entre les étapes 1 et 2. Cela permet d'éviter l'étape 4 pour les cubes de 4x4x4 et 5x5x5.
Pour résoudre un 3x3x3 en couche par couche, on doit apprendre 5 algorithmes au minimum. Pour résoudre n'importe quel "supercube" (même un 500x500x500), 2 algorithmes supplémentaires sont nécessaires.
Une méthode plus efficace consiste à :
Placer les centres
Placer toutes les arêtes de même couleur ensemble (possible seulement si on les oriente dans un même sens)
Résoudre le cube comme s'il s'agissait d'un 3x3x3.
Il est fréquent de finir l'étape 3 avec une seule rangée d'arête mal orientée (ce qui ne peut arriver sur un 3x3x3). Une quatrième étape, peut parfois consister à orienter cette rangée d'arête.
On peut, grâce au logiciel Gabbasoft Cube, résoudre un cube informatique allant jusqu'à 20x20x20.

Remarques

Si un petit cube est à sa place, cela ne signifie pas nécessairement que les couleurs sont à leur bonne place. Par exemple un cube-arête a deux positions de couleur possibles et un cube-sommet trois.
Chaque étape intermédiaire utilise elle-même des algorithmes spécifiques.
Il existe en fait de nombreuses méthodes de résolution. Certains spécialistes y ont même consacré leur thèse universitaire. Des compétitions sont organisées. Les meilleurs concurrents sont capables de rétablir un cube en moins de quinze secondes grâce à plusieurs dizaines d’algorithmes (environ 80 pour la méthode Fridrich, la plus largement utilisée).

Théorie mathématique sur le Rubik's Cube.

Article détaillé : Théorie mathématique sur le Rubik's Cube.

Le cube de Rubik est un support pédagogique très intéressant pour l’enseignement des mathématiques, en particulier pour la théorie des groupes.
La résolution du cube peut passer par l’algèbre, en modélisant chacune des rotations par une lettre. L’ensemble des configurations du cube constitue un groupe fini.
Une question fondamentale que l’on peut se poser sur le cube est le diamètre du graphe des configurations du cube, c'est-à-dire le nombre minimal de mouvements (flip) nécessaires pour relier n'importe quelle paire de configurations du cube — nombre parfois appelé nombre de Dieu. Plus encore que ce nombre de Dieu, on voudrait connaître l'algorithme de Dieu, c'est-à-dire la méthode la plus simple et élégante à décrire qui permette, pour chaque configuration du cube, de trouver la plus courte séquence la transformant en le cube résolu (le terme d'algorithme de Dieu fait allusion au Livre de Dieu imaginé par le mathématicien Erdös qui contiendrait les preuves les plus simples et élégantes de chaque théorème mathématique).
Cette question se décline en deux versions à propos du Rubik’s Cube, selon ce que l’on choisit d’appeler « mouvement élémentaire ». Si un mouvement élémentaire est un quart de tour d’une face du cube, étant donné une position, on peut faire 12 mouvements élémentaires. Si un mouvement élémentaire est au choix un quart de tour ou un demi-tour d’une face du cube, étant donné une position, il existe 18 mouvements élémentaires.

On savait jusqu'en 2010 qu'il existait une configuration du cube à au moins 20 mouvements du cube résolu si on autorise les demi-tours, 26 sinon. Une telle configuration est appelée superflip. Tomas Rokicki, mathématicien à l’université Stanford, a établi qu’il est possible de résoudre tout Rubik’s cube en un maximum de 25 mouvements (en autorisant les demi-tours)6. Le même mathématicien a ensuite annoncé avoir réduit ce nombre à 22 avec de plus larges moyens matériels7. En autorisant seulement les quarts de tour, il faut au maximum 40 mouvements (Tomas Rokicki annonce avoir réduit ce nombre à 297).
En juillet 2010, un groupe de scientifiques internationaux (incluant Tomas Rokicki, ainsi que Morley Davidson, John Dethridge et Herbert Kociemba) démontre par un calcul exhaustif que le nombre de Dieu est 208. Ce calcul a nécessité quelques semaines de calcul distribué sur un grand nombre d'ordinateurs prêtés par Google, et représentant l'équivalent d'un temps de calcul de 35 ans sur un PC haut de gamme. Au passage, ce calcul a révélé qu'il y a environ 300 millions de superflips (configurations qui nécessitent exactement 20 flips pour être résolues) et qu'il faut en moyenne 17,88 flips pour résoudre une configuration tirée uniformément au hasard.

Championnats et records.

Il existe une World Cube Association qui organise des championnats suivant des règles précises : chaque candidat utilise son cube personnel (parfois lubrifié) et la position de départ est la même pour tout le monde. Le premier championnat du monde s’est déroulé à Budapest en 1982.
Le temps le plus rapide jamais réalisé officiellement est de 5,66 s, détenu par Feliks Zemdegs lors du Melbourne Winter Open 2011 (25 juin 2011).
Le record officiel basé sur la moyenne de 3 cubes parmi 5 (excluant l’essai le plus rapide et le plus lent) est de 7.64 s. détenu par Feliks Zemdegs9, lors du Melbourne Winter Open 2011 (25 juin 2011).
Il existe également des records réalisés de façon moins conventionnelle : les yeux bandés (le blindfold cubing), avec une seule main, avec les pieds10…
La France organise tous les ans un championnat de France à Paris (hôtel Novotel du Châtelet).
En 2011, le robot CubeStormer II a réussi à battre le record du monde jusque là détenu par un humain en résolvant un cube en seulement 5,352 secondes. Il s'agissait d'un robot en Lego conçu et programmé par Mike Dobson et David Gilday et fonctionnant grâce à une application Android sur un Samsung Galaxy S II11.

Source : Wikipedia