Résoudre le King Snake Cube 4×4

Le King Snake Cube 4×4 est un casse-tête. King Snake parce que c’est un serpent, Cube parce qu’il faut en faire un cube, 4×4 parce que c’est sa dimension.

Notre mission sera de le résoudre, et je vais vous montrer pourquoi le recours à l’outil informatique est indispensable.

Présentation du problème

cube
Le cube est fait. Pour l’instant tout va bien.

Le King Snake est un croisement entre un échiquier et un Rubik’s cube. C’est un cube constitué de plein de petits cubes en bois. Ils tiennent parce qu’ils sont tous reliés ensemble.

La première étape consiste à le défaire. C’est très facile il suffit de trouver l’extrémité et de le dérouler.

defaire

 

Il est défait. Rien ne va plus.
Il est défait. Rien ne va plus.

On obtient un serpent. On voit donc comment les cubes sont reliés ensemble : il y une ficelle qui traverse tous les cubes d’un bout à l’autre.

Ce serpent ressemble au King Snake : une espèce qui a des rayures blanches et noires. C’est elle qui a donné son nom au casse-tête.

Bref le plus dur est à venir : il va falloir reconstituer le cube. Le plus sûr aurait été de noter comment il était fait en le défaisant mais… j’ai oublié de le faire

Comment fonctionne ce casse-tête

A travers tous les cubes passe une ficelle. Lorsque cette ficelle rentre d’un côté et sort sur le côté, il y a un virage. A ce moment on peut faire tourner le cube sur lui-même.

virage

Pour chaque virage il y a 4 possibilités pour les 4 directions. Trouver la solution, c’est trouver tous les virages que doit faire le serpent pour reformer le cube.

snake_avec_virages

Sur les 64 cubes, il a 45 virages. En terme de combinaisons ça donne :

4^{45}=1\ 237\ 940\ 039\ 285\ 380\ 274\ 899\ 124\ 224 chemins possibles

En réalité tous les chemins ne sont pas possibles, car il y a des contraintes physiques.

Déjà le serpent ne peut pas aller à un endroit d’où on vient.

impossibilité 2
Le cube en surbrillance ne peut pas être tourné vers le bas, parce qu’il y a déjà un cube.

Ensuite il faut qu’on reste à l’intérieur d’un cube de dimension 4.

impossibilité 1
Le cube ne peut pas aller où il est, parce qu’on dépasse la taille de 4.

A priori ça fait beaucoup moins de combinaisons à tester. Mais rassurez-vous il en reste toujours des millions.

Bilan : à moins d’avoir un stagiaire à disposition, on ne peut pas résoudre ce casse-tête méthodiquement en testant tout. Et même avec un stagiaire très rapide ça peut prendre des années.

Il va falloir faire preuve d’astuce!

Comment le résoudre

Si vous êtes très chanceux vous pouvez essayer au hasard. C’est comme ça que font les gens qui essaient. A la fois il y a bien des gens qui gagnent au loto, donc pourquoi pas!

En étant plus raisonnable, on peut essayer de faire appel à la logique. Avez vous remarqué la présence de portions du serpent contenant 4 cubes à la suite?

Le cube défait a des des portions de 4 cubes à la suite
Ils prennent toute la largeur du cube. Une bonne idée serait donc de les placer en premier, et de résoudre le casse-tête à partir de là. Comme pour le Tangram : on commence par placer les plus grosses pièces.

Deux portions de 4 sont très proches, on regarde donc comment les placer.

alignement des blocs de 4_1 alignement des blocs de 4_2

alignement des blocs de 4_3 alignement des blocs de 4_4

Les 4 positions sont chacune le début d’un million de combinaisons possibles. Pour tout dire ça ne nous aide pas beaucoup. Et même pas du tout

Heureusement il nous reste une dernière carte à jouer : celle de la programmation.

Il y a des millions de cas à tester, eh bien qu’à cela ne tienne : l’ordinateur va les tester tous, et nous donner la solution. Un ordinateur c’est bien : comme un stagiaire c’est à la fois obéissant et gratuit. L’avantage c’est que c’est beaucoup plus rapide. Même l’ordinateur le plus lent au monde est plus rapide que le stagiaire le plus rapide qui soit. Enfin, à vérifier.

Modélisation du problème

Pour résoudre le problème, il faut arriver à le modéliser, et de préférence le plus simplement possible. Reprenons notre serpent.

Il est défait. Rien ne va plus.

On va partir de la gauche du serpent, et noter de façon absolue la direction qu’il doit prendre pour former le cube. Pour ça on utilise un petit repère.

repere

Pour le début il y a beaucoup de situations symétriques. La première direction est complètement arbitraire. Donc on dit que le premier bloc de 3 cubes va vers l’avant. Pour le second virage la situation est également symétrique, donc on dit là encore arbitrairement qu’il va vers la droite. Pour la suite par contre le chemin peut varier donc il va falloir commencer à tout tester.

La solution sera une succession de directions à faire prendre au serpent. Pour simplifier on note juste les initiales des 46 directions:

adxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Ecriture d’un algorithme

Notre algorithme doit tout tester. Donc on commence par tester un virage en allant dans une première direction. Si la direction est possible on va au virage suivant et à nouveau on teste un premier virage. Quand une direction n’est pas possible on teste la suivante, et quand on a testé toutes les directions d’un virage mais qu’aucune n’est possible on revient en arrière et on teste une autre direction. Et ainsi de suite.

