2. Disques mélangés

2.1. Règles du jeu

Voyons à présent comment passer d'une configuration quelconque de départ à une configuration quelconque d'arrivée. Trouvons un algorithme qui permette, en respectant les mêmes règle de passer, par exemple, de
6 7 5 3 2 1 8 4 à 8 5 3 7 4 2 6 1 .

2.2. Résolution

Le principe de résolution est le suivant : il faut déplacer le plus grand disque vers sa position finale. Pour cela, il faut retirer tous les autres disques du pieux où se trouve le plus grand disque et de celui vers lequel il doit être déplacé. Voici ce que cela donne pour notre exemple initial :
6 7 5 3 2 1 8 4 7 6 5 4 3 2 1 8 8 7 6 5 4 3 2 1 8 5 3 7 4 2 6 1 .
Une fois encore, pour pouvoir modifier une configuration de n disques, il faut savoir le faire pour n - 1.
Nous avons besoin de définir une nomenclature qui nous permettra d'identifier une configuration donnée. Une configuration de n disques sera décrite par un mot de n lettres de l'alphabet suivant : {1, 2, 3}.
Chaque lettre indique le pieu sur lequel se trouve un disque. Ainsi, le mot suivant 132122 correspond à la configuration suivante :
6 3 4 2 1 5
En rangeant les disques par taille décroissante, le mot 132122 nous dit qu'il faut placer le premier disque sur le pieu 1, le second sur le pieu 3, le troisième sur le 2, etc.
Pages : 1 2 3 4 5 6 7
Les tours de Hanoï
15 mai 2013
Sommaire général