- Torres de Hanói
-
Torres de Hanói.
Etapas de la resolución del problema con 4 discos.Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.[1] Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
Contenido
Descripción
El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
- Sólo se puede mover un disco cada vez.
- Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
- Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.
Se cuenta que un templo de Benarés (Uttar Pradesh, India), se encontraba una cúpula que señalaba el centro del mundo. Allí estaba una bandeja sobre la cual existían tres agujas de diamante. En una mañana lluviosa, un rey mandó a poner 64 discos de oro, siendo ordenados por tamaño: el mayor en la base de la bandeja y el menor arriba de todos los discos.Tras la colocación, los sacerdotes del templo intentaron mover los discos entre las agujas, según las leyes que se les habían entregado: "El sacerdote de turno no debe mover más de un disco a la vez, y no puede situar un disco de mayor diámetro encima de otro de menor diámetro". Hoy no existe tal templo, pero el juego aún perduró en el tiempo...
Otra leyenda cuenta que Dios al crear el mundo, colocó tres varillas de diamante con 64 discos en la primera. También creó un monasterio con monjes, los cuales tienen la tarea de resolver esta Torre de Hanói divina. El día que estos monjes consigan terminar el juego, el mundo acabará. No obstante, esta leyenda resultó ser un invento publicitario del creador del juego, el matemático Éduard Lucas. En aquella época, era muy común encontrar matemáticos ganándose la vida de forma itinerante con juegos de su invención, de la misma forma que los juglares hacían con su música. No obstante, la falacia resultó ser tan efectista y tan bonita, que ha perdurado hasta nuestros días. Además, invita a realizarse la pregunta: "si la leyenda fuera cierta, ¿cuándo será el fin del mundo?".
El mínimo número de movimientos que se necesita para resolver este problema es de 264-1. Si los monjes hicieran un movimiento por segundo, los 64 discos estarían en la tercera varilla en algo menos de 585 mil millones de años. Como comparación para ver la magnitud de esta cifra, la Tierra tiene como 5 mil millones de años, y el Universo entre 15 y 20 mil millones de años de antigüedad, sólo una pequeña fracción de esa cifra.
Resolución
El problema de las Torres de Hanói es curiosísimo porque su solución es muy rápida de calcular, pero el número de pasos para resolverlo crece exponencialmente conforme aumenta el número de discos. Existen algunas versiones del problema con un número diferente de varillas. Aunque se conocen algoritmos eficientes que resuelven el problema con 3 varillas de manera óptima, no se han encontrado aún sus contrapartidas para cualquier número (N igual o superior a 3) de ellas.
Solución simple
Una forma de resolver la colocación de la torre es fundamentándose en el disco más pequeño, en este caso el de hasta arriba. El movimiento inicial de este es hacia la varilla auxiliar. El disco número dos por regla, se debe mover a la varilla número tres. Luego el disco uno se mueve a la varilla tres para que quede sobre el disco dos. A continuación se mueve el disco que sigue de la varilla uno, en este caso el disco número tres, y se coloca en la varilla dos. Finalmente el disco número uno regresa de la varilla tres a la uno (sin pasar por la dos) y así sucesivamente. Es decir, el truco está en el disco más pequeño.
Mediante recursividad
Este problema se suele plantear a menudo en ámbitos de programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a la intermedia (auxiliar) y a la función le llamaríamos hanoi (origen, auxiliar, destino), como parámetros, la función recibiría las pilas de discos. El algoritmo de la función sería el siguiente:
- Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.
- Si no: hanoi({0...n-1},destino, auxiliar) //mover todas las fichas menos la más grande (n) a la varilla auxiliar
- mover disco n a destino //mover la ficha grande hasta la varilla final
- hanoi (auxiliar, origen, destino) //mover todas las fichas restantes, {0...n-1}, encima de la ficha grande (n)
- terminar
C++
/* {Pre: discos > 1 ^ discos = número de discos ^ ini,dest,aux = caracteres que identifiquen las torres} {Post: Se escribe por el canal estándar de salida los movimientos a realizar, indicados a partir de los caracteres que identifican las torres, para llevar todos los discos desde la torre inicial a la de destino} */ void hanoi(int discos, char ini, char dest, char aux) { if (discos == 1) cout << ini << " --> " << dest << endl; else { hanoi(discos - 1, ini, aux, dest); cout << ini << " --> " << dest << endl; hanoi(discos - 1, aux, dest, ini); } } /* Ejemplo de función que llama automáticamente a hanoi(int, char, char, char) solo dándole el número de discos {Pre: discos > 1} {Post: Se escribe por el canal estándar de salida los movimientos a realizar para llevar todos los discos desde la torre de inicio hasta la de destino. Las torres serán identificadascomo M A V siendo la inicial M y la de destino V} */ void hanoi(int discos) { hanoi(discos, 'M', 'A', 'V'); }
C#
using System; using System.IO; namespace TorresHanoi { public class Hanoi { public static void Main(string[] args) { int n; Console.Write("Escriba el número de discos en la torre de hanoi: "); n = Leer.datoInt(); { Console.Write("Error, reescriba el número de discos en la torre: "); n = Leer.datoInt(); } } public static void algoritmoHanoi(int n, String from, String temp, String to) { if (n == 0) return; algoritmoHanoi(n-1, from, to, temp); System.Console.WriteLine("Mover disco " + n + " de " + from + " a " + to); algoritmoHanoi(n-1, temp, from, to); } } public class Leer { public static int datoInt() { string dato; dato = System.Console.ReadLine(); return int.Parse(dato); } } }
Java
import java.util.*; public class Hanoi { public static void main(String args[]){ int n; Scanner sc=new Scanner(System.in); System.out.print("Escriba el número de discos en la torre de hanoi: "); n=sc.nextInt(); while(n<0){ System.out.print("Error, reescriba el número de discos en la torre: "); n=sc.nextInt(); } algoritmoHanoi(n,"Primera Torre","Segunda Torre","Tercera Torre"); } public static void algoritmoHanoi(int n, String from, String temp, String to) { if (n == 0) return; algoritmoHanoi(n-1, from, to, temp); System.out.println("Mover disco " + n + " de " + from + " a " + to); algoritmoHanoi(n-1, temp, from, to); } }
Prolog
%Hanoi usando recursividad en lenguaje Prolog hanoi(N):- move(N,'A','C','B'). move(0,_,_,_):-!. move(N, Src, Dest, Spare):- M is N-1, move(M, Src, Spare, Dest), primitive(Src, Dest), move(M, Spare, Dest, Src). primitive(X, Y):- writelist([mueve, un, disco, desde, X, hasta, Y]), nl. writelist([]). writelist([H|T]):- write(H), write(' '), writelist(T). %
Ensamblador
;Realizado por Javier Muñoz y Wilson Moreno ;Hanoi usando recursividad en lenguaje Ensamblador ;Se supone una correcta implementacion del proc Imprimir tal que imprima: ;[BP].Inicio "->" [BP].Destino ;Juéguesela como pueda para imprimirlo, lo importante es el proc Hanoi ;El llamado sería ;Mov Ax, 3;en ax esta la cantidad de discos ;Mov Bx, 'I';El inicio se representa con I ;Mov Cx, 'D';El destino se representa con D ;Mov Dx, 'A';El aux se representa con A ;Los valores se ingresan en orden inverso a como estan en el struc ;el primero que se mete en la pila es el ultimo que esta declarado en el struc ;Push Ax ;Meto la cantidad de discos ;Push bx;Meto el inicio "letra I" ;push cx;Meto el destino "letra D" ;push dx ;Meto el aux "letra A" ;Call Hanoi ;Struc que utiliza la estructura de la pila Param Struc BPViejo Dw ? DirRet DW ? Aux Dw ? Destino Dw ? Inicio Dw ? Discos Dw ? Param Ends ;AQUI ESTÁ EL CÓDIGO Hanoi Proc Near Push BP; Mov BP,SP ;Recupero en los registros los valores en el orden ;que le había asignado antes de meterlos en la pila Mov Ax, [BP].Discos Mov BX,[BP].Inicio Mov Cx,[BP].Destino Mov Dx,[BP].aux Cmp Ax,1;Si la cantidad de discos = 1 JE parada;Voy a la condicion de parada Dec Ax ;Primero decremento la cantidad de discos en 1 ;Ahora voy a llamarlo con los parametros en diferente orden Push Ax;Primero la cantidad de discos (discos-1) Push bx;Despues la variable correspondiente a inicio Push dx;Despues la variable correspondiente a aux Push cx;;Despues la variable correspondiente a destino Call Hanoi;Llamo al algoritmo con el nuevo orden Call imprimir ; cout << ini << " --> " << dest << endl; ;Saco todos los valores de la pila Pop cx Pop dx pop bx pop ax ;Ahora voy a llamarlo con los parametros en diferente orden Push Ax; YA ESTABA DECREMENTADO DESDE EL LLAMADO ANTERIOR Push Dx;Despues la variable correspondiente a aux Push Cx;Despues la variable correspondiente a destino Push BX;Despues la variable correspondiente a inicio Call Hanoi;Llamo a Hanoi con el nuevo orden ;saco todos los valores de la pila Pop bx Pop cx pop dx pop ax ;Termina el algoritmo después del segundo llamado Jmp Salir Parada: call imprimir Salir: ;Cuando llega a este punto, la pila tiene el siguiente orden (inverso al struc) ; |Discos AX | ; |Inicio BX | ; |Destino CX | ; |Aux DX | ; |DirRet | ; |BPViejo | <- Tope ;Al sacar el BP viejo, tengo la direccion de retorno de donde "venia" Pop BP ;Saco BPViejo del tope de la pila Ret;Regreso de donde venia Hanoi EndP
Batch
@echo off setlocal enabledelayedexpansion ::::::::::::::::::::::::::::::::::::::::: ::Script Para Resolver Torres de Hanoi.:: ::Creado por Hugo Guerrero (Guerrerohgp): ::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::::::::::: ::Script to solve Hanoi Towers:: :: Created By Guerrerohgp :: :: 2011 :: :::::::::::::::::::::::::::::::: :ini set/p "cantidad=Ingrese el numero de discos en la torre: " if not defined cantidad goto:ini if !cantidad! lss 0 goto:ini call:algoritmoHanoi !cantidad! Torre_1 Torre_2 Torre_3 pause>nul exit :algoritmoHanoi setlocal if "%1" equ "0" goto:eof set/a "cnt=%1-1" call:algoritmoHanoi !cnt! % class="re2">2 %4 %3 echo.Mover disco %1 de %2 a %4 call:algoritmoHanoi !cnt! % class="re2">3 %2 %4 endlocal goto:eof
Iterativa
Otra manera de resolver el problema, sin utilizar la recursividad, se basa en el hecho de que para obtener la solución más corta, es necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares sólo existe un movimiento posible que no lo incluye. El problema se reduce a decidir en cada paso impar a cuál de las dos pilas posibles se desplazará el disco pequeño:
El algoritmo en cuestión depende del número de discos del problema.- Si inicialmente se tiene un número impar de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila destino, y en cada paso impar se le mueve a la siguiente pila a su izquierda (o a la pila destino, si está en la pila origen).
- La secuencia será DESTINO, AUXILIAR, ORIGEN, DESTINO, AUXILIAR, ORIGEN, etc.
- Si se tiene inicialmente un número par de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila auxiliar, y en cada paso impar se le mueve a la siguiente pila a su derecha (o a la pila origen, si está en la pila destino).
- La secuencia será AUXILIAR, DESTINO, ORIGEN, AUXILIAR, DESTINO, ORIGEN,
Una forma equivalente de resolverlo es la siguiente: coloreando los discos pares de un color y los impares de otro; se resuelve el problema añadiendo la siguiente regla: no colocar dos discos del mismo color juntos. De esta manera sólo queda un movimiento posible (además del de volver hacia atrás).Curiosidades
A la hora de resolver matemáticamente el problema, nos encontramos con muchas curiosidades matemáticas respecto a la resolución. Son las siguientes:
- La ficha número n (siendo 1 la más pequeña) se mueve por primera vez en el paso número 2^(n-1), y después de ese primer movimiento, se moverá cada 2^n movimientos. De este modo, la ficha 1, se mueve en 1, 3, 5, 7, 9... etc. La ficha 3, se mueve en 4, 12, 20, 28, 36... etc.
- Y el número de veces que se mueve cada ficha es de 2^(n-k),siendo n el número de fichas y k igual a 1 para la ficha más pequeña.
- El número de movimientos mínimo a realizar para resolver el problema es de (2^n)-1, siendo n el número de fichas.
- Todas las fichas impares (siendo 1 la más pequeña) se mueven siguiendo el mismo patrón. Asimismo, todas las fichas pares se mueven siguiendo el patrón inverso a las impares. Por ejemplo: si queremos mover un número impar de piezas desde la columna 1 hasta la 3, sucederá lo siguiente:
-
- Todas las fichas impares seguirán este patrón de movimiento: 1 -> 3 -> 2 -> 1 -> 3 -> 2 -> 1 -> 3 -> 2 -> 1.
- Todas las fichas pares seguirán este patrón de movimiento: 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3
- Estos patrones dependen únicamente del número de piezas. Si el número de piezas es par, los patrones de las impares serán los de las pares, y viceversa.
- Uniendo la primera regla con la segunda, sabemos siempre qué pieza hay que mover y a qué columna hay que desplazarla, luego el problema está resuelto.
Referencias
- ↑ Walter William Rouse Ball, Harold Scott Macdonald Coxeter, (1987), «Mathematical recreations and essays»,Dover Publications, ISBN 0-486-25357-0
Véase también
- Recursividad
- Exponencial
Enlaces externos
Wikimedia Commons alberga contenido multimedia sobre Torre de Hanói. Commons- Interactivo 1
- Interactivo 2
- Artículo de Antonio Javier Serrano Mora sobre La Torre de Hanói
- Artículo de Rodolfo Valeiras sobre La Torre de Hanoi
- Matemáticas tras las Torres de Hanói
- Dos soluciones no recurrentes en C++ - (en inglés)
Wikimedia foundation. 2010.