Si les directions à tester étaient A, B et C, on testerait de cette façon : A, AA, AAA, AAB, AAC, AB, ABA, ABC, AC, ACA….. Avec en plus le fait de retirer les mots dont le début n’est pas possible. Si AB n’était pas possible, tous les chemins qui commencent par AB ne sont pas possible. Donc on passerait directement de AB à AC.

De cette façon on aura testé toutes les vraies possibilités. Ça s’appelle du backtracking et c’est un algorithme récursif, c’est à dire qu’il s’agit d’une même fonction qui s’appelle elle-même. Ce type d’algorithme est délicat à écrire, mais souvent très puissant puisqu’en très peu de lignes il peut faire tout le travail. Voici son écriture simplifiée :

Fonction tester_un_virage(position)
  Pour chaque virage
    Si position + virage est possible Alors
      Si position + virage est une solution Alors
        afficher position + virage
      Fin Si
      tester_un_virage(position + virage)
    Fin Si
  Fin Pour
Fin Fonction

tester_un_virage(position_initiale)

Ce problème est classique, il est dit de type NP. Avec ces problèmes il est facile de vérifier si une solution proposée marche, mais le nombre de test à effectuer grandit de façon exponentielle en fonction de la taille du problème. Ici la taille correspond à la dimension du cube. Ces problèmes ne sont pas toujours résoluble. Le risque est que le programme mette beaucoup trop de temps à trouver des solutions. Si c’est un jour c’est long mais encore ça va. Si c’est un an ça posera davantage de problèmes. Et même les plus gros ordinateurs actuels ont leurs limites.

Exécution du programme

J’ai écris un code en C++. Il a été bien optimisé, pour tourner aussi vite que possible (le code source est disponible sur GitHub).

Et bonne nouvelle au bout d’une minute j’obtiens un résultat!

adrdahrbghabadbahgbghdrghdagrbghabrdabgrdrgbah

Reconstituer le cube à partir de la liste d’instructions n’est pas très dur, il faut juste rester bien concentré et garder en tête la direction du repère. Pour ceux qui connaissent ça ressemble beaucoup à l’application de générateurs du Rubik’s cube. Une série d’instructions à appliquer à la suite avec des lettres correspondant aux faces à tourner.

cube
Le cube est résolu!

Sauf que non! Rebondissement de dernière minute, en soulevant le cube il y a un problème.

solidité
Ça ne tient pas!

Le chemin que prend le serpent n’en fait pas un cube suffisamment solide. Alors qu’au début le cube était tout ce qu’il y a de plus solide. L’explication est simple : il y a plusieurs solutions, et certaines sont moins bonnes que d’autres.

Donc il faut faire tourner le programme jusqu’au bout. Au bout d’une heure de calcul, et 1 854 768 620 positions testées, le programme a trouvé 8 solutions différentes. J’ai colorié les parties de solutions en commun.

adrdahrbghabadbahgbghdrghdagrbghabrdabgrdrgbah
adrdahrbghabadbahgbghdrghdagrbghabrbadhrbrgbah
adrdahrbghabgrhahabgrbahabadhrdabrhgbgaghdhgrd
adrdahrbghahadhabghgbdrgbdagrhgbahrdahgrdrghab
adrdahrbghahadhabghgbdrgbdagrhgbahrhadbrhrghab
adrdahrbghahgrbabahgrhabahadbrdahrbghgagbdbgrd
adrbgahdrbrhrdababahgrhrdbdhgbahdbaghgbrgahrda
adrbgahdrbrhrdabahabgrbrdhdbghabdhagbghrgabrda

Certaines se ressemblent beaucoup. J’ai déjà testé la première, donc je ne vais pas m’amuser à tester la seconde, on voit bien qu’elle est quasiment identique. Pareil pour les solutions 4 et 5 : il ne suffit d’en tester qu’une.

Et ça marche effectivement la troisième est solide

Fantastique! ça tient!
Fantastique! ça tient

Au final j’ai quand même tout testé : parmi les 8 il n’y en a que 2 qui sont suffisamment solides. Elles sont d’ailleurs plus techniques à réaliser, et je vous garanti que ça n’est pas du tout le type de mouvement qu’on fait naturellement en essayant au hasard (donc si vous vouliez essayer au hasard c’était raté d’avance). Un problème qu’on aurait pu avoir est qu’une solution ne soit pas réellement faisable (avec un nœud par exemple). Mais ça n’est pas le cas.

Les deux vraies solutions, qui se ressemblent beaucoup :

adrdahrbghabgrhahabgrbahabadhrdabrhgbgaghdhgrd
adrdahrbghahgrbabahgrhabahadbrdahrbghgagbdbgrd

Voilà c’est fini j’espère que cet article vous a plu. Si vous connaissez une façon de résoudre ce casse-tête sans programmation dites-le moi! Après tout il y a peut-être des génies parmi vous

N’hésitez pas non plus à proposer en commentaires d’autres casse-têtes à résoudre où l’informatique peut jouer un rôle.

portrait

Johan van Santen

Développeur fullstack web et Android indépendant.

Après avoir travaillé 4 ans en banque d’investissement et dans du développement de logiciels topographique, j’ai travaillé sur mes projets d’applications Android et ma plateforme web App-Types. Aujourd'hui je suis à plein temps sur mon nouveau projet Random Lunch.

   

Commentaires

commentaire