[LONG] Panoplie des logiciens,ennes (1980-1991)

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 ...

CuBiC (Geoffrey Chappell,1991) : http://cjoint.com/?exrcqodR0m :-?

Il s'agit d'un casse-tête géométrique à trois dimensions composé de 27 
petits cubes (en réalité 26, car il n'existe aucun 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 cacherait, au centre du cube ... :-?

Le Rubik's Cube a atteint son maximum de popularité au début des années 
1980. Plus de 100 millions de cubes furent 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 existerait 
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_ ...

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).

         =============================================

Le nombre de positions différentes est de 8! x 37 x 12! x 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 1200 ans pour les épuiser toutes !?!

         =============================================

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.

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 (seulement) pour l'instant que l'algorithme de Dieu nécessite 
au minimum 20 mouvements si l'on autorise les demi-tours, 26 sinon et 
qu'il nécessite au maximum 29 mouvements si l'on autorise les 
demi-tours, 40 sinon :-?

Liens et source cités (à éventuellement lire et cliquer) :

http://cjoint.com/?exrcqodR0m
http://en.wikipedia.org/wiki/Rubiks
http://fr.wikipedia.org/wiki/Rubik%27s_Cube

[fu2:fr.education.entraide.maths]