Las Torres de Hanói son un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas. Consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en la primera varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento.
El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente.
Las reglas son:
* 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.
El Algoritmo de Dios es una idea originada por las discusiones sobre los distintos caminos para resolver un cubo de Rubik, pero que también puede ser aplicado en otros puzzles combinatorios y juegos matemáticos. Se usa para cualquier algoritmo práctico que produzca una solución con el menor número posible de movimientos, con la idea de que un ser omnisciente conocería una solución óptima para cada posible configuración.
Ejemplos
Se desconoce si existe un algoritmo de Dios para el cubo de Rubik.
Para el puzzle del quince, el problema para encontrar una solución se conoce que es NP-hard. De todos modos, todavía no se sabe si existe un algoritmo de Dios para este problema. Para el juego de las torres de Hanoi, existe un algoritmo de Dios para cualquier número posible de discos.
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 otras 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.
Otra manera de resolverlo es basá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-1 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+1)
- terminar
Resolución de la torre de cuatro discos
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, etc.
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
- 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 numero 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.
Dato inutil: "...sabias que existe la escala Scoville que mide la potencia picante de algunas salsas, siendo la substancia más picante la capsaicina pura"
manda por e-mail esta entrada...
meme
ordenador portatil
intel tecnologia
ubuntu juegos linux