Connaissez-vous le jeu des tours de Hanoï ?
Ce célèbre jeu créé au XIX ème siècle a passionné de nombreuses personnes par sa complexité !
Cependant, nous allons voir qu'il existe un algorithme relativement simple qui permet de le résoudre de manière optimisée.

Commençons par rappeler les règles:
Le jeu des tours de Hanoï est constitué de trois piquets, placés verticalement, et d'un nombre aléatoire de disques de taille décroissante. Chacun des disques est percé en son centre pour être mis autour de l’un ou l’autre des trois piquets. Les disques sont initialement placés par taille décroissante autour du piquet le plus à gauche, formant ainsi une tour. Le but du jeu consiste à déplacer les disques sur le piquet de droite par ordre de taille décroissante. Les disques peuvent aller et venir librement sur les piquets, en suivant ces 2 règles:

• on ne déplace qu’un seul disque à la fois
• un disque ne peut jamais être posé sur un disque plus petit

Aujourd'hui, nous vous proposons de résoudre ce jeu à l'aide de seulement 4 lignes de codes !
Nous allons résoudre cet algorithme de manière récursive en Python :

def Hanoi(n, i, j, k):
    if n == 1:
        return [(i, k)]
    return Hanoi(n - 1, i, k, j) + [(i, k)] + Hanoi(n - 1, j, i, k)

Voici le résultat de notre code en action. Essayez d'augmenter le nombre de disques, vous verrez que notre bot ne rencontre pas plus de difficultés pour résoudre le problème.

Le principe est le suivant :
On suppose que l'on sait résoudre l'algorithme pour n disques. Ainsi, pour le résoudre avec n+1 disques, il suffit de déplacer la tour de n disques sur le poteau du milieu, puis de déplacer le n+1 ème disque du poteau de gauche au poteau de droite, puis de déplacer la tour de n disques qui est sur le poteau du milieu au poteau de droite. Or on sait résoudre cet algorithme pour un seul disque (il suffit de déplacer le disque du poteau de gauche à celui de droite). Avec cet algorithme, on peut donc résoudre le problème pour deux disques en appliquant la logique. Une fois que l'on sait faire pour deux disques, on peut le résoudre pour trois disques etc...

Maintenant, pour estimer le labeur économisé par ces 4 lignes de code, essayons de déterminer le nombre de coups minimum pour pouvoir résoudre le jeu pour n-disques. On note U_n le nombre de coups qu'il faut pour pouvoir résoudre le jeu avec n-disques. D'après le principe de récursivité, on a U_n+1=U_n+1+U_n, ce qui correspond à faire la tour de n disques (U_n coups), puis déplacer le plus gros disque (1 coup), puis déplacer la tour à droite (U_n coups). On a donc U_n+1=2xU_n+1, et donc U_n=2ⁿ-1
Voici une estimation du temps qu'il faut pour résoudre le jeu manuellement en comptant une seconde par coup :

On fait la course ? Nous on part à dos de Python, rendez-vous dans 30 ans 😅 !