Diferencia entre revisiones de «Torres de Hanói»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 21:35 6 may 2010

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.

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 2⁶⁴-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

ADVERTENCIA: Si no quieres conocer detalles para resolver el acertijo, no sigas leyendo.

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 A B C siendo la inicial A
y la de destino C}
*/
void hanoi(int discos) {
    hanoi(discos, 'A', 'C', 'B');
}

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).

%

Modula-2

%Hanoi usando recursividad en lenguaje Modula-2

FROM SWholeIO IMPORT WriteCard;
FROM STextIO IMPORT WriteChar,WriteString,WriteLn;

PROCEDURE hanoi(x:CARDINAL;ini,aux,dest:CHAR);

BEGIN
	IF x = 1 THEN
		WriteString("MOVER DISCO ");
		WriteCard(x,1);
		WriteString(" DEL cilindro ");
		WriteChar(ini);
		WriteString(" AL cilindro ");
		WriteChar(dest);
		WriteLn;
		
	ELSE
		hanoi(x-1,ini,dest,aux);
		WriteString("MOVER DISCO ");
		WriteCard(x,1);
		WriteString(" DEL cilindro ");
		WriteChar(ini);
		WriteString(" AL cilindro ");
		WriteChar(dest);
		WriteLn;
		hanoi(x-1,aux,ini,dest);
		
	END;
END hanoi;

%

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, 32... etc
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

Enlaces externos

Wikimedia Commons alberga una categoría multimedia sobre Torre de Hanói.
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)

[1] Walter William Rouse Ball, Harold Scott Macdonald Coxeter, (1987), «Mathematical recreations and essays»,Dover Publications, ISBN 0-486-25357-0

[1]

@@ Línea 4: / Línea 4: @@
 == 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: HEY MUCHACHOS ESTE ES EL DEL PARCIAL PILAS
+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.