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
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.
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.
Sur les 64 cubes, il a 45 virages. En terme de combinaisons ça donne :
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.
Ensuite il faut qu’on reste à l’intérieur d’un cube de dimension 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?
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.
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.
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.
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:
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!
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.
Sauf que non! Rebondissement de dernière minute, en soulevant le cube il y a un problème.
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.
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 
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 :
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.
Mes Projets
Mon CV
Mes photos
Mes Tweets