Las torres de Hanói
Las torres de Hanói 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.
Definir la función
hanoi :: Int -> [String]
tal que (hanoi n) es la lista de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,
λ> hanoi 1 ["Mueve el disco 1 de A a C"] λ> hanoi 2 ["Mueve el disco 1 de A a B","Mueve el disco 2 de A a C","Mueve el disco 1 de B a C"] λ> mapM_ putStrLn (hanoi 2) Mueve el disco 1 de A a B Mueve el disco 2 de A a C Mueve el disco 1 de B a C λ> mapM_ putStrLn (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
hanoi :: Int -> [String] hanoi n = aux n "A" "B" "C" where aux n a b c | n == 1 = ["Mueve el disco 1 de " ++ a ++ " a " ++ c] | otherwise = aux (n-1) a c b ++ ["Mueve el disco "++ show n ++ " de " ++ a ++ " a " ++ c] ++ aux (n-1) b a c