Tours de Hanoï - Simulateur du jeu des tours de Hanoi

Nombre de plateaux

Vitesse

Contexte

Les tours de Hanoï sont un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de « départ » à une tour d'« arrivée » en passant par une tour « intermédiaire », et ceci en un minimum de coups, tout en respectant les règles suivantes :

on ne peut déplacer plus d'un disque à la fois
on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

On suppose que cette dernière règle est également respectée dans la configuration de départ.

Algorithme

L'algorithme employé afin de résoudre ce jeu est récursif et possède une complexité O(2ⁿ).

function hanoi(n, from, to, pivot) {
    if (n == 1) {
        piles[to].push(piles[from].pop());
    } else {
        hanoi(n - 1, from, pivot, to);
        piles[to].push(piles[from].pop());
        hanoi(n - 1, pivot, to, from);
    }
}