Le problème des tours de Hanoï est 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.

Merci Wikipédia

Nous avons eu à écrire un programme en OCaml pour résoudre ce problème de manière simple et quasi instantanée. Voici ma version :

let hanoi n =
  let c = ref 0 in
    let movedisk f t =
      incr c;
      print_endline("coup"^string_of_int !c^": "^f^" --> "^t) in
    let rec dohanoi n f u t =
      if n = 1 then movedisk f t
      else begin
	dohanoi (n - 1) f t u;
	movedisk f t;
	dohanoi (n - 1) u f t;
      end in
    if n > 0 then dohanoi n "gauche" "milieu" "droite";;

Ce qui donne pour n=4 par exemple :

coup1: gauche --> milieu
coup2: gauche --> droite
coup3: milieu --> droite
 . . .
coup13: gauche --> milieu
coup14: gauche --> droite
coup15: milieu --> droite
- : unit = ()

Face à ceci je ne crois pas qu’Édouard Lucas reste longtemps le plus fort