Torres de Hanói

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Torres de Hanói.

Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Édouard Lucas.[1] Este juego de mesa 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 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[editar]

Etapas de la resolución del problema con 4 discos.

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:

  1. Sólo se puede mover un disco cada vez.
  2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
  3. 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.

Historia[editar]

Visitantes en el museo Universum experimentando con display

Se cuenta que en 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 que existían tres agujas de diamante. En una mañana lluviosa, un rey mandó a poner 64 discos de oro ordenados por tamaño: el mayor, en la base de la bandeja, y el menor, arriba de todos los discos. Tras su 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 ningún disco encima de otro de menor diámetro». Hoy no existe tal templo, pero el juego aún perdura 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, quienes tenían la tarea de resolver esta Torre de Hanói divina. El día que estos monjes consiguieran terminar el juego, el mundo acabaría. 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 lo 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ía el fin del mundo?».) La mínima cantidad de movimientos para resolver este problema es de 264 – 1; si los monjes hicieran un movimiento por segundo, sin equivocarse, 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 unos 5 mil millones de años, y el Universo, unos 14 mil millones de años de antigüedad, solo una pequeña fracción de esa cifra.)

Resolución[editar]

La solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el número de pasos para resolver el problema crece exponencialmente conforme aumenta el número de discos.

Solución simple[editar]

El secreto está en que según la cantidad de discos que contiene la torre inicial, sea esta par o impar, las secuencias de movimientos del disco pequeño son diferentes. Si la cantidad es par, el disco pequeño se moverá hacia la auxiliar, luego (cuando le toque) a la destino y luego a la origen, así, repetidamente hasta finalizar. Y si la cantidad es impar, el disco pequeños se moverá hacia la destino, luego a l auxiliar y luego a la origen, repitiéndose esta serie hasta finalizar el juego. Ahora bien, sabemos que los movimientos 1, 3, 5 etc hasta el final (siempre el número final de movimientos es 2 elevado a la cantidad de discos de la torre de inicio, y a esto se le resta uno, con lo cual el número de movimientos será impar, y el último movimiento será del disco más pequeño) ya tienen una varilla destino de fácil cálculo. Ahora bien, qué pasa en los otros movimientos. Pasa algo muy simple: en una varilla el tope será el disco más pequeño, y entonces quedan otras dos que varillas una de las cuales, al menos podrá estar vacía, con lo cual muevo el disco que no sea 1 (ya no es su turno) a la vacía). Si las otras dos en las que no están el 1, no están vacías, por la regla del juego, solo podremos optar por mover la menor hacia la mayor. Parece difícil la explicacióm pero sabiendo (a partir de la paridad del nro total de discos) la secuencia de movimientos fluye. Ejemplo de secuencia en un juego de 4 discos de A a C con B Auxiliar 1 a B (porque 4 es par) 2 a C (no hay opción) 1 a C (porque le toca a 1 y se sigue la secuencia BCA al ser 4 par) 3 a B (no hay opción) 1 a A 2 a B (no hay opción) 1 a B 4 a C (no hay opcion) 1 a C 2 a A (no hay opcion) 1 a A 3 a C (no hay opción) 1 a B 2 a C(no hay opción) 1 a C

Mediante recursividad[editar]

Este problema se suele plantear a menudo en programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, si llamamos origen a la primera pila de discos, destino a la tercera y auxiliar a la intermedia, y si a la función la denomináramos hanoi, con origen, auxiliar y destino como parámetros, el algoritmo de la función sería el siguiente:

Algoritmo Torres de Hanói (Complejidad \Theta(2^n))

Entrada: Tres pilas de números origen, auxiliar, destino, con la pila origen ordenada

Salida: La pila destino

  1. si origen \scriptstyle == \{1\} entonces
    1. mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino)
    2. terminar
  2. si no
    1. hanoi(\scriptstyle \{1, \dots , n-1 \},origen,destino, auxiliar)     //mover todas las fichas menos la más grande (n) a la varilla auxiliar
  3. mover disco n a destino                //mover la ficha grande hasta la varilla final
  4. hanoi (auxiliar, origen, destino)          //mover todas las fichas restantes, 1...n–1, encima de la ficha grande (n)
  5. terminar

El número de movimientos mínimo a realizar para resolver el problema de este modo es de 2n – 1, siendo n el número de discos.

Iterativa[editar]

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

Una forma equivalente de resolverlo es la siguiente: coloreando los discos pares de un color y los impares de otro, y se resuelve el problema añadiendo la siguiente regla: no colocar juntos dos discos de un mismo color. De esta manera, solo queda un movimiento posible (además del de volver hacia atrás).

Variantes[editar]

Henry Dudeney en su libro The Canterbury Puzzles (1907) propuso una variante (llamada «Problema del almojarife» o The reve's puzzle) que usa cuatro agujas en lugar de tres.[2] En 1939, J. S. Frame y B. M. Stewart propusieron —en forma independiente— un algoritmo que resuelve el problema, dado un parámetro i:

  1. Trasladar recursivamente una pila de n – i discos, desde la aguja inicial a otra auxiliar, usando las cuatro agujas en el proceso.
  2. Trasladar los i discos más grandes, desde la aguja inicial hacia la aguja final, usando el algoritmo estándar para tres agujas e ignorando la cuarta.
  3. Recursivamente trasladar los n – i discos más pequeños, desde la aguja auxiliar hacia la aguja final, usando las cuatro agujas en el proceso.

Y demostraron que, si n es igual al número triangular tk, la elección óptima para i es justamente k, y si tk – 1 < n < tk, tanto k – 1 como k lo son. Nótese que se está hablando del valor óptimo para este algoritmo particular; encontrar el número mínimo de movimientos en el caso general es, todavía, una cuestión abierta. Sin embargo, para n menor o igual a 30 discos se ha verificado que el algoritmo de Frame-Stewart es, efectivamente, óptimo.[3]

Véase también[editar]

Notas y referencias[editar]

  1. Walter William Rouse Ball, Harold Scott Macdonald Coxeter, (1987), «Mathematical recreations and essays»,Dover Publications, ISBN 0-486-25357-0
  2. Paul Stockmeyer (1994). «Variations on the Four-Post Tower of Hanoi Puzzle». Congressus Numerantium 102:  pp. 3-12. http://www.cs.wm.edu/~pkstoc/boca.ps. 
  3. Richard E. Korf; Ariel Felner (2007). «Recent Progress in Heuristic Search: a Case Study of the Four-Peg Towers of Hanoi Problem». International Joint Conference on Artificial Intelligence:  pp. 2324-2329. http://www.ijcai.org/papers07/Papers/IJCAI07-374.pdf. 

Enlaces externos[editar]