L’heuristique divin du cube Rubik 2x2x2

Dans un rêve, Duckkcud a rencontré le dieu Heurik… Il lui demandait :

      DUCKKCUD - Ô grand dieu Heurik, peux-tu me dire ce qu’est l’heuristique divin du cube Rubik 2x2x2 ?

      HEURIK -  D’abord je ne suis pas un grand dieu. J’en suis un jeune et t’invite à me parler de façon conviviale. Si les humains ont de l’admiration pour le divin, je dirais que bien des dieux, comme moi, ont de l’admiration pour l’humain, surtout pour leur convivialité et leur humilité.

      DUCKKCUD – Alors, c’est quoi l’heuristique divin ?

      HEURIK -  Un heuristique, c’est un bon chemin. Quand on est perdu dans un labyrinthe ou pris dans un dédale de choix ou de chemins, parfois, selon l’emplacement, il y a localement un indice pour optimiser son parcours vers la destination voulue. C’est comme le problème du commis voyageur qui veut minimiser son kilométrage pour visiter tous ses clients. Il peut prendre des jours à envisager toutes les possibilités pour l’optimum ou bien simplement aller au plus près au fur à mesure avec passablement d’efficacité. Ainsi en est-il pour bourrer un coffre d’auto de bagages. Commencer avec les plus gros morceaux est un bon chemin, si encore il y a une solution.

Plusieurs méthodes ont été élaborées afin d’établir le bon chemin pour la résolution du cube de Rubik. Le chemin divin est imbattable en ce qui concerne le nombre de coups pour la solution.

      DUCKKCUD -  Je comprends ce qu’est un heuristique mais qu’aurait-il de divin pour un simple cube ?

      HEURIK -  Hé bien, je connais toutes les combinaisons.

      DUCKKCUD -  Je peux l’imaginer, mais qu’est-ce que cela donne ?

      HEURIK -  Je connais le niveau de chacune.

      DUCKKCUD -  Qu’entends-tu par niveau ?

      HEURIK -  Le niveau 0 est celui du cube parfait avec chaque face toute colorée identiquement. La valeur du niveau d’un cube mélangé représente combien de coups ( ou de mouvements d’un quart de tour ou d’un demi tour ) sont nécessaires pour solutionner ce cube.

      DUCKKCUD - Je comprends. Si je savais à quel niveau un cube est mélangé, j’aurais juste à tester les  mouvements de rotations possibles et choisir la première de ces rotations qui donne un niveau inférieur. Ainsi de suite pour chaque prochain niveau inférieur afin de solutionner rapidement le cube. On pourrait cheminer directement à la solution sans besoin de formules ou de longue méthode.

      HEURIK -  Tu sembles comprendre vite quand on t’explique lentement.

      DUCKKCUD -  C’est bien beau, mais comment savoir ce fameux niveau ?

      HEURIK -  Je les ai tous mémorisés. C’est pour cela qu’on me dit divin.

      DUCKKCUD -  Effectivement divin. Y a-t-il un truc ?

      HEURIK -  Oui, la collection de 12 livres que ma mère Heurika m’a donnée quand j’étais petit.

      DUCKKCUD -  Puis-je le voir pour y croire ?

      HEURIK -  Bien sûr, l’incrédule. Voici la collection. Les 11 premiers livres contiennent chacun un million de ces niveaux correspondants chacun à une combinaison particulière des couleurs du cube. Chaque livre a mille pages de mille inscriptions. Le dernier, le douzième, en contient moins. Voici, dans le tome 2, la page 164 :

Heuristique divin du cube Rubik 2x2x2

 

Tome 2                                            page 166

   0          10         20         30         40         50         60         70         80         90        

 

0  9....A.9.. 4..5...7.. 9A...8.9.. .A.5...9.9 ....A..A.. 97...8...9 8...A.9... A.8...8... 8..77...9. 9....9.9..

 

1  .8..8.A.A. ...A.8.A.. .8...7..9A ..9...A... A.9...A.8. A..7...8.. .9..A9...A .8..9....7 8....A.A.. A...9A...9

 

2  ...B7...9. .A.B...A.A ....0..A8. ..9.A...7. ..A..99..A ...9..7... 9..B9..A.. .9..9...9. .A..8.9.8. ...A.8.9..

 

3  A....A8... .8.A..9.A. ..8.9...A. ..A..9.9.9 ...8.8.... A..9.8...A ..79...A.A ....A.7... A.8.A..9.. ..9A...9..

 

4  .99...A..A ...9..9A.. 9...9..7.. 8.9....87. ...8..7..9 .A.4...A.9 ...8...9.. 79...9.A.. .9...6..99 ...9.9..8.

 

