Tours de Hanoï
Trois tiges et un cône de disques, le plus grand en bas. Déplacez toute la tour sur la tige de droite. Vous ne pouvez déplacer qu’un disque à la fois, et un disque plus grand ne doit jamais reposer sur un plus petit. La solution la plus courte demande 2ⁿ − 1 coups : 1, 3, 7, 15, 31, etc. Déplacez un disque à la fois sur un disque plus grand ou sur une tige vide. Toute la tour doit finir sur la tige de droite. La solution la plus courte demande 2ⁿ − 1 coups. Faites glisser un disque, ou cliquez sur une tige puis sur une autre.
Comment ça marche
- Ouvrez cette page. Quatre disques sont empilés sur la tige de départ. Quinze coups, c’est le minimum.
- Faites glisser le disque du dessus vers une autre tige, ou cliquez sur une tige puis sur celle que vous voulez. Un disque plus grand sur un plus petit est refusé.
- Appuyez sur Résoudre pour voir une solution la plus courte, ou avancez avec Étape. Enregistrez ensuite un PNG.
Un disque, et jamais un grand sur un petit
Un coup prend le disque du dessus d’une tige et le pose sur une autre tige, ou sur une tige vide. C’est le seul type de coup. Le disque que vous posez doit être plus petit que celui sur lequel il atterrit. Avec ces règles, les disques de chaque tige restent triés, le plus grand en bas.
2ⁿ − 1 coups, pas moins
Pour déplacer n disques, vous écartez d’abord les n − 1 disques posés sur le plus grand, vous déplacez le plus grand une fois, puis vous remettez les n − 1 disques par-dessus. Si n − 1 disques demandent T coups, n disques en demandent 2T + 1. Cela donne 2ⁿ − 1 : 1, 3, 7, 15, 31. Huit disques, la plus grande tour ici, demandent 255 coups.
Le même casse-tête, avec un disque de moins
Déplacez les n − 1 disques du haut sur la tige auxiliaire. Déplacez le plus grand disque à l’arrivée. Déplacez les n − 1 disques de la tige auxiliaire sur l’arrivée. Chacune de ces tâches plus petites est à nouveau le même casse-tête. Étape et Résoudre jouent un chemin le plus court. Depuis une tour parfaite, c’est cette récursion. Depuis un plateau mélangé, c’est quand même un chemin le plus court, trouvé en explorant les positions autorisées.
Questions fréquemment posées
Quelles sont les règles des tours de Hanoï ?
Déplacez un disque à la fois. Prenez le disque du dessus d’une tige et posez-le sur une autre tige. Ne posez jamais un disque plus grand sur un plus petit.
Combien de coups demande la solution la plus courte ?
2ⁿ − 1. Un disque, c’est 1 coup, deux disques 3, trois 7, quatre 15 et cinq 31.
Qui a inventé les tours de Hanoï ?
Édouard Lucas a présenté ce casse-tête en 1883. L’histoire des prêtres qui déplacent 64 disques d’or est la légende qu’il racontait avec.
Puis-je regarder la solution ?
Oui. Étape joue un coup d’une solution la plus courte. Résoudre joue le reste. « Regarder 3 disques » déroule la stratégie récursive classique depuis le début.
Outils associés
Tours de Hanoï
Les tours de Hanoï : trois tiges, un disque à la fois, et jamais un grand sur un petit. La solution la plus courte compte 2ⁿ−1 coups. Édouard Lucas a présenté ce casse-tête en 1883.
Parcours du cavalier
Faites sauter un cavalier sur chaque case de l’échiquier exactement une fois. Jouez vous-même avec les indices de Warnsdorff, ou regardez Résoudre terminer un parcours ouvert ou fermé. Enregistrez le tracé en PNG.
Huit dames
Placez huit dames sur un échiquier sans qu’aucune n’en attaque une autre. Essayez vous-même, regardez la recherche par retour sur trace trouver une solution pas à pas, et parcourez les 92 solutions.
Taquin
Jouez au taquin classique dans votre navigateur, avec des pièces en bois en 3×3, 4×4 ou 5×5. Mélangez, faites glisser des lignes entières d’un coup, essayez l’impossible 14-15 de Sam Loyd, ou regardez Résoudre le terminer.
Aiguille de Buffon
Lâchez des aiguilles sur un plancher rayé, dans votre navigateur. Comptez les croisements et regardez l’expérience de Buffon de 1777 estimer π.
Cercles de multiplication
Reliez chaque nombre d’un cercle à son multiple. Dessinez une table de multiplication, une cardioïde ou une figure en fil sur papier, à la craie ou sur bois.
La conjecture de Collatz
Explorez le problème de Collatz 3n+1 dans votre navigateur. Parcourez les suites de grêlons, faites pousser un arbre de Collatz géométrique et zoomez dans la fractale de Collatz continue.
Fourmi de Langton
Lancez la fourmi de Langton dans votre navigateur. Observez la symétrie, le chaos et l’autoroute de 104 pas, puis essayez des règles multicolores, plusieurs fourmis, une grille hexagonale et des turmites.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur