Jouez au classique puzzle des Tours de Hanoï en ligne. Déplacez des disques entre les piquets en suivant les règles. Choisissez votre difficulté et résolvez-le en un minimum de coups. Gratuit, sans inscription.
Les Tours de Hanoï est un puzzle mathématique inventé par le mathématicien français Édouard Lucas en 1883. Il se compose de trois piquets et de plusieurs disques de tailles différentes qui peuvent glisser sur n'importe quel piquet. Le puzzle commence avec les disques empilés par ordre croissant de taille sur un piquet, et l'objectif est de déplacer toute la pile vers un autre piquet, en respectant des règles spécifiques. Le nombre minimum de coups nécessaires pour résoudre le puzzle est de 2^n − 1, où n est le nombre de disques.
Le nombre minimum de coups pour résoudre les Tours de Hanoï avec n disques est de 2^n − 1. Par exemple : 3 disques = 7 coups, 4 disques = 15 coups, 5 disques = 31 coups, 6 disques = 63 coups, 7 disques = 127 coups, et 8 disques = 255 coups.
Oui. La preuve utilise l'induction mathématique. Pour déplacer n disques du piquet A au C, vous devez d'abord déplacer n−1 disques vers le piquet B (prenant T(n−1) coups), puis déplacer le plus grand disque vers le piquet C (1 coup), puis déplacer les n−1 disques du piquet B vers le C (encore T(n−1) coups). Cela donne la récurrence T(n) = 2T(n−1) + 1, qui se résout en T(n) = 2^n − 1.
Non. Le nombre minimum de coups (2^n − 1) est prouvé être à la fois nécessaire et suffisant. Toute solution nécessite au moins ce nombre de coups, et il existe une stratégie qui atteint exactement ce nombre.
Pour le puzzle physique avec 8 disques, les résolveurs experts peuvent le compléter en moins de 2 minutes. En programmation compétitive, les ordinateurs peuvent le résoudre instantanément pour n'importe quel nombre pratique de disques en utilisant l'algorithme récursif.