Ir al contenido principal

Las torres de Hanói

Las torres de Hanoi es un rompecabeza que consta de tres postes que llamaremos A, B y C. Hay N discos de distintos tamaños en el poste A, de forma que no hay un disco situado sobre otro de menor tamaño. Los postes B y C están vacíos. Sólo puede moverse un disco a la vez y todos los discos deben de estar ensartados en algún poste. Ningún disco puede situarse sobre otro de menor tamaño. El problema consiste en colocar los N discos en el poste C.

Los postes se pueden representar mediante el siguiente tipo de datos

data Poste = A | B | C
  deriving Show

Definir las funciones

movimientos :: Integer -> [(Integer,Poste,Poste)]
hanoi       :: Integer -> IO ()

tales que

  • (movimientos n) es la lista de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,
λ> movimientos 1
[(1,A,C)]
λ> movimientos 2
[(1,A,B),(2,A,C),(1,B,C)]
λ> movimientos 3
[(1,A,C),(2,A,B),(1,C,B),(3,A,C),(1,B,A),(2,B,C),(1,A,C)]
  • (hanoi n) escribe los mensajes de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,
λ> hanoi 3
Mueve el disco 1 de A a C
Mueve el disco 2 de A a B
Mueve el disco 1 de C a B
Mueve el disco 3 de A a C
Mueve el disco 1 de B a A
Mueve el disco 2 de B a C
Mueve el disco 1 de A a C

Soluciones

data Poste = A | B | C
  deriving (Eq, Show)

movimientos :: Integer -> [(Integer,Poste,Poste)]
movimientos n = aux n A B C
  where
    aux n a b c
      | n == 1    = [(1,a,c)]
      | otherwise = aux (n-1) a c b ++ (n,a,c) : aux (n-1) b a c

hanoi :: Integer -> IO ()
hanoi n =
  putStrLn (unlines (map mensaje (movimientos n)))

-- (mensaje (n.x.y)) es la cadena indicando que el disco n se ha movido
-- desde el poste x al poste y. Por ejemplo,
--    λ> mensaje (1,A,B)
--    "Mueve el disco 1 de A a B"
mensaje :: (Integer,Poste,Poste) -> String
mensaje (n,x,y) =
  "Mueve el disco " ++ show n ++ " de " ++ show x ++ " a " ++ show y