Les tours de Hanoï

Contrairement aux apparences et aux rumeurs, ce problème de logique n'est pas du tout millénaire. Il a été inventé de toutes pièces en 1883 par l'ingénieux mathématicien français Édouard Lucas, qui l'a habilement commercialisé sous le pseudonyme exotique de N. Claus de Siam, en l'accompagnant d'une fausse légende indienne prophétique prédisant la terrible fin du monde lorsque de pieux moines bouddhistes auraient achevé de déplacer soixante-quatre immenses disques d'or pur.

La méthode infaillible de résolution repose entièrement sur le concept fondamental de récursivité. Pour réussir à déplacer le plus grand disque de la pile, le joueur doit obligatoirement d'abord transférer l'ensemble des disques situés au-dessus de lui vers le piquet auxiliaire disponible. Pour un nombre n de disques, le nombre minimum de déplacements individuels requis est strictement égal à deux puissance n, moins un.

Ce puzzle de manipulation est aujourd'hui devenu légendaire dans l'apprentissage de la science informatique contemporaine, car il constitue certainement l'un des exemples les plus élégants, clairs et visuels pour introduire les étudiants à la programmation récursive et à la rigoureuse réflexion algorithmique.