Torres de Hanói

En una de mis publicaciones anteriores se encuentra la presentación del tema de las Torres de Hanoi, es lo que en clase explique, pero como no tienen mucho texto que explique lo que yo dije en clase, entonces hago esta publicación con una breve explicación de cada diapositiva.

Explicación de mi presentación "Torres de Hanói"

El juego consiste en pasar todos los discos del poste ocupad, es decir, la que posee la torre de discos, a una de los otros postes 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.

El juego de las Torres de Hanói consiste en tres postes que serán indicados con las letras A, B y C, por lo general de izquierda a derecha, aunque el orden realmente no importa, es solo para poder referirnos a cada uno de los postes. El juego clásico contiene todos los discos en el poste A, estos son apilados en orden según su tamaño, estando el de radio mayor en la base de nuestra torre. Para referirnos a los discos, estos son numerados del 1 al 8, en el ejemplo de la diapositiva, por ser 8 discos totales, sabiendo que el disco 1 será el de la punta de la torre.

En mi caso especial, tome la instancia de 5 discos, así que para saber cuantos son el mínimo de movimientos requeridos para pasar toda la torre del poste A al C, se calcula con la formula (2^n)-1, donde n es el número de discos que tiene nuestra torre. En este caso por ser la torre de 5 discos tenemos que los movimientos mínimos necesarios para resolver esta torre es de 31 movimientos.

También podemos saber cuantas veces será necesario mover cada disco para resolverlo, y se tiene que el disco de la base, en este caso el 5, solo se mueve una vez. Esto va en orden de la potencias del 2, empezando del "dos a la cero", hasta llegar a "dos a la cuatro", que corresponde al disco 1, el más pequeño. Y para comprobar que si son los movimientos de cada disco, podemos sumar los movimientos de cada disco y nos dará en este caso 31, que es lo que calculamos con la formula.

Para darnos una idea del número de movimientos posibles y permisibles, empezamos con un solo disco para ejemplificar. En este caso solo se tienen dos posibilidades de movimiento si en un inicio se estaba en la torre A, podemos mover a la torre B o C.

Ahora vemos el ejemplo con dos discos, y ya nuestras opciones de movimientos se incrementaron. Podemos observar mediante los dibujos que se encuentran en cada nodo del árbol, como quedaría nuestras tres torres según el disco que movamos.

Desde que tenemos dos discos nos topamos en que si no se piensa correctamente los movimientos que haremos, podríamos entrar en un ciclo sin salida, ya que después de un movimiento es posible regresar al estado anterior, pero aquí el objetivo del juego es tener todos los discos en una torre diferente a la inicial.

En esta imagen podemos observar el árbol con todos los movimientos posibles y permisibles que un jugador lograría hacer en el caso de 5 discos, no se diga si se desea resolver uno de 8 discos o más.

Pero como ya mencionaba, el objetivo es realizar el mínimo de movimientos posibles, que ya calculamos para el caso de 5 discos, que nos resultó 31 movimientos de discos, y esto como se indica en la linea amarilla, es el camino para resolver la torre de 5 discos con solo 31 movimientos.

Representando los posibles movimientos como un grafo, siempre tendremos que la diagonal del costado derecho nos guiará a el mínimo de movimientos, que es ir de la torre A (punto verde), a la torre C (punto rojo).

Y por tener tantos posibles movimientos, es posible perderse en alguno de estos y guiarnos a un movimiento innecesario o repetido, lo que nos llevaría a no lograr el objetivo del juego.

En la imagen se observa el camino más largo que se puede tomar para llegar a la solución.

En siguiente enlace encontré muy buena información, y una explicación a detalle del juego, junto con algunas variantes:
Las torres de Hanói

Y si desean jugar un poco, les dejo otro enlace, donde pueden jugar desde 3 a 12 discos, o si lo desean también pueden observar los movimientos para resolver cierta torre con el número de discos que desees:
Mazeworks
Nota: Es probable que necesites instalar algún plugin.