# Rubik's Cube

Le Rubik's Cube (ou cube de Rubik) est un casse-tête inventé par Ernő Rubik en 1974, et qui s'est rapidement répandu sur toute la planète au cours des années 1980. Au Canada francophone, il est nommé cube Rubik (sans le « de ») et l'appellation Rubik's Cube est considérée comme exclusivement anglophone. Il s'agit d'un casse-tête géométrique à trois dimensions composé extérieurement de 26 éléments qui, à première vue, semblent être des cubes pouvant se déplacer sur toutes les faces et paraissant 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.
Le record de résolution d'un cube est de 3,134 secondes, record établi par l'Américain Max Park le 12 juin 2023. Le plus grand Rubik's Cube du monde est le 34 × 34 × 34 réalisé par Matt Bahner$^,$.

## Histoire

Le Rubik's Cube est inventé le 19 mai 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ő Rubik obtient en 1976 le brevet hongrois HU170062 pour le « Magic Cube », mais il 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 un 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 ainsi de les intéresser à la géométrie en trois dimensions. Ce n'est qu'ensuite qu'il a l'idée (grâce à la suggestion d'un ami) de colorer chaque face d'une couleur différente, constatant alors qu'après mélange, l'état résolu du cube s'avérait extrêmement difficile à retrouver (une chance sur 43 252 003 274 489 860 000 à chaque rotation). Il eut alors l'idée de le commercialiser en tant que « casse-tête » géométrique et mathématique. Il faut un mois à l'inventeur du Rubik's Cube pour résoudre son propre casse-tête.
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 Farkas, 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 copié sous licence par de nombreux distributeurs par le monde. Il est distribué par Win Games 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 les versions 2×2×2 et 5×5×5 (connues 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 (12$^{12}$). Depuis juin 2008, la marque V-Cube vend les modèles en 6×6×6, 7×7×7 et 8×8×8.
En 1981, Patrick Bossert, écolier britannique de douze ans, publie sa solution détaillée. You can do the cube s'est vendu à 1,5 million d'exemplaires à travers le monde, dans dix-sept éditions différentes. Il est numéro un des best-sellers du Times et du New York Times en 1981.
Le 10 novembre 2016, la Cour de justice de l'Union européenne annule l'enregistrement en tant que marque européenne de la forme du Rubik's Cube, considérant que cet enregistrement protège non pas une marque mais une « solution technique », à savoir la capacité de rotation des faces du cube, qui dépend d'un brevet plutôt que d'une marque.

## Caractéristiques

Le Rubik's Cube est un cube dont chaque face est divisée en neuf cubes miniatures qui peuvent tourner indépendamment les uns des autres. En fait, le cube est composé d'un axe central portant les centres des six faces, de huit cubes sommets à trois faces visibles et de douze cubes d'arête à deux faces visibles. À l'état résolu, chaque face du cube de Rubik est d'une couleur différente des autres, mais la rotation indépendante de chaque face provoque un mélange des sommets et d'arêtes.
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. La pratique qui consiste à résoudre le Rubik's Cube le plus rapidement possible est le speedcubing. En utilisant la méthode la plus simple, on peut y arriver en moins d'une minute avec suffisamment d'entraînement. Certains pratiquants y arrivent en moins de dix secondes, et le record du monde est détenu depuis le 11 juin 2023 par l'américain Max Park, avec un temps de seulement 3,134 secondes.

## Résolution

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 Layer by Layer pour « couche par couche ».

### Nombre d'états

On commence par fixer le Cube, c'est-à-dire donner une orientation au Cube (dire quelle face est le Haut, quelle face est l'Avant…). Un « état » est une configuration des autocollants (stickers) qui respecte l'orientation du Cube. Autrement dit, on mélange le Cube avec des rotations de base {U,D,F,B,L,R} sans bouger, sans tourner le Cube, comme si on avait un mécanisme qui fixe le Cube de sorte qu'on ne puisse tourner que ses faces.
Le nombre d'états est supérieur à 43 trillions. Ainsi, même si on trouvait un milliard d'états par seconde, il faudrait plus de 1 370 ans pour les épuiser tous. Ou encore, les états des Rubik's Cubes classiques (57 millimètres de côté) pourraient recouvrir la surface entière de la Terre sur une hauteur d'environ six étages.
Plus précisément, il y a $8!\times 3^{7}\times 12!\times 2^{10}=43\ 252\ 003\ 274\ 489\ 856\ 000$ états, ce qui se calcule comme suit :
* Il y a deux orientations possibles pour chacune des douze arêtes. Étant donné qu'on ne peut pas changer l'orientation d'une arête seule (loi des flips), l'orientation de toutes les arêtes fixe l'orientation de la dernière. Cela donne 2$^{11}$ possibilités d'orientation des arêtes ;
* Il y a trois orientations possibles pour chacun des huit sommets. De même, on ne peut pas pivoter un sommet seul (loi des twists), l'orientation du dernier sommet est donc fixée par les autres. Cela donne 3$^7$ possibilités d'orientation des sommets ;
* Les arêtes peuvent s'interchanger entre elles, ce qui donne 12! possibilités de positionnements pour les arêtes ;
* Les sommets peuvent s'interchanger entre eux. Cela fait 8! possibilités ;
* Mais il existe une loi dite « loi de parité » : on ne peut échanger juste deux sommets ou deux arêtes (mais on peut interchanger deux sommets et deux arêtes). La position des arêtes et des premiers sommets fixe donc la position des deux derniers sommets et il faut donc diviser le résultat par deux.
Ce qui donne : ${\frac {2^{11}\times 3^{7}\times 12!\times 8!}{2}}=2^{10}\times 3^{7}\times 12!\times 8!$
Les centres ne sont pas considérés dans ce calcul, car ils sont fixes (mais ils peuvent tourner).
Des versions modifiées du cube original, par exemple avec un motif imprimé sur ses faces (par exemple Hello Kitty), nécessitent de 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 et il faut donc multiplier le nombre d'états du Rubik's cubes par 4$^6$/2 = 2 048. Pour un Rubik's cubes avec des centres orientés (un Super Rubik's cubes comme Rubik's cubes Hello Kitty), on a une quatrième loi, la loi des centres : à l'état résolu, le nombre de degrés des centres est un multiple de 180.

### Méthodes de résolution

On peut tenter de chercher la solution au hasard, mais étant donné 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 un état par seconde, il lui faudrait en moyenne un temps 100 fois supérieur à l'âge actuel de l'Univers (environ 5 × 10$^{17}$ secondes) pour réussir à trouver tous les états du Cube seulement grâce au hasard (4,3 × 10$^{19}$ 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 mois.
On peut manipuler le Cube méthodiquement, selon des algorithmes prédéfinis qui permettent de remonter le Cube progressivement, c'est-à-dire de déplacer et d'orienter les pièces par étapes, sans perdre les fruits de son travail préalable.

#### « Méthode couche par couche »

La méthode couche par couche est la plus intuitive et la plus simple à mettre en œuvre. La résolution nécessite en moyenne un peu plus de 185 rotations : 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 (bleu, orange, vert et rouge)), puis la deuxième couronne (la rangée horizontale à mi-hauteur), déplacer les arêtes de la face du bas à leur place et les orienter correctement, déplacer les sommets à leur place, et 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 « sandwich »

Une autre méthode intuitive est la méthode « sandwich » : 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 quatre arêtes à placer), et enfin, orienter ces quatre arêtes correctement.

#### Méthode de Jessica Fridrich

La méthode de Jessica Fridrich (ou CFOP) 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 en même temps que la deuxième couronne), réaliser l'OLL (orient last layer ; c'est-à-dire orienter les cubes de la dernière face), et enfin 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 après une démarche de mémorisation : soit 42 pour les F2L (les F2L ne nécessitent cependant pas d'être appris par cœur, ils peuvent être effectués de manière intuitive), 57 pour l'OLL, et 21 pour la PLL. Des méthodes alternatives permettent d'apprendre moins de séquences, comme l'OLL ou la PLL en deux étapes. Cependant, ces méthodes sont plus lentes.

#### Méthode Roux

Basée sur la construction de bloc, la méthode Roux est une méthode de speedcubing plus intuitive qui nécessite moins de coups que la méthode CFOP. Elle est notamment utilisée par l'ancien champion d'Europe de Rubik's cube Alexander Lau. Elle porte le nom de son inventeur, Gilles Roux. Cette méthode utilise les déplacements de l'axe du centre, comparativement à la méthode CFOP. Les étapes sont les suivantes : construire un bloc 1×2×3, construire le bloc opposé 1×2×3, placer et orienter les derniers coins (CMLL), et résoudre les six dernières arêtes et les quatre derniers centres, en ne tournant que la face du haut et la tranche.

#### Méthode de Lars Petrus

La méthode de Lars Petrus est une approche différente des deux premières : elle est moins automatisée, mais elle a l'avantage de conserver au maximum les cubes bien placés. La résolution nécessite en moyenne 60 mouvements. Elle est souvent utilisée pour des résolutions optimisées :
* Réaliser un « petit cube » de dimensions 2×2×2 (constitué de trois couleurs) ;
* Étendre ce « petit cube » à un parallélépipède 2×2×3 (constitué de quatre 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 ;
* Enfin, placer les quatre arêtes restantes.

#### Méthodes corners first

Une approche encore différente et assez intuitive (Guimond, Ortega, Waterman) 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 sont très utilisées dans les années 1980, et deviennent plus rares par la suite. 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, et résoudre la couche intermédiaire.

#### Résolution informatique

En 1981, Morwen Thistlethwaite (en) est l'un des premiers à publier une méthode de résolution informatique efficace. Grâce à sa méthode, il est capable de résoudre le cube en moins de 52 rotations.
En 1992, Herbert Kociemba améliore l'algorithme de Thistlethwaite. Son logiciel « Cube Explorer » implémente cet algorithme. Ce dernier est notamment utilisé pour générer des mélanges par la World Cube Association.
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 bien placé a deux orientations 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 quelques secondes seulement grâce à plusieurs dizaines d'algorithmes (environ 80 pour la méthode Fridrich, la plus largement utilisée).

## Théorie mathématique

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 états 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 états, c'est-à-dire le nombre minimal de rotations nécessaires pour relier n'importe quelle paire d'états — 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, à partir d'un état quelconque, de trouver la plus courte séquence menant à l'état résolu (le terme d'algorithme de Dieu fait allusion au Livre de Dieu imaginé par le mathématicien Paul 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 cubes, selon ce que l'on choisit la face-métrique (f) ou la quart-métrique (q). Pour la face-métrique, une demi-tour compte 1 (|U|² = 1) pour la quart-métrique la demi-tour compte 2 (|U|² = 2).
exemple:
Q = L'UR'U²L U'L'U LR²U'
|Q| = 11f
|Q| = 13 (ou13q)
Jusqu'en 2010, il existait un état nommé SuperFlip qui nécessite 20f ou 26q pour l'atteindre. Tomas Rokicki, mathématicien à l'université de Stanford, établit qu'il est possible de résoudre tout Rubik's cubes en un maximum de 25f rotations. En 2008, ce même mathématicien a démontré que ce nombre pouvait être réduit à 22f.
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 20f. Ce calcul nécessite 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 révèle qu'il y a environ 300 millions d'états qui nécessitent exactement 20 rotations de face pour être résolues et qu'il faut en moyenne 17f pour résoudre un état tiré uniformément au hasard.
En août 2014, Tomas Rokicki et Morley Davidson démontrent que le nombre de Dieu est 26q.

## Championnats et records

La World Cube Association (abrégée WCA) régule des compétitions suivant des règles précises : chaque candidat utilise son cube personnel (souvent lubrifié) et la position de départ est la même pour tous les participants d'une même manche. Le premier championnat du monde se déroule à Budapest en 1982. Les deuxièmes championnats du monde n'ont lieu qu'en 2003 à Toronto, au Canada.
Le temps le plus rapide jamais réalisé officiellement est de 3,13 s, détenu par Max Park lors de la compétition Rubik's Cube Pride à Long Beach en Californie, le 11 juin 2023, améliorant le record de 3,47 s, détenu par le Chinois Yusheng Du. Le record officiel basé sur la moyenne de trois cubes parmi cinq (excluant l'essai le plus rapide et le plus lent) est de 4,48 s, détenu par Yiheng Wang (effectué au Mofunland Cruise Open le 19 juin 2023), détrônant le précédent record de 4,86 s, codétenu par Tymon Kolasiński (effectué à Cube4fun in Warsaw le 30 juillet 2022) et Max Park (effectué au Marshall Cubing September le 24 septembre 2022).
Il existe également d'autres disciplines reconnues par la World Cube Association : résolution les yeux bandés (le blindsolving), avec une seule main, de variante, etc. Le temps officiel le plus rapide les yeux bandés est de 12,78 s établi par l'Américain Tommy Cherry au 4BLD in a Madison Hall 2023.
La France organise tous les ans un championnat de France. Ce championnat est organisé à Paris, en France, entre 2004 et 2012. Depuis 2013, il se tient chaque année à Tigery. L'édition 2020 est annulée en raison de la pandémie de Covid-19.
En 2011, le robot CubeStormer II réussit à battre le record du monde (à l'époque de 5,66 s) jusque-là détenu par un humain en résolvant un cube en seulement 5,270 s. 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 II.
Depuis, le 17 mars 2014, le robot ARM-Powered Cubestormer 3 bat ce record en réalisant le casse-tête en 3,253 s lors du Big Bang Fair de Birmingham, au Royaume-Uni. Le robot conçu par les mêmes ingénieurs est construit en Lego et fonctionne grâce à une application Android sur un Samsung Galaxy S4.
Le 23 janvier 2016, le robot Sub1 réalise le casse-tête en seulement 0,887 s, détrônant ainsi le précédent robot. Ce record est réalisé au Cubikon Store de Munich, en Allemagne. Le robot bat même son propre record en 2018 en réalisant le casse-tête en 0,637 s.

## Variantes et décoration

Le succès du Rubik's cubes donne naissance à plusieurs variantes. Rubik's publie au total quatre variantes de forme cubique, en changeant le nombre de cubes sur une arête. Panagiotis Verdes (en) est l'inventeur de versions plus complexes, des cubes 6×6×6 et 7×7×7. De son côté, l'informatique peut simuler des cubes jusqu'à 1 000×1 000×1 000. D'autres variantes consistent à changer le polyèdre utilisé. La plupart de ces variantes ont été inventées par Uwe Mèffert ou encore la Twistball inventée par Josip Matijek. Il existe d'autres variantes, comme le Rubik's Barrel ou le Puzzle multipyramidal.
Il existe des variantes du schéma de couleurs classique. Par exemple, sur le schéma dit « japonais », la face blanche et la face bleue sont opposées. Le cube calendrier est décoré de sorte qu'il soit possible de former n'importe quelle association de jour et date sur une des faces. Il existe également des variantes publicitaires ou à thèmes : ainsi ont été créés des Rubik's Cubes à l'effigie de Dark Maul, d'Homer Simpson, du musée du Louvre ou encore de marques de sodas. Certains Rubik's Cubes sont aussi distribués (parfois sous forme de porte-clés : 2×2×2 ; 3×3×3), pour des organisations ou des entreprises.

## Dans la culture populaire

L'image du cube est reprise dans nombre de graphismes évoquant les années 1980 (articles, vêtements, disques, etc.), faisant de lui l'un des symboles culturels de cette décennie. Entre 1983 et 1984, Hanna-Barbera réalise douze épisodes d'une série d'animation appelée Rubik, The Amazing Cube, diffusée sur ABC. Le Rubik's cube fait plusieurs aussi apparitions dans la série d'animation Les Simpson, notamment quand Homer est distrait par un cube en apprenant les commandes de la centrale (Une belle simpsonnerie), dans les lots impossibles à gagner lorsque Homer devient forain (Un drôle de manège), quand Marge tente de résoudre le cube pendant que le reste de la famille lui crie des conseils (Une crise de Ned) et quand Homer résout un panier plein de cubes après avoir obtenu un QI de 105 (Le Cerveau).
Dans le film Cube, sorti en 1997, les personnages évoluent dans une structure comportant des pièces se déplaçant de façon a priori aléatoire afin de retrouver leur position initiale. La couleur des parois de chaque pièce peut varier entre le blanc, le bleu, l'orange, le rouge, le vert et le jaune (couleurs du Rubik's cubes classique). La structure comprenant ces pièces s'avère être un cube rappelant le casse-tête. La suite, intitulée Cube 2 et sortie en 2002, abandonne ce principe en utilisant uniquement des pièces aux parois blanches. Le concept est finalement repris dans la préquelle Cube Zero sortie en 2004.
Depuis 2005, l'artiste Invader réalise des compositions en utilisant des Rubik's cubes.
Dans le film À la recherche du bonheur, qui se passe en 1981, le personnage principal impressionne un directeur de ressources humaines en résolvant un Rubik's Cube.
Le 19 mai 2014, pour célébrer le 40e anniversaire du Rubik's Cube, le moteur de recherche Google place sur sa page d'accueil une animation permettant aux internautes de manipuler virtuellement le célèbre cube.

## Galerie

* Cube dans un état mélangé.
* Cube dans son état résolu.
* Mécanisme interne du cube.
* Twistball bicolore bleu-vert.
* Pyraminx (tétraèdre).
* Skewb (cube).
* Megaminx (dodécaèdre régulier).
* Square One (cube).
* Rainbow Cube (cuboctaèdre).
* Cube miroir ou cube architecte.
* V-Cube 6 (6×6×6).
* V-Cube 7 (7×7×7).
* Pocket Cube (2×2×2).
* Rubik's cubes (3×3×3).
* Rubik's Revenge (4×4×4).
* Professor's Cube (5×5×5).

## Récompense

* Spiel des Jahres meilleur jeu solitaire 1980