Algorithme du Diable

La question de l'algorithme de Dieu étant

Quelle est le nombre minimum de mouvements pour atteindre la solution ?

Il est également légitime de se poser la question
Quelle est le nombre maximum de mouvements pour atteindre la solution ?

On peut l'appeller le Nombre du Diable

Cependant, la réponse à cette question est l'infini, en effet, il suffit de tourner toujours la même face sans arret.
 

Mais il si l'on ajoute la conditon : une configuration ne peut être atteinte qu'une seule fois, alors il y a une solution, le nombre de configuration étant fini (4.3 x 10¹⁹ pour le 3x3).

Cet algorithme a même un nom en mathématique, on l'appelle un circuit hamiltonien

Un circuit hamiltonien est un cycle qui passe par toute les configurations une seule fois jusqu'à revenir à son point de départ.

                                          

on peut déjà remarquer que le nombre du diable est égale au nombre de configuration du casse tête

N_diable = N_combinaison 

ainsi

N_{diable (3x3)} = 43 252 003 274 489 856 000

N_{diable (2x2)} = 3674160

Maintenant, la question est:

Est-il possible de trouver un circuit hamiltonien pour un casse tête ?

La réponse est oui. D'ailleurs, on en a déjà trouver un pour le 2x2 et le 3x3 (source)

Pour le 2x2x2 : 

Le nombre de coup de l'algorithme n'étant "que" de 3674159, il est possible de tout écrire dans un fichier texte que vous pouver télécharger
 

Pour le 3x3x3 :

Un circuit hamiltonien a également été trouvé pour le 3x3 (source)

Le nombre de coup de l'algorithme étant  43 252 003 274 489 855 999, il est impossible de tout écrire dans un fichier texte

il devient donc obligatoire de poser des varibales intermédiaires

vous pouvez télécharger cet algorithme ici

* Quelques propriétés interressantes de ce hamiltonien : 

répartition des différents coups pour ce circuit :

U:  10,898,125,406,064,467,088
U': 10,727,912,135,641,656,820
R:  10,901,458,532,532,248,688
R': 10,724,506,023,073,643,108
D:             588,588,720,174
D':            588,588,580,818
L:                     268,288
L':                    268,288
F:                       1,370
F':                      1,358
B:                           0
B':                          0

* S'il venait à Feliks l'idée d'éxécuter cet algorithme, lui qui tourne le cube si vite (environ 9 coups par secondes) et avec tant de déxtérité, il lui faudrait

43 252 003 274 489 856 000/9 = 4 805 778 141 609 984 000 secondes = 152 390 225 190 années = 11.123 l'age de notre univers (13.7 milliard d'années)

autant dire que ce n'est pas envisageable.