Rubik's Cube
Un article de Wikipédia, l'encyclopédie libre.
Le Rubik’s Cube (parfois désigné en français sous le terme de 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.
C’est un casse-tête géométrique à trois dimensions composé de 27 petits cubes (en réalité 26, car il n’existe 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.
Sommaire |
[modifier] Historique
Le Rubik’s Cube est inventé en 1974 par Ernő Rubik, un sculpteur et professeur d’architecture hongrois, qui s’intéresse à la géométrie et à l’étude des formes en 3D. Ernő 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 de 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, 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, New York et 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 1982. Le « Rubik’s Cube » gagne le prix des distributeurs de jouets britanniques en 1980 et de nouveau en 1981. 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 tétraèdre.
En 1981, Patrick Bossert, écolier britannique de douze ans, publie sa propre solution détaillée. Le livre, You can do the cube, se vend à 1,5 million d’exemplaires à travers le monde, dans dix-sept éditions différentes. Il est numéro 1 des best-sellers de The Times et The New York Times en 1981.
De 1983 à 1984, Hanna-Barbera crée douze épisodes d’un dessin animé appelé Rubik, The amazing cube qui est diffusé sur ABC.
[modifier] 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. Si le blanc se trouve sur la face supérieure et le bleu sur la face avant, alors le rouge est à droite et ainsi de suite. Sur les copies 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 (dodécaédrique, étoilé, sphérique, à angles rabattus, etc.), de taille (2×2×2, 4×4×4, etc.) et de décoration (par exemple sous forme de calendrier, imposant un exercice quotidien pour les mettre à la bonne date).
La pratique du Rubik’s Cube est le speedcubing et consiste à la résolution du cube en un temps le plus court possible. On peut arriver, avec suffisamment d’entraînement, à quelques minutes. Les meilleurs, cependant, le font en moins de 15 secondes.
Il existe différentes techniques, consistant à réaliser des algorithmes comportant une dizaine de mouvements. Les techniques les plus utilisées consistent à construire la « croix » d’une face avant de finir cette face en y associant les bords 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 « Layer by Layer » pour « couche par couche » et la plus connue est la méthode Fridrich, inventée par Jessica Fridrich et améliorée par la communauté des cubeurs.
 Cube dans un état mélangé |
 Cube dans son état résolu |
 Mécanisme interne du cube |
[modifier] Résolution
[modifier] Complexité du problème
Le nombre de positions différentes est de 8! × 37 × 12! × 210 = 11 × 72 × 53 × 314 × 227 = 43 252 003 274 489 856 000 (c’est-à-dire plus de 43 milliards de milliards de combinaisons), dont 1 seule correspond au cube fini. Pour donner une idée du nombre de combinaisons, en passant en revue 1 milliard de combinaisons différentes par seconde, cela prendrait plus de 1 200 ans pour les épuiser toutes !
Cela se calcule comme suit :
- Chaque arête peut prendre deux orientations possibles. É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 nous donne 211 possibilités d’orientation des arêtes.
- Chaque coin a trois orientations possibles. De même, on ne peut pas retourner un coin seul, l’orientation du dernier coin est donc fixée par les autres. Cela nous donne 37 possibilités d’orientation de coins.
- Les arêtes peuvent s’interchanger entre elles, ce qui nous 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 2 derniers coins et il faut donc diviser le résultat par deux.
Ce qui donne bien : 8! × 37 × 12! × 210 = 43 252 003 274 489 856 000
Il faut noter que 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.
[modifier] 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. 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é un mois.
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 :
[modifier] 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 bleue, 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 positionner correctement,
- déplacer les cubes-sommet à leur place,
- enfin les tourner sur eux-mêmes.
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.
[modifier] Méthode d’Ofapel
Une autre méthode intuitive :
- Réaliser une face, par exemple la face supérieure 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 bords,
- tourner le centre du cube de manière à bien placer tous les centres (à ce stade il ne reste plus que 4 bords à bien placer),
- par échanges, amener chaque bord à sa place,
- enfin orienter ces 4 bords correctement.
On pourra noter que cette méthode, après quelques aménagements, permet de reconstituer correctement un Rubik’s cube 4×4×4, 5×5×5, etc.
[modifier] 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 »,
- effectuer une étape intermédiaire de réarrangement, qui consiste à afficher deux croix sur les 2 faces restantes,
- é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 cubes sommets restants,
- et enfin, placer les 4 arêtes restantes.
[modifier] 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,
- Créer les quatre paires constituées d’une arête et d’un coin qui lui correspond afin de les insérer une à une sur la face de départ, le but étant de finir les deux premiers étages,
- 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 nombreux algorithmes :
- 41 pour finir les deux premiers étages
- 57 pour l’OLL
- 21 pour la PLL
Des méthodes alternatives permettent d’apprendre moins d’algorithmes, comme l’OLL ou la PLL en deux étapes.
[modifier] 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 nombreux algorithmes de solutions. 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 10 secondes grâce à plusieurs dizaines d’algorithmes (environ 80 pour la méthode Fridrich, la plus largement utilisée).
Un mathématicien issu de l’université de Stanford a établi qu’il est possible de résoudre un Rubik’s cube en un maximum de 23 mouvements, quelle que soit sa configuration initiale[1].
[modifier] Didactique en mathématiques
Article détaillé : Théorie mathématique sur le Rubik's Cube.Le cube de Rubik est aussi 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 nombre minimal de mouvements nécessaires pour passer d’une position quelconque du cube à une autre. Un algorithme qui répondrait à cette question, en décrivant une méthode pour résoudre le cube à partir de n’importe quelle position initiale en un nombre minimal de mouvements, serait appelé « algorithme de Dieu ».
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 sait pour l’instant que l’algorithme de Dieu nécessite au minimum 20 mouvements si on autorise les demi-tours, 26 sinon et qu’il nécessite au maximum 29 mouvements si on autorise les demi-tours, 40 sinon.
[modifier] 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 9,18 secondes, par Édouard Chambon au Murcia Open 2008.
Le record officiel basé sur la moyenne de 3 cubes parmi 5 (excluant l’essai le plus rapide et le plus long) est aussi détenu par le Français du nom d’Édouard Chambon. Il est de 11,48 secondes et a été mesuré et approuvé le 23 février 2008 à Murcia, Espagne, à la compétition du "Murcia Open 2008".
Plusieurs personnes ont aussi réussi à résoudre un Cube 20×20×20 généré par ordinateur avec le logiciel gabbasoft[réf. nécessaire]. La France organise tous les ans un championnat de France à Paris (hôtel Novotel du Châtelet).
Il existe également des records plus « exotiques » : yeux bandés, avec une seule main, avec les pieds[2]…
[modifier] Divers
- Le Rubik’s Cube fait plusieurs apparitions dans la série animée les Simpson, notamment quand Homer est distrait par un cube en apprenant les commandes de la centrale dans Une belle simpsonnerie, quand Marge tente de résoudre le Cube pendant que le reste de la famille lui crie des conseils dans Une crise de Ned et quand Homer résout un panier plein de cubes après être devenu une personne d’intelligence normale (avec un QI de 105) dans Le Cerveau.
- Dans le film Armageddon (1998), Rockhound (joué par Steve Buscemi) résout un Cube pendant son entretien avec le psychologue de la base d’entraînement en disant « Facile. »
- En 2006, dans le film À la recherche du bonheur, Chris Gardner (Will Smith) se fait embaucher en épatant son recruteur en réalisant les six faces en quelques minutes. Will Smith a d’ailleurs réitéré son exploit sur le plateau du grand journal.
- Dans le film Eh mec ! Elle est où ma caisse ?, sorti en 2001, Jesse (Ashton Kutcher) et Chester (Seann William Scott) cherchent un disrupteur dimensionnel. Ils apprennent par la suite qu’il s’agit du Rubik’s Cube que Chester essaye de résoudre depuis le début de l’histoire. C’est d’ailleurs en le terminant qu’il active le disrupteur dimensionnel.
- Le président américain Ronald Reagan était réputé pour sa persévérance au Rubik’s Cube. Son secrétaire à la défense Caspar Weinberger lui aurait lancé le défi au moment de son accession au pouvoir de l’achever à la fin de sa présidence[3].
- Il fait aussi une apparition dans Numb3rs, série télévisée alliant mathématiques et criminologie.
- Michel Gondry a publié sur Internet une vidéo le montrant résolvant le Rubik’s Cube avec ses pieds en un temps relativement court. En réalité, le film était truqué : il s’agissait d’un film où il mélangeait le cube passé à l’envers. L’illusion était consolidée par une introduction ou Michel Gondry exposait son exploit (passée à l’endroit et montée avant la prétendue résolution elle-même) et par le passage en arrière-plan d’un figurant qui marchait en réalité à reculons.
[modifier] Variantes
Le succès du Rubik’s Cube a donné naissance à plusieurs variantes. Rubik a commercialisé trois variantes de forme cubique, en changeant le nombre de cubes sur une arête :
 Pocket Cube (2×2×2) |
Rubik’s Cube (3×3×3) |
 Rubik’s Revenge (4×4×4) |
 Professor’s Cube (5×5×5) |
À noter qu’existent aussi des versions non encore commercialisées de cubes 6×6×6 et 7×7×7, inventées par Panagiotis Verdes.
D’autres variantes consistent à changer le polyèdre utilisé. La plupart de ces variantes furent inventées par Uwe Mèffert :
[modifier] Famille
Voici un récapitulatif des différents cubes et autres polyèdres :
| Cubes de Rubik | Autres polyèdres ou solides | Autres casse-tête |
|---|---|---|
|
|
[modifier] Récompense
[modifier] Voir Aussi
[modifier] Liens internes
- Yu Nakajima, champion du monde 2007.
[modifier] Liens externes
- Méthodes de résolution :
- (en) Rubik’s Cube Solver : un générateur de solution
Simulations du cube :
- (fr) randelshofer.ch
[modifier] Notes et références
- ↑ La preuve est basée sur 25 coups, mais avec de plus larges moyens matériels, ce nombre a été réduit à 23 par le même mathématicien. (en) Tomas Rokicki, Twenty-Five Moves Suffice for Rubik’s Cube[pdf] et
- ↑ Les championnats de Rubik’s cube, Tangente, 2007 n° 114, p. 45
- ↑ Kenneth Walsh, Ronald Reagan, New York, Random House Value Publishing (1997) et Richard Reeves, President Reagan: The Triumph of Imagination, New York, Simon & Schuster (2005).
