Le Rubik's Cube

Cet objet insolite aux multiples facettes. Nombreux furent les cheveux perdus par ceux qui tentèrent de le résoudre.
- Vous n'avez jamais résolu un Rubik's Cube?
- Vous n'avez jamais programmé?
- Vous n'êtes pas un Geek?
Ce blog est fait pour vous. Car avant d'écrire avec un ami ce programme qui résout le Rubik's cube, j'étais comme vous.

Laissez-vous tenter par cette aventure merveilleuse qui change une façon de voir le monde. Embarquez avec moi dans ce tutoriel détaillé, accessible à tous où vous apprendrez à résoudre le Rubik's Cube à l'aide d'un ordinateur.

Bienvenue dans mon monde !
Un peu de découpage

Pour atteindre notre objectif, il est important d'avoir une vision très claire de ce qu'est le Rubik's Cube. En première approche, considérons-le comme un empilement de 27 cubes répartis en trois tranches de trois cubes par trois. Cette approche n'est pas tout à fait exacte puisqu'en réalité, il n'y a pas de cube central, comme on le voit sur la photo, mais elle a l'avantage d'être simple à conceptualiser.
- Quels sont les mouvements autorisés?
Quand vous tenez un Rubik's entre vos mains, tous les mouvements ne sont pas possible. En fait, la seule combinaison réalisable est de faire la rotation d'une tranche. Il y a trois tranches perpendiculaires à chacune des trois directions de l'espace. (Si vous n'êtes pas familier avec la géométrie dans l'espace, attendez le prochain article où tout deviendra plus limpide pour vous) Par rapport à l'axe vertical, par exemple, on peut considérer qu'il y a une tranche du haut, une tranche du milieu et une tranche du bas.

Une rotation de la tranche du milieu peut être considérée comme les rotations simultanées, et dans le sens opposé des deux tranches extérieures. Ainsi, on peut limiter le nombre de mouvements possibles aux rotations des faces extérieures sans diminuer les possibilités d'action. Cela permet de se rendre compte que pour chaque face, le cube au centre de la face est un point fixe par rapport aux autres cubes centriques. On le voit bien sur la photo qui précède cet article : physiquement, ce sont trois axes collés les uns aux autres qui maintiennent le reste de la structure du cube.

Si vous n'en n'êtes pas convaincus, je vous engage vivement à prendre un Rubik's Cube entre vos mains (votre frère ou votre ami Geek en aura forcément un à vous prêter), à maintenir le cube centrale d'une des faces à une position fixe et à tenter de déplacer les autres cubes centraux sans casser le Rubik's Cube (votre ami Geek serait tout triste). Convaincu?
Bien. Poursuivons !
- Effets de structure :
Les cubes centraux étant fixes les uns par rapport aux autres, on peut attribuer à chaque face une couleur : la couleur du cube central. Quand on essaye de résoudre le Rubik's Cube pour la première fois, une erreur commune consiste à ne pas prendre cela en compte et à essayer par exemple de reconstituer la face bleue sur la face blanche, ce qui ne peut pas fonctionner.

Nous avons six cubes centraux : un par face, mais quid de tous les autres cubes, me demanderez-vous?
En fait, il y en a deux sortes. Concentrons-nous sur une face. Autour du cube central, on huit cubes dont quatre sont situés sur un sommet du cube et quatre sont situés sur une arrète. Si l'on compte sur l'ensemble du cube, on a huit cubes sommets et douze cubes arrete.

6+8+12=26, ce qui fait 27 petits cubes si l'on y ajoute le cube fictif situé au centre du Rubik's.

Mais laissez-moi attirer votre attention sur les particularités de chacun de ces cubes. Tout d'abord, un cube d'une catégorie ne peut par aucun des déplacements cités plus haut se retrouver dans une autre catégorie.

Les cubes centraux : Coincés qu'ils sont au milieu de leur face, ils ne présentent qu'une face visible.
Les cubes sommets : Au bord du cube, ils présentent trois faces visibles à l'utilisateur.
Les cubes arrêtes : Entre deux cubes sommets et deux cubes centraux, ils présentent deux faces visibles.
Et en réalité, seule les faces visibles de chacun des petits cubes sont colorées. En effet, il est impossible par un des déplacements réalisables de retourner un cube par rapport aux axes centraux qui les soutiennent.

Voilà. J'espère vous avoir donné suffisement de grain à moudre.

Je vous conseille vivement de vérifier tout ce que j'ai dit en utilisant un Rubik's Cube physique. Rien de mieux pour vous convaincre que je ne suis pas en train de vous baratiner, et pour bien assimiler ces connaissances de bases qui seront nécessaires pour l'écriture de notre code.
Géométrie dans l'espace

Ces mots font généralement peur... Et pourtant, il va falloir que nous passions par là. Alors prenons notre courage à deux mains et vous verrez : ce n'est pas aussi barbare que ce que cela n'y paraît.

Pour situer un point dans l'espace, il est intéressant de construire un système d'axes qui permettent de le localiser. Dans le système cartésien, on défninit la position d'un point à l'aide de trois coordonnées. Chaque coordonnée correpond à la position du point sur l'un des axes de l'espace.

Il est donc nécessaire de se mettre d'accord sur le sens et la directiond es axes. Dans nos représentations, nous considérerons par convention que l'axe "z" est vertical, et orienté vers le haut (z est plus grand pour un objet plus haut); les axes x et y sont perpendiculaires l'un à l'autre et situés dans le plan horizontal. L'axe x donne la position d'un point dans un plan horizontal en terme de position droite et gauche. Il est orienté vers la gauche. L'axe y donne la position d'un point en terme d'avant arrière. Il est orienté vers l'avant.

Ainsi, pour résumer, un point est défini par des coordonnées [x,y,z].

Le point situé aux coordonnées [1,1,1] sera situé par rapport à l'origine du repère : une unité à gauche (1 suivant l'axe des x), une unité vers l'avant (1 suivant l'axe des y) et une unité vers le haut (1 suivant l'axe des z).
Le point situé aux cooronnées [-1,0,1] sera situé une unité à droite de l'origine sur l'axe des x, à la même position que l'origine sur l'axe des y et une unité au dessus de l'origine sur l'axe des z.

N'hésitez pas à jouer vous-mêmes à positionner des points dans l'espace et à trouver leur coordonnées. Nous allons bientôt mettre ces notions en pratique et il serait intéressant que vous y soyez habitués.
Télécharger ce document
Scilab

J'en vois certains se demander quand je finirais de tourner autour du pot pour entrer dans le vif du sujet : la programation.

Avant de programmer, il faut choisir un environnement de programation. Comme ce tutoriel a pour vocation d'être accessible à tous, j'ai cherché un outil de programation gratuit, simple d'installation et d'utilisation et donnant la possibilité de faire des représentations 3d sans trop se casser la tête.

Le logiciel de calcul numérique scilab, remplit tous ces critères. Je vous invite donc à le télécharger ici avant de poursuivre ce tutoriel.

Dans le prochain article, nous ferons nos premiers pas avec scilab. Pour les curieux, je vous invite à commencer à vous familiariser avec le logiciel en lisant le pdf que j'ai placé au dessus de cet article. il provient directement du site de scilab et permêt de se familiariser avec le logiciel, sans utiliser de fonctionalité trop avancée dont nous n'aurons de toute façon pas besoin pour ce projet.
Premiers pas

Vous avez téléchargé Scilab et vous mourrez d'impatience de l'utiliser? Cela tombe bien puisque c'est ce que nous allons faire.

Quand vous démarrez scilab, c'est la console qui s'affiche. On peut lui donner des instructions directement en console, mais pour ce que nous allons faire, mieux vaudra utiliser son éditeur de texte, Scinote afin de pouvoir sauvegarder notre travail au fûr et à mesure que le temps passe et que notre code s'etoffe.
Pour ouvrir l'éditeur de texte de scilab, cliquez sur l'icone en haut à gauche en forme de calepin. Une nouvelle fenêtre doit s'ouvrir. C'est ici que vous rentrerez les instructions que vous voudrez faire executer à Scilab. Ensuite, il vous faudra sauvegarder votre code (raccourci ctrl+S) et le charger dans la console (raccourci ctrl+L) afin de l'éxecuter.

Faisons un essai.
- Ouvrez Scilab !
- Ouvrez Scinote !
- Ecrivez ceci : plot3d !
- Utilisez le raccourci clavier ctrl+S pour enregistrer votre oeuvre ! (Vous devez le placer quelque part sur votre disque dur. Je vous conseille de faire un dossier Scilab où vous placerez tous vos fichiers si vous voulez suivre ce tutoriel)
- Utilisez le raccourci clavier ctrl+L pour l'exporter vers la console !
Et magie, si tout se passe bien, une fenêtre s'ouvre avec une courbe tracée dans l'espace.

Mais que c'est-il passé?

En programmation, on appelle fonction un objet informatique auquel on fournit un certain nombre de données (les paramêtres, ou arguments) et qui en retour nous renvoit un certain nombre de données (les résultats).
Il y a deux types de fonctions : celles que nous codons nous-même et celles qui sont déjà incluses dans Scilab. Ainsi, la commande : "plot3d" appelle une fonction. Ici, elle n'a reçu aucun argument. Son action est d'afficher un graphique en 3 dimensions.

Mais comment pourrions-nous utiliser cette fonction pour afficher, non pas cette très jolie courbe, mais par exemple quelque chose qui aurait l'apparence d'un Rubik's Cube ?
Il faudra utiliser des paramètres afin de préciser à la fonction plot3d ce que nous voulons exactement.

L'univers de Scilab commence à vous intéresser? Continuez de lire ce blog, car dans le prochain paragraphe, vous découvrirez la meilleure fonction qu'il propose !
Appel à l'aide

Comme promis, je vais vous dévoiler aujourd'hui la fonction la plus utile que Scilab propose. Il s'agit de la fonction help.

Cela doit être votre premier réflexe quand vous ne savez plus vraiment que faire. Evidemment, il ne suffit pas de taper la commande help pour que tous vos problèmes soient résolus. Il faut aussi savoir l'utiliser.

"Mais je ne sais pas comment faire !"

Vous avez de la chance : c'est l'objet de cet article. Alors découvrons ensemble cette fonction. Après avoir lancé Scilab, tapez : "help plot3d" soit dans l'invite de commande de la console directement, soit dans l'éditeur de texte (dans ce cas, n'oubliez pas : ctrl+L pour charger dans la console).

Vous devriez obtenir ceci :
Télécharger ce document
La première chose qui a pu vous marquer : tout est en anglais... Si vous ne parlez pas anglais, cela peut vous rebuter, mais sachez tout de même que vous pourrez obtenir un grand nombre d'information même sans comprendre la langue.

La première section : "Calling Sequence" (séquence d'appel) donne la liste des arguments obligatoires et optionnels qu'accepte la fonction plot3d.

La deuxième section décrit chacun de ces arguments. Avec un peu d'expérience, ces deux sections peuvent vous permettre d'apprendre pratiquement tout ce que vous avez à savoir sur une fonction.

La troisième section décrit brièvement la fonction. Ici, par exemple on peut lire ceci : "plot3d(xf,yf,zf,[theta,alpha,leg ,flag,ebox]) draws a surface defined by a set of facets." Ainsi, cette fonction permet de dessiner une surface définie par un ensemble de facettes. Cela pourrait bien avoir une utilité par rapport à notre problématique : manipuler un Rubik's cube.

La quatrième section donne des exemples d'utilisations. C'est une section très importante aussi, car souvent, il est plus simple de copier/coller un exemple et de l'adapter à un cas particulier que de comprendre par soi-même comment on utilise la fonction.

Enfin la section : "See Also" peut vous aider à trouver d'autres fonctions reliées si jamais celle-là n'avez pas apporté la réponse à votre question, et la section "Authors" recense les auteurs de cette page d'aide.

Exercice pour la prochaine fois : En utilisant la rubrique d'aide sur la fonction plot3d, essayez d'afficher un cube centré sur l'origine du repère et de côté 1. Si vous y arrivez, essayez de colorer chaque face d'une couleur différente. Sinon, ne désespérez pas, je viendrais à votre aide.
Si l'on commençait par un cube...

Avant de nous plonger dans la résolution du Rubik's cube, nous allons tenter d'en obtenir une réprésentation graphique. Vous vous en souvenez : Je vous avez dit que l'on pouvait représenter le Rubik's cube comme un ensemble de 27 sous-cubes. Quelle meilleure manière de représenter 27 cubes que de commencer par en représenter un?

Nous avons parlé de géométrie dans l'espace un peu plus tôt. Si vous avez bien compris ce que je disais, vous comprendrez aussi que les coordonnées des sommets d'un cube de diamètre 1 centré sur l'origine sont :

sommet 1 : droite arrière bas [-0.5 -0.5 -0.5],
sommet 2 : droite arrière haut [-0.5 -0.5 0.5],
sommet 3 : droite avant bas [-0.5 0.5 -0.5],
sommet 4 : droite avant haut [-0.5 0.5 0.5],
sommet 5 : gauche arrière bas [ 0.5 -0.5 -0.5],
sommet 6 : gauche arrière haut [ 0.5 -0.5 0.5],
sommet 7 : gauche avant bas [ 0.5 0.5 -0.5],
sommet 8 : gauche avant haut [ 0.5 0.5 0.5]

Ainsi, on peut reconstituer
la face du haut en reliant les sommets : [2 4 8 6]
la face du bas : [7 5 1 3]
la face gauche : [5 6 8 7]
la face avant : [3 4 8 7]
la face droite : [1 2 4 3]
et la face arrière : [1 2 6 5]

Si l'on pose un Rubik's cube sur sa face jaune, avec la face orange devant, les couleurs sont forcéments situés comme ceci :
face haute : blanche
face du bas : jaune
face gauche : bleue
face avant : orange
face droite : verte
face arrière : rouge.

Pour donner toutes ces informations à la fonction : "plot3d" (relisez l'aide si cela peut vous en convaindre) il faut rentrer le code suivant :
Télécharger ce document
Les phrases précédées d'un double slash (//) sont des commentaires. Ils sont là pour vous aider à comprendre le code.

Copiez/Collez ce texte dans Scinote puis chargez le dans Scilab (toujours ctrl+L) et vous devriez obtenir le même dessin 3d que celui qui précède cet article. Dans la fenêtre graphique, vous pouvez l'observer sous tous ses angles en utilisant l'icone en haut à gauche de la fenêtre.
Nos premières fonctions

J'ai conscience que le paragraphe précédent qui expliquait comment afficher un cube dans l'espace a pu être fastidieux. En pensant au fait qu'il va nous falloir en afficher 27 (souvenez-vous : nous allons représenter le Rubik's cube comme un ensemble de 27 cubes), j'imagine que vous pouvez rechigner à la tâche.

Mais je vous propose une alternative ! Nous allons créer notre propre fonction qui affiche un cube de côté égal à une unité graphique. Il faudra renseigner à cette fonction la position du centre du cube, en coordonnées [x y z], ainsi que l'agencement des couleurs qui sera une liste ordonnée. Et avec l'originalité légendaire du programmeur, je vous propose de nommer cette fonction : "plotcube".

En Scilab, cela se présentera comme suit :

function [ ]=plotcube(Position,Couleurs)
...
endfunction

Pour l'intérieur de la fonction, vous avez déjà fait le plus gros du travail. il suffira d'ajuster un tout petit peu le code du paragraphe précédent. Mais intéressons-nous aux deux lignes écrites ci-dessus !

On commence par le mot : "function" (avec un "u" et pas un "o" : c'est le mot anglais pour fonction) puis une liste qui représente ce que retourne la procédure. La liste est vide car la procédure (c'est un synonyme de fonction) affiche simplement le graphe et ne retourne aucune valeur à l'utilisateur. Ensuite vient le nom de la fonction : il s'agit ici de plotcube. Enfin, entre parenthèses : les arguments d'appels.

Pour appeler cette fonction afin d'obtenir le même résultat que la dernière fois, il suffira d'écrire dans la console Scilab (ou dans Scinote, sans oublier de charger) :

plotcube([0,0,0],[color("white"),color("yellow"),color("blue"),color("orange"),color("green"),color("red")]).

Ainsi, à chaque fois que l'on voudra afficher un cube, il suffira d'écrire une ligne de code au lieu de réécrire toute une page. Malins les informaticiens non?!

Et pour que vous assimiliez bien tout cela, prenons quelques autres exemples.

J'aimerais créer une fonction qui s'occupe de créer mon Rubik's cube virtuel (que j'appellerai "CreationRubix"), et une autre qui l'affiche en graphe 3d (que j'appellerai "AfficheRubix").

Ce pourrait ressembler à ceci :

function [ObjetRubix]=CreationRubix()
...
endfunction

function [ ]=AfficheRubix(ObjetRubix)
...
endfunction

Ainsi, la fonction CreationRubix retournerait à l'utilisateur l'objet virtuel : "ObjetRubix", et la fonction AfficheRubix utiliserait les caractéristiques de cet objet pour l'afficher.

Et aussi surprenant que cela puisse paraître, nous ne sommes pas très loin d'en être à ce point-là ! Continuez-donc à lire mon blog, et n'hésitez pas à poser des questions en commentaire si certains points vous semblaient obscurs.
Des fonctions, d'accord ! Mais je mets quoi dedans ?

C'est ce que nous allons voir au cours de ce paragraphe. Et les choses vont devenir amusantes !

Nous devons créer les trois fonctions décrites plus haut. Je vais vous expliquer les deux plus simples dans cet article? La troisième, un peu plus technique fera l'objet de l'article suivant.

Commençons par la fonction : "plotcube". Nous avons déjà fait 90% du travail. Si vous aviez bien compris la dernière fois, la seule nouveauté, c'est que l'on décale la position du cube (son centre était l'origine du repère la dernière fois) en ajoutant aux coordonnées de chacun de ces sommets les coordonnées du nouveau centre du cube.

Voici ce que cela donne pour la partie du code :
Télécharger ce document
Limpide n'est-ce pas ?

Maintenant, nous allons écrire la fonction qui affichera l'objet : Rubik's cube quand nous l'aurons créer. Pour ce faire, accordons-nous sur la définition que l'on en fait.

Nous avons dit que le Rubik's cube était un ensemble constitué de 27 sous-cubes.

Qu'est-ce qui différencie tous ces cubes?

Deux choses :
- Leur position (trois nombres réels)
- L'orientation de leur couleurs (six nombres réels définissant les couleurs : une par face)
Ainsi, un petit cube peut être représenté par une liste constituée de neuf nombres dont les trois premiers définissent la position du centre, et les six suivants définissent l'orientation des couleurs.

Pour l'orientation des couleurs, je fixe un ordre afin que nous puissions tous nous y tenir : [haut,bas,gauche,devant,droite,derrière].

Notre Rubix cube contiendra donc 27 vecteurs (un vecteur est un ensemble de nombres) contenant chacun neuf éléments décrirons un sous-cube. En mathématique, on appelle ce type d'objet : une matrice de 27 lignes et 9 colonnes (chaque colonne est un vecteur).

Nous appellerons cet objet : ObjetRubix

Remarque : en Scilab, les deux points servent à créer une liste. Exemple : le vecteur :
1:9
est équivalent au vecteur :
1 2 3 4 5 6 7 8 9

Ainsi,
ObjetRubix(5,3) renvoie au troisième élément du vecteur désignant le cinquième sous-cube (donc sa position suivant l'axe des z)
ObjetRubix(8,1:3) renvoie à toutes les coordonnées (x, y et z) du sous-cube n°8.
ObjetRubix(8,4:9) renvoie à la liste de toutes les couleurs des faces dans l'ordre suivant : [haut,bas,gauche,devant,droite,derrière].

On peut donc afficher le sous-cube n°5, par exemple en utilisant la fonction plotcube de la manière qui suit :

plotcube(ObjetRubix(5,1:3),ObjetRubix(5,4:9));

Pour afficher tout le cube, ce n'est pas beaucoup plus difficile :

for i=1:27
plotcube(ObjetRubix(i,1:3),ObjetRubix(i,4:9));
end;

C'est une boucle. On a dit à Scilab d'executer l'ensemble des commandes comprises entre le for et le end pour i prenant toutes les valeurs entières de 1 à 27.
Cela permettra l'affichage de notre cube à partir du moment où nous l'aurons créer (remplissage de la matrice).
Télécharger ce document
Entrez dans la matrice !

Comme nous l'avons déjà dit plusieur fois, le cube est constitué de 27 sous-cubes, tous affectés d'une position (suivant x,y et z) et d'une liste ordonnée de couleur.

Au moment de sa création, on peut déclarer que la liste des couleurs est la même pour chaque sous cubes (ils sont tous dans le même sens au départ, ce qui donne l'apparence d'un cube complet homogène). Cependant, il peut être intéressant de retirer les couleurs des faces intérieures des sous-cubes afin de pouvoir les identifiers plus facilement par la suite.

Ainsi,On commenceras par créer nos 27 sous-cubes à l'aide de trois boucles imbriquées, en leur donnant tous le même ordonencement de couleurs.

Ensuite, nous supprimerons toutes les couleurs non-visibles. Pour ce faire, nous utiliserons l'instrucition conditionnelle : la commande "if".

Voici un exemple :

if ObjetRubix(i,1)==-1 then // si x=1 (on notre cube est sur la face de droite)
ObjetRubix(i,3+3)=0 //Alors on supprime la couleur du côté gauche du sous-cube i
end;

Ayant compris cette ligne de code, vous serez capables de comprendre aisément l'ensemble de la procédure qui suit.
Télécharger ce document
Fin de la première partie

Si vous m'avez suivi jusqu'ici, félicitations ! Vous venez de passer du premier au deuxième échelon de l'évolution sur l'image précédente.

Vous aves appris un certain nombre de notions fondamentales qui vous seront forcément utiles dans la suite de ce projet, ce qui vous a permis de coder une fonction pour afficher le Rubik's cube.

Evidemment, vos efforts ne s'arrêtent pas là. Au programme pour la suite de ce blog :
- Comment modéliser les rotations des tranches ?
- Comment résout-on le Rubik's cube à la main ?
- Comment créer un code Scilab qui résolve le Rubik's Cube?
Si vous avez des suggestions concernant la suite du blog, elles sont les bienvenues. Si vous avez lu jusqu'ici et que vous avez aimé ce que vous avez lu, n'hésitez pas non plus à me le faire savoir en cliquant sur "j'aime" et en parlant de ce blog autour de vous.