5  ..9.9...A. ..8..9..97 ...A...98. ..5.9...8. A...9...A. .A..89...9 ...AA...8. 7..8....7. 7...8.9..A ...A..AA..

 

6  A...9.8..9 ...8..9... A..9.9.9.. .8.8....A. .9..A9...9 ...79...8. ..9.A...8. 8.A..A..9. ..8.A...9. ..9..97...

 

7  .98....A.A ..A..8...9 ..AA...9.9 ....9.A.A. ...9.9.A.. 8...8.9... .8.9...9.. 79...9..7. ..98..8... .8A....A.A

 

8  ..8..9.9.. .A.A....A. .99...9.A. ..9...8..8 ..4.8...A. 9.9..8...7 ...8..AA.. .9.7....88 ...9...8A. ..7..7...9

 

9  ..98..A... 8...8..8.4 .9...7.9.. 9..8....7. A...9.5... 99...A...A 9...8...77 ...9...9A. ..9..7...8 ..89...A.8

   0          10         20         30         40         50         60         70         80         90        

 

Tome 2                                           page 166

 

 

À cette adresse, sur la ligne 2, dans la colonne 24, est le seul 0 de toute la collection. Ce chiffre représente le niveau du cube parfait. Tous les autres chiffres de la page expriment un niveau pour une combinaison de couleurs de cube mélangé. C’est chiffré en hexadécimal; le niveau maximum est 11. En hexadécimal, en plus de 10 chiffres de 0 à 9, on a 6 lettres comme chiffrement. La lettre A vaut 10, B vaut 11… F vaut 15.

Cela a pris 12 volumes de mille pages de mille inscriptions de niveaux pour recueillir les 11 022 480 combinaisons possibles. Le dernier tome n’a qu’une centaine de pages.

      DUCKKCUD -  Fantastique ! Mais comment fait-on pour savoir qu’une coloration spécifique d’un cube mêlé correspond à tel endroit dans le volume ? Je vois une numérotation. Y a-t-il un code ?

      HEURIK -  Je vois que tu portes bien ton nom avec ton code. Oui, il y a un code ou une façon de chiffrer cet endroit que j’appelle adresse. Cela se calcule de façon analogue à la numération digitale ou hexadécimale. Pour les nombres décimaux, les chiffres sont pondérés selon leur rang de droite à gauche en unité, dizaine, centaine… Soit la pondération de 1, 10, 100, 1000, … 10n …

Par exemple, le codage de 7803 est simple :

n. décimal

7

8

0

3

 

 

 Pondération

1000

100

10

1

 

 

 Produit

7000

800

0

3

Somme =

7803

C’est un peu trivial.

      DUCKKCUD -  Trivial juste parce qu’on est habitué à cette numérotation; c’est un code bien arbitraire mais il a l’avantage de se compter sur les dix doigts humains.

      HEURIK -  Pour les hexadécimaux, c’est pondéré 1, 16, 256, 4096…16n…

Essayons le nombre hexadécimal C0DE. 

n. Hexadécimal

C

         0

D

E

 

 

 Pondération

4096

256

16

1

 

 

 Produit

49152

0

208

14

Somme =

49374

Un avantage de ce code est d’exprimer de grands nombres de façon compacte.

Pour le Rubik 2x2x2, on a 8 coins de 3 cases, soit en tout 24 cases. Mais puisqu’on peut négliger un coin qui peut rester fixe, on considère 7 coins qui peuvent occuper 21 cases. On pourrait coder un nombre de 7 chiffres dans une base de 21. Cela offrirait une grande liste d’adresses possibles mais qui nécessiterait pour les compiler environ 2000 livres comme les miens.

      DUCKKCUD -  Ouf ! J’imagine qu’on peut faire mieux en factorisant la pondération car le nombre de cases que peut occuper un coin diminue à mesure que les coins précédents sont situés. Ce nombre diminue de 3 par coin placé, soit 21, 18, 15, 12 ,9 ,6, 3, 1. De cette façon, on peut composer un numéro d’identification de chaque combinaison en ne nécessitant qu’un douzaine de livres.

      HEURIK -  Exactement.

Ainsi, la pondération s’établit selon un ordre factoriel 524880, 29160, 1944, 162, 18, 3, 1 pour un total de 11 022 480 combinaisons affichées dans ma collection.

      DUCKKCUD -  Je vois que tu as composé ainsi un numéro d’identification pour tous les cubes, mêlés ou pas. Tu appelles ce numéro une adresse en analogie à une adresse postale. Pourrais-tu me donner un exemple de codification de cette nébuleuse adresse ?

      HEURIK -  D’accord. Commençons par  numéroter les cases comme ceci sur une représentation 2D du cube parfait.

 

 

 

0

 

 

 

 

1

2

 

 

 

3

4a

5b

6

