Torres de Hanói 1

Torres de Hanói

Torres de Hanói.

Las Torres de Hanói es un rompecabezas ojuego matemático inventado en 1883 por elmatemático francés Édouard Lucas.[1] Estesolitario se trata de un juego de ocho discosde radio creciente que se apilan insertándoseen una de las tres estacas de un tablero. Elobjetivo del juego es crear la pila en otra delas estacas siguiendo unas ciertas reglas. Elproblema es muy conocido en la ciencia dela computación y aparece en muchos librosde texto como introducción a la teoría dealgoritmos.

Descripción

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

El juego, en su forma más tradicional, consiste en tres varillasverticales. En una de las varillas se apila un número indeterminado dediscos (elaborados de madera) que determinará la complejidad de lasolución, por regla general se consideran ocho discos. Los discos seapilan sobre una varilla en tamaño decreciente. No hay dos discosiguales, y todos ellos están apilados de mayor a menor radio en una delas varillas, quedando las otras dos varillas vacantes. El juego consisteen pasar todos los discos de la varilla ocupada (es decir la que posee latorre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:

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

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 centrodel mundo. Allí estaba una bandeja sobre la queexistían tres agujas de diamante. En una mañanalluviosa, un rey mandó a poner 64 discos de oroordenados por tamaño: el mayor, en la base de labandeja, y el menor, arriba de todos los discos. Tras sucolocación, los sacerdotes del templo intentaron moverlos discos entre las agujas, según las leyes que se leshabían entregado: «El sacerdote de turno no debemover más de un disco a la vez, y no puede situar

Torres de Hanói 2

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 queestos monjes consiguieran terminar el juego, el mundo acabaría. No obstante, esta leyenda resultó ser un inventopublicitario del creador del juego, el matemático Éduard Lucas. (En aquella época, era muy común encontrarmatemáticos ganándose la vida de forma itinerante con juegos de su invención, de la misma forma que los juglares lohacían con su música. No obstante, la falacia resultó ser tan efectista y tan bonita que ha perdurado hasta nuestrosdías. Además, invita a realizarse la pregunta: «Si la leyenda fuera cierta, ¿cuándo sería el fin del mundo?».) Lamínima cantidad de movimientos para resolver este problema es de 264 – 1; si los monjes hicieran un movimientopor 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ónLa solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el número de pasos para resolver elproblema crece exponencialmente conforme aumenta el número de discos.

Solución simpleUna forma de resolver el problema se fundamenta en el disco más pequeño, el de más arriba en la varilla de origen.El movimiento inicial de este es hacia la varilla auxiliar. El disco n.o 2 se debe mover, por regla, a la varilla destino.Luego, el disco n.o 1 se mueve también a la varilla destino para que quede sobre el disco n.o 2. A continuación, semueve el disco que sigue de la varilla origen, en este caso el disco n.o 3, y se coloca en la varilla auxiliar.Finalmente, el disco n.o 1 regresa de la varilla destino a la origen (sin pasar por la auxiliar), y así sucesivamente. Esdecir, el truco está en el disco más pequeño.

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

Algoritmo Torres de Hanói (Complejidad )

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

Salida: La pila destino

1. si origen entonces

1. mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino)2.2. terminar

2.2. si no

1. hanoi( ,destino, auxiliar)     //mover todas las fichas menos la más grande (n) a la varilla auxiliar3. mover disco n a destino                //mover la ficha grande hasta la varilla final4. hanoi (auxiliar, origen, destino)          //mover todas las fichas restantes, 1...n–1, encima de la ficha grande (n)5.5. terminar

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

Torres de Hanói 3

IterativaOtra manera de resolver el problema, sin utilizar la recursividad, se basa en el hecho de que para obtener la soluciónmás corta, es necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares sóloexiste un movimiento posible que no lo incluye. El problema se reduce a decidir en cada paso impar a cuál de las dospilas 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á enla 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 lapila 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, yse resuelve el problema añadiendo la siguiente regla: no colocar juntos dos discos de un mismo color. De estamanera, solo queda un movimiento posible (además del de volver hacia atrás).

VariantesHenry 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. En 1939, J. S. Frame y B. M. Stewart propusieron —enforma 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 elnúmero mínimo de movimientos en el caso general es, todavía, una cuestión abierta. Sin embargo, para n menor oigual a 30 discos se ha verificado que el algoritmo de Frame-Stewart es, efectivamente, óptimo.

Notas y referencias[1] Walter William Rouse Ball, Harold Scott Macdonald Coxeter, (1987), «Mathematical recreations and essays»,Dover Publications, ISBN

0-486-25357-0

Enlaces externos• Wikimedia Commons alberga contenido multimedia sobre Torre de Hanói. Commons• Artículo de Antonio Javier Serrano Mora sobre La Torre de Hanói (http:/ / olmo. pntic. mec. es/ ~aserra10/

articulos/ hanoi. html)• Artículo de Rodolfo Valeiras sobre La Torre de Hanoi (http:/ / www. rodoval. com/ heureka/ hanoi/ index. html)

Fuentes y contribuyentes del artículo 4

Fuentes y contribuyentes del artículoTorres de Hanói  Fuente: http://es.wikipedia.org/w/index.php?oldid=71915356  Contribuyentes: Abece, Albireo3000, Amadís, Andreasmperu, Angueto, Balles2601, Biasoli, Canopus49,CarlosHoyos, Carlospretelt, Cinabrium, Colo cali, Diegusjaimes, Dossier2, EgrojSoft, Emijrp, FAR, Felipealvarez, Fremen, Gafotas, Galandil, GermanX, Ggenellina, HUB, Hari Seldon, Helmyoved, Intimalai, Isha, JacobRodrigues, Johnbojaen, Juntik, KnightRider, LP, Lima moretes, Lourdes Cardenal, Magister Mathematicae, Manwë, Markoszarrate, Miguelangelcv, Mister,Montgomery, Mrexcel, Muro de Aguas, OMenda, Paintman, Parras, Pilaf, Pólux, Rafa3040, Ralgis, Raulshc, Rovnet, Rsg, Sabbut, Sanbec, Simprosio, SuperBraulio13, Superzerocool, Taichi,Tamorlan, Thelmadatter, Vitamine, 244 ediciones anónimas

Fuentes de imagen, Licencias y contribuyentesArchivo:Tower of Hanoi.jpeg  Fuente: http://es.wikipedia.org/w/index.php?title=Archivo:Tower_of_Hanoi.jpeg  Licencia: GNU Free Documentation License  Contribuyentes: Ies, ÆvarArnfjörð BjarmasonArchivo:Tower of Hanoi 4.gif  Fuente: http://es.wikipedia.org/w/index.php?title=Archivo:Tower_of_Hanoi_4.gif  Licencia: Creative Commons Attribution-Sharealike 2.5  Contribuyentes:André Karwath aka AkaFile:UniversumUNAM34.JPG  Fuente: http://es.wikipedia.org/w/index.php?title=Archivo:UniversumUNAM34.JPG  Licencia: Creative Commons Attribution-Sharealike 3.0  Contribuyentes:User:AlejandroLinaresGarciaArchivo:Commons-logo.svg  Fuente: http://es.wikipedia.org/w/index.php?title=Archivo:Commons-logo.svg  Licencia: logo  Contribuyentes: SVG version was created by User:Grunt andcleaned up by 3247, based on the earlier PNG version, created by Reidab.

LicenciaCreative Commons Attribution-Share Alike 3.0//creativecommons.org/licenses/by-sa/3.0/