RÉSOLUTION

La solution générale est donnée par l'algorithme suivant.

Algorithme récursif

La solution de base du jeu de la Tour de Hanoï est formulée de manière récursive.
Étiquetez les piquets avec A - B - C et numérotez les disques de 1 (le plus petit) à n (le plus grand). L'algorithme est exprimé comme suit:

1. Déplacez les n-1 premiers disques de A à B. (Cela laisse le disque n seul sur le piquet A)
2. Déplacez le disque n de A à C
3. Déplacez les n-1 disques de B à C

Pour déplacer n disques, il faut effectuer une opération élémentaire (déplacement d'un seul disque) et une opération complexe, c'est-à-dire le mouvement de n-1 disques. Cependant, cette opération se résout également de la même manière, en demandant comme opération complexe le déplacement de n-2 disques. En itérant ce raisonnement on réduit le processus complexe à un processus élémentaire, c’est-à-dire le déplacement de n-(n-1)=1 disque.
C'est un algorithme récursif de complexité exponentielle.

Il est intéressant de noter que le casse-tête peut être résolu pour n'importe quel "n", avec une démonstration par récurrence: supposons que nous ayons une tour en A composée de N disques, et supposons que N soit le nombre de disques maximum autorisés à résoudre le jeu. Au terme du déplacement de la tour de A à B, nous ajoutons à A un disque supplémentaire, de taille égale à N+1, et supposons que ce disque ait été arrêt tout le temps sous les autres. À ce stade, nous déplaçons simplement le disque de A à C, et nous pourrons certainement déplacer la tour de B à C en suivant les mêmes étapes que celles qui étaient nécessaires pour le faire de A à B. Après avoir montré qu’une tour de N disques peut être déplacée d’une colonne à une autre, il est également montré qu’on peut déplacer une tour de N+1 disques.

Aspects psychologiques

Ce casse-tête est utilisé en particulier dans la recherche psychologique, à travers la résolution des problèmes. Il est également utilisé comme test neuropsychologique.

Ce test peut détecter les mauvais fonctionnements des zones frontale et préfrontale et permet d’évaluer les fonctions exécutives telles que la planification, le travail, la mémoire et l’inhibition.
La résolution du jeu de la Tour de Hanoï dépend de l'activité inhibitrice, de la "mémoire de travail", c'est-à-dire l'utilisation de la mémoire à court terme, de la mémoire procédurale et de l'intelligence fluide. Ce test est similaire à celui de la Tour de Londres, ainsi qu'à celui des Tours de Toronto, utilisé avant tout pour évaluer les compétences de décision stratégique et résolution de problèmes chez les enfants de 4 à 13 ans et pour étudier les effets du vieillissement sur la résolution des problèmes simples.