7

8

9

10c

11d

12

13

 

 

14

15

 

 

 

 

16

17

 

 

 

 

18e

19f

 

 

 

 

 

20g

 

 

 

On remarque d’abord qu’il y a un coin non numéroté. C’est parce qu’il est fixe par rapport aux autres coins qui sont mobilisables par les 9 rotations de base, soient celles des trois faces Droite, Haute et Avant, en sens horaire ou anti-horaire, ainsi que les 3 rotations d’un demi-tour. On n’aura donc que 7 facettes mobiles à considérer pour identifier le cube selon sa coloration.

Considérons les 7 facettes : a , b , c et d pour les blancs, e, f et g pour les jaunes. Elles serviront de référence pour chacun des coins mobiles du cube.

Ensuite, on trouve le quantième de la case où est positionnée chacune de ces facettes de référence.

      DUCKKCUD -  Oui ?

      HEURIK -  Prenons pour commencer le cube parfait et trouvons ses quantièmes.

Le premier est facile. Le coin a est en quatrième position. Son quantième est 4.

 Maintenant, les cases #1, #3 et #4 ne sont plus disponibles.

Le coin b est en #5. Son quantième est 2 car c’est la deuxième case de libre en commençant à compter par zéro.

 Alors, les cases #1, #2, #3, #4, #5 et #6 ne sont plus disponibles.

Le coin c est en #10. Son quantième  est 4 car c’est la quatrième case de libre en commençant à compter par zéro.

 Ainsi de suite pour les autres coins… On obtient enfin ce tableau.

 

Coin

a

b

c

d

e

f

g

 

 

Couleurs

Blanc

Rouge

Bleu

Blanc

Bleu

Orange

Blanc

Vert

rouge

Blanc

Orange

Vert

Jaune

Rouge

Vert

Jaune

Vert

Orange

Jaune

Orange

Bleu

 

 

Position

4

5

10

11

18

19

20

 

 

Quantième

4

2

4

3

6

4

2

 

 

 Pondération

524880

29160

1944

162

18

3

1

 

 

 Produit

2099520

56320

7776

486

108

12

2

2166224

Somme des produits = Adresse

 

On calcule alors un nombre qui est la somme des quantièmes x leur poids respectif. Chaque poids est le produit du poids du rang précédent x le nombre de possibilités restantes.

C’est analogue à la codification décimale ou hexadécimale.

      DUCKKCUD -  Wow ! On obtient donc l’adresse 2166224 ou 2 166 2 24. Le niveau du cube parfait est inscrit au tome 2,  la page 166, la ligne 2, et le 24 ième caractère de cette ligne.

      HEURIK -  Je vois que tu saisis bien. Essayons un exemple moins parfait.

 

 

 

 

0

 

 

 

 

1

2b

 

 

 

3

4f

5

6

7e

8

9

10

11c

12

13

 

 

14g

15

 

 

 

 

16

17

 

 

 

 

18d

19a

 

 

 

 

 

20

 

 

 

 

      DUCKKCUD -  Je vais essayer ta méthode de calcul de l’adresse en remplissant un tableau analogue à celui que tu m’a montré. En retraçant les couleurs de chaque facette de coin de référence.

Le a blanc du coin blanc-rouge-bleu est positionné à la case #19. Son quantième est donc 19.

Le b blanc du coin blanc-bleu-orange  est en position #2 pour un quantième de 2.

Le c blanc du coin blanc-vert-rouge est en position #11. Son quantième est 8 car les 3 cases #2, #5, #6 sont déjà occupées par les coins précédents.

 Et ainsi de suite pour obtenir ce tableau…

Coin

a

b

c

d

e

f

g

 

 

Couleurs

Blanc

Rouge

Bleu

Blanc

Bleu

Orange

Blanc

Vert

rouge

Blanc

Orange

Vert

Jaune

Rouge

Vert

Jaune

Vert

Orange

Jaune

Orange

Bleu

 

 

Position

19

2

11

18

7

4

14

 

 

Quantième

19

2

8

10

4

2

2

 

 

 Poids

524880

29160

1944

162

18

3

1

 

 

 Produit

9972720

58320

15552

1620

72

6

2

10048292

Somme des produits = Adresse

 

Cela donne enfin l’adresse 10048292 ou 10 048 2 92.

      HEURIK -  Très bien. Quel niveau donc pour cette adresse?  Moi, je m’en souviens par cœur. Toi, fouilles le tome 10 de l’heuristique divin, page 48, ligne 2, le 92 ième caractère. Que vois-tu ?

      DUCKKCUD -  J’y vois la lettre A à cette adresse , soit le niveau 10 pour ce cube mélangé.

      HEURIK -  Exact. On est donc à 10 coups de la solution qui s’effectuera par une séquence de rotations. Définissons tout de suite les rotations de base et leurs abréviations :  D pour rotation du côté Droit du cube dans le sens horaire; D- pour tourner en sens inverse. On a aussi les rotations H pour Haute ou dessus et A pour Avant ainsi que la H- et la A- en sens anti-horaire. À cela s’ajoutent D2, A2, et H2 pour les 3 rotations de demi-tour. À chaque niveau, il faudra envisager systématiquement, une à une, ces 9 options de rotation et suivre le bon chemin, c’est-à-dire une rotation qui descend de niveau.

Considérons, pour commencer, la rotation D. Par cœur, je sais que j’obtiens alors un niveau de 9 avec cette rotation. C’est bon. Je ne me pose pas plus de question et j’adopte ce premier mouvement gagnant.

Je suis maintenant au niveau 9 et recommence à tester une à une les 9 rotations sur ce cube pour trouver celle qui obtient un niveau inférieur. Ce n’est qu’en testant la rotation A2 que  je vois qu’elle mène à un niveau de 8. Go pour A2.

Je suis donc maintenant au niveau 8.

Ici, les rotations D, D-, D2, A, A-, A2 et H mèneraient à un niveau de 9. Pas bon.

Mais H- fonctionne et est adopté pour m’avancer au niveau 7.

Je teste ainsi de suite… pour obtenir finalement une séquence de seulement 10 coups :

D A2 H- D- H A2 H A H2 A2

Veuillez excuser ma rapidité mais c’est ma compulsion d’admirer le jouissant jaillissement des couleurs unies qui m’anime comme un certain petit prince pour les couchers de soleil.

Dans tous mes volumes de l’heuristique divin, tu ne trouveras pas de niveau plus grand que B. Donc 11 est le maximum de coups pour solutionner efficacement n’importe quel cube Rubik 2x2x2.

      DUCKKCUD - Je suis ébaubi. Puis-je apporter avec moi cette divine collection puisque tu la connais par cœur ?

      HEURIK -  Que non ! C’est un cadeau de ma mère.

      DUCKKCUD -  Il n’est sûrement pas en librairie.

      HEURIK -  Pas que je sache. Cependant, tu peux t’en composer un.

      DUCKKCUD -  Comment ? Cela va être long.

      HEURIK -  Très long à la main. Mais ce n’est pas si compliqué. Tu prépares tous les volumes en blanc pour les niveaux à consigner mais en ayant soin de bien inscrire les numéros des tomes, pagination et numéros de lignes…

Puis tu inscris 0 à l’adresse 2166224 du cube parfait.

Tu trouves ensuite toutes les 9 adresses des cubes obtenus par les 9 rotations et tu les consignes avec la valeur 1.

Tu recommences, pour toutes les adresses de niveau 1, à tester les 9 rotations pour chacune et écrire le niveau 2 à leurs adresses correspondantes. Si une adresse est déjà numérotée d'un niveau inférieur, on ne la change surtout pas car un meilleur chemin s'y rend.

Et tu recommences pour toutes les adresses de niveau 2… et ainsi de suite, en montant graduellement de niveau… jusqu'à ce qu'un niveau ne se retrouve plus, c'est à dire 12 pour le cube 2 x 2 x 2.

      DUCKKCUD -  Je remarque que les addresses marquées d'un point au lieu d'une valeur signifient que ces cubes sont impossibles, comme ceux dont on aurait twisté un coin d'un tiers de tour. Ouf ! Jamais je ne parviendrai à écrire un tel ouvrage en des centaines, des milliers de vies. Je ne suis pas un dieu.

      HEURIK -  Et avec un ordinateur, penses-tu que tu pourrais y arriver ?

      DUCKKCUD -  Bien là, tu soulèves un point intéressant. Ce serait peut-être abordable.

      HEURIK -  J’ai bon espoir car ma collection serait logeable dans un fichier de 11 022 480 octets. Soit 21 x 18 x 15 x 12 x 9 x 6 x 3.

      DUCKKCUD -  L’heuristique divin est donc humainement abordable. Pendant que j’y pense, as-tu une collection pour le cube Rubik 3x3x3 ?

      HEURIK -  Non, mais ma mère Heurika en a une collection complète. Au lieu du 107, on parle de 1018 tomes.

      DUCKKCUD -  Ce doit être toute une bibliothèque divine !

      HEURIK -  Ces livres, couchés à plat par terre, une douzaine d’épais, peuvent couvrir toute la surface de votre planète Terre. Je te laisse imaginer la grandeur de son château…

 

Ding ! Duckkcud vient de se réveiller. À l’écran, l’heuristique divin est apparu après quelques jours de calcul sur son vieux PC en ce 15 janvier 1997. Quel rêve !