Tours de Hanoï

But du jeu

Transportez toute la tour de disques sur la tige d’arrivée (à droite), en respectant deux règles.

Règles

• On ne déplace qu’un seul disque à la fois : celui du sommet d’une tige.
• Un disque ne peut jamais reposer sur un disque plus petit.

Commandes

• Touchez une tige pour soulever son disque du sommet, puis touchez la tige de destination.
• Vous pouvez aussi faire glisser le disque d’une tige à l’autre.
• Au clavier : touches 1 à 4 (source puis destination), ou flèches gauche et droite puis Espace.

Coups minimaux

Avec 3 tiges, il faut au minimum 2ⁿ − 1 coups pour n disques (7 pour 3 disques, 1 023 pour 10). Avec 4 tiges, l’algorithme de Frame-Stewart réduit spectaculairement ce nombre : 49 coups suffisent pour 10 disques.

L’option « Disques dispersés » part d’une position aléatoire où les disques sont répartis sur les tiges : le minimum propre à cette position est calculé et affiché.

À propos de l’IA

L’IA explore par une recherche en largeur toutes les positions possibles (jusqu’à 4¹⁰, soit plus d’un million pour 10 disques et 4 tiges) : elle connaît donc, depuis n’importe quelle position, le nombre exact de coups restants et le meilleur coup. Depuis la tour classique, elle applique l’algorithme récursif de Frame-Stewart, dont elle vérifie l’optimalité par cette même recherche.

Les records ne sont homologués qu’en partie classique, sans indice ni aide de l’IA.