Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
25 novembre 2008 2 25 /11 /novembre /2008 08:08

Le Rubik’s Cube - Méthodes de résolution

 

 

Le Rubik’s Cube - Méthodes de résolution

 

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 :

  1. 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),
  2. puis la deuxième couronne (la rangée horizontale à mi-hauteur),
  3. déplacer les cubes-arête de la face du bas à leur place et les positionner correctement,
  4. déplacer les cubes-sommet à leur place,
  5. 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.

 

Le Rubik’s Cube - Méthode d’Ofapel

Une autre méthode intuitive :

  1. Réaliser une face, par exemple la face supérieure rouge,
  2. réaliser la face opposée à celle déjà correcte, pour cela il faut d’abord placer correctement tous les coins, puis les orienter correctement, et enfin mettre les arêtes,
  3. tourner le centre du cube de manière à bien placer tous les centres (à ce stade il ne reste plus que 4 arêtes à placer),
  4. par échanges, amener chaque arêtes à sa place,
  5. enfin orienter ces 4 arêtes correctement.

Cette méthode, après quelques aménagements, permet de reconstituer correctement un Rubik’s cube 4×4×4, 5×5×5, etc.

 

Le Rubik’s Cube - 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 :

  1. Réaliser un « petit cube » de dimensions 2×2×2 (constitué de 3 couleurs),
  2. étendre ce « petit cube » à un parallélépipède 2×2×3 (constitué de 4 couleurs), sans jamais détruire le « petit cube »,
  3. effectuer une étape intermédiaire de réarrangement, qui consiste à afficher deux croix sur les 2 faces restantes,
  4. é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,
  5. placer et orienter les 4 cubes sommets restants,
  6. et enfin, placer les 4 arêtes restantes.

 

Le Rubik’s Cube - 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 :

  1. Réaliser une croix sur une face,
  2. 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,
  3. Réaliser l’OLL (orientate last layer), c’est-à-dire orienter les cubes de la dernière face,
  4. 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.

 

Le Rubik’s Cube - 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 80, 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) :

  1. Placer et orienter les coins (plusieurs approches sont possibles pour cela);
  2. Placer et orienter les arêtes de deux couronnes opposées;
  3. Résoudre la couche intermédiaire.

 

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.

 

Le Rubik’s Cube - Didactique en mathématiques

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.

 

Le Rubik’s Cube - 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 7.08 secondes, par Erik Akkersdijk au Czech 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 détenu par le Japonais du nom de Yu Nakajima, et est de 11,28 secondes.

Plusieurs personnes ont aussi réussi à résoudre un Cube 20×20×20 généré par ordinateur avec le logiciel gabbasoft. 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…

 

Le Rubik’s Cube - Méthodes de résolution

 

 

 

Le Rubik’s Cube - Méthodes de résolution

 

voir aussi  DEFI POUR LA TERRE - Fondation Nicolas Hulot - ADEME -

Partager cet article

Repost 0
Published by cedric - dans HIGH-TECH
commenter cet article

commentaires

clovis simard 26/06/2013 13:40

ALGORITHME DE DIEU.fermaton.over-blog.com

Présentation

  • : franco-thai
  • franco-thai
  • : apporter informations, cultures, loisirs, outils de communication, etc. Un pont entre la France et la Thaïlande
  • Contact

Partage / Share

Recherche

Archives