Ver el código de «Torres de Hanói»

{{Ficha de juguete
|imagen             = Tower of Hanoi.jpeg
|tamañoimagen       = 300px
|pie_imagen         = Torres de Hanói 
|Nombre completo    = Torres de Hanói
|Otros nombres      = Torres de Brahma o Torres de Lucas
|Lugar de origen    = [[Francia]] {{bandera|Francia}}
|fechaorigen        = 1883
|Tipo               = [[Rompecabezas]]
|Inventor           = [[François Éduard Anatole Lucas|Édouard Lucas]]
|Compañía           = 
|fechadesde         = 
|unidadesvendidas   = 
|web                =
}}

Las '''Torres de Hanói''' es un [[rompecabezas]] o [[juegos matemáticos|juego matemático]] inventado en 1883 por el [[matemático]] [[Francia|francés]] [[François Éduard Anatole Lucas|Édouard Lucas]].<ref>Walter William Rouse Ball, Harold Scott Macdonald Coxeter, (1987), ''«Mathematical recreations and essays»'',Dover Publications, ISBN 0-486-25357-0</ref> Este [[juego de mesa]] individual consiste en un número de discos perforados de radio creciente que se apilan insertándose en uno de los tres postes fijados a un tablero. El objetivo del juego es trasladar la pila a otro de los postes siguiendo ciertas reglas, como que no se puede colocar un disco más grande encima de un disco más pequeño. 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 [[algoritmo]]s.

La fórmula para encontrar el número de movimientos necesarios para transferir ''n'' discos desde un poste a otro es: 2<sup>''n''</sup> - 1.

== Descripción ==
[[Archivo:Tower of Hanoi 4.gif|mini|250px|Resolución del problema con 4 discos]]
El juego, en su forma más tradicional, consiste en tres postes verticales. En uno de los postes se apila un número indeterminado de discos perforados por su centro (elaborados de madera), que determinará la complejidad de la solución. Por regla general se consideran siete discos. Los discos se apilan sobre uno de los postes en tamaño decreciente de abajo arriba. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio -desde la base del poste hacia arriba- en uno de los postes, quedando los otros dos postes vacíos. El juego consiste en pasar todos los discos desde el poste ocupado (es decir, el que posee la torre) a uno de los otros postes vacíos. Para realizar este objetivo, es necesario seguir tres simples reglas:

# Solo se puede mover un disco cada vez y para mover otro los demás tienen que estar en postes.
# Un disco de mayor tamaño no puede estar sobre uno más pequeño que él mismo.
# Solo se puede desplazar el disco que se encuentre arriba en cada poste.

Existen diversas formas de llegar a la solución final, todas ellas siguiendo estrategias diversas.

== Historia ==
[[File:UniversumUNAM34.JPG|thumb|250px|Visitantes en el museo [[Universum]] experimentando con un montaje interactivo]]

El rompecabezas fue inventado por el [[matemático]] [[Pueblo francés|francés]] [[Édouard Lucas]] en 1883. Se cuenta una historia sobre un templo en la [[India]] en [[Kashi Vishwanath]] que contiene una gran sala con tres postes gastados por el tiempo, rodeada de 100 discos dorados. Los sacerdotes de [[Brahmán (casta)|Brahma]], actuando bajo el mandato de una antigua profecía, han estado moviendo estos discos de acuerdo con las reglas inmutables de Brahma desde ese momento. Por lo tanto, el acertijo también se conoce como el rompecabezas de la Torre de [[Brahma]]. Según la leyenda, cuando se complete el último movimiento del rompecabezas, el mundo se terminará.<ref>{{cita libro |apellido=Spitznagel |nombre=Edward L. |título=Selected topics in mathematics |año=1971 |editorial=Holt, Rinehart and Winston |página=[https://archive.org/details/selectedtopicsin0000spit/page/137 137] |isbn=0-03-084693-5 |url=https://archive.org/details/selectedtopicsin0000spit/page/137 }}</ref> No está claro si Lucas inventó esta leyenda o si se inspiró en ella.

Si la leyenda fuera cierta, y si los sacerdotes pudieran mover los discos a una velocidad de uno por segundo, utilizando el menor número de movimientos, completar la tarea les llevaría 2<sup>100</sup>&nbsp;-&nbsp;1 segundos, o aproximadamente 4.019 cuatrillones de años, que es aproximadamente 290.942 cuatrillones de veces la edad actual del Universo.

Existen muchas variaciones en esta leyenda. Por ejemplo, en algunos relatos el templo es un [[monasterio]], y los sacerdotes son [[monje]]s. Se puede decir que el templo o monasterio se encuentra en diferentes partes del mundo, incluidos [[Hanói]], [[Vietnam]], y puede estar asociado con cualquier [[religión]]. En algunas versiones, se introducen otros elementos, como el hecho de que la torre fue creada en el comienzo del mundo, o que los sacerdotes o monjes solo pueden hacer un movimiento por día.

== Resolución ==

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 [[crecimiento exponencial|crece exponencialmente]] conforme aumenta el número de discos.Como ya se ha indicado, el número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanói es 2<sup>''n''</sup> - 1, donde ''n'' es la cantidad de discos.<ref>{{cita libro |apellido=Petković |nombre=Miodrag |título=Famous Puzzles of Great Mathematicians |url=https://archive.org/details/famouspuzzlesofg0000petk |año=2009 |editorial=AMS Bookstore |isbn=0-8218-4814-3 |página=[https://archive.org/details/famouspuzzlesofg0000petk/page/197 197]}}</ref>

Una manera sencilla para saber si es posible terminar el "juego" es que si la cantidad de discos es impar la pieza inicial irá a destino y si es par a auxiliar.

=== Solución simple ===

Una forma de resolver el problema se fundamenta en el disco más pequeño, el de más arriba en la varilla de ''origen''. En un juego con un número par de discos, el movimiento inicial de la varilla ''origen'' es hacia la varilla ''auxiliar''. El disco n.<sup>o</sup>&nbsp;2 se debe mover, por regla, a la varilla ''destino''. Luego, el disco n.<sup>o</sup>&nbsp;1 se mueve también a la varilla ''destino'' para que quede sobre el disco n.<sup>o</sup>&nbsp;2. A continuación, se mueve el disco que sigue de la varilla ''origen'', en este caso el disco n.<sup>o</sup>&nbsp;3, y se coloca en la varilla ''auxiliar''. Finalmente, el disco n.<sup>o</sup>&nbsp;1 regresa de la varilla ''destino'' a la ''origen'' (sin pasar por la ''auxiliar''), 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 [[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|
'''Entrada:''' Tres pilas de números ''origen'', ''auxiliar'', ''destino'', con la pila ''origen'' ordenada 

'''Salida:''' La pila ''destino''
# '''si''' ''origen'' <math>\scriptstyle == \{1\}</math> '''entonces'''
## '''mover''' el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino) 
## '''terminar'''
# '''si no'''
##''hanoi''(<math>\scriptstyle \{1, \dots , n-1 \}</math>,''origen'',''destino'', ''auxiliar'') &nbsp;&nbsp;&nbsp;&nbsp;//mover todas las fichas menos la más grande (''n'') a la varilla auxiliar
# '''mover''' disco ''n'' a ''destino'' &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //mover la ficha grande hasta la varilla final
# ''hanoi'' (''auxiliar'', ''origen'', ''destino'')&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //mover todas las fichas restantes, 1...''n''–1, encima de la ficha grande (''n'')
# '''terminar'''
||<math>\Theta(2^n-1)</math>}}

El número de movimientos mínimo a realizar para resolver el problema de este modo es de 2<sup>''n''</sup>&nbsp;–&nbsp;1, siendo ''n'' el número de discos.

=== Iterativa ===
[[Archivo:Iterative algorithm solving a 6 disks Tower of Hanoi.gif|thumb|250px|Solución iterativa con 6 discos]]
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 solo 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'',&nbsp;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'',&nbsp;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).<ref>{{cita publicación |apellido=Troshkin |nombre=M. |título=Doomsday Comes: A Nonrecursive Analysis of the Recursive Towers-of-Hanoi Problem |publicación=Focus |volumen=95 |número=2 |páginas=10–14 |año= |idioma=ruso }}</ref>

=== Reglas matemáticas de los desplazamientos ===
A la hora de resolver matemáticamente el problema, se producen numerosas circunstancias matemáticas particulares 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, 36... etc.
* Y el número de veces que se mueve cada ficha es de 2^(n-k),siendo n el número de fichas y k igual a 1 para la ficha más pequeña.
* 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 se quiere 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, se sabe siempre qué pieza hay que mover y a qué columna hay que desplazarla, por lo que el problema queda resuelto.

=== Demostración recurrente y por inducción. ===
Tengamos un plato de Hanói con tres varillas colocadas tal que la primera contenga los n discos ordenados y las otras dos varillas no contengan nada.

Empecemos definiendo el ejercicio más básico, tenemos un solo disco, por tanto el movimiento del primer plato al último es 1 solo paso.


<math>a_{1} = 1</math>
 <math>a_{0} = 0</math>  pues con 0 discos no hay movimiento que hacer;  para realizar la demostración no es necesario considerar este resultado pues no tiene sentido 0 discos en una torre de Hanói aunque se pueda considerar válido.
Para dos discos tenemos que mover el pequeño a la varilla auxiliar, el grande a la final y el pequeño a la final para un total de 3 pasos.

<math>a_{2} = 3</math>

Para tres discos tenemos que

<math>a_{3} = 7</math>  movimientos necesarios mínimos.


Para la resolución de este ejercicio se pueden aplicar dos caminos diferentes. La resolución de la ecuación en diferencia general que nos permitirá hallar las raíces de un [[polinomio]] y sus coeficientes para calcular posteriormente una función  f(n) que nos devuelva un número exacto de movimientos dados para n discos o aplicar recurrencia para tratar por intuición el resultado final:

==== Fórmula general ====
Tengamos un estado <math>a_{n}</math> que denota la cantidad de movimientos a realizar para n discos.

Para hallar la ecuación hay que aplicar una hipótesis que apoye la ecuación a demostrar:

* Sabemos que para un disco se necesita un movimiento, para dos discos tres movimientos y para tres discos se necesitan siete movimientos.

* Suponemos la hipótesis que para mover n discos se tiene que mover los (n-1) discos anteriores y uno más que es el disco n, además sabemos que esos discos deben moverse el doble de veces pues para 2 discos, hay que mover el disco pequeño dos veces, una para quitarlo de la cima y otra para ponerlo en la cima al final.

* Para tres discos es exactamente lo anterior, debemos mover los 2 discos menores 2 veces, una para quitarlos de encima del disco grande, 1 movimiento para mover el disco grande a la varilla final, y otra vez volver a mover los dos discos encima del disco grande.

Por tanto la fórmula final que nos queda es:

<math>a_{n} = 2 * a_{n-1} + 1</math>

Reordenándola:

<math>a_{n} - 2*a_{n-1} - 1 = 0</math>

Es una ecuación sencilla que se podría resolver fácilmente y llegar a la conclusión que para n discos dados los movimientos son:    <math>a_{n} = 2^{n} - 1</math>    Sin embargo, vamos a resolverla paso por paso para estudiarla.

En este caso podemos convertir los término dependientes de cada iteración en raíces polinomiales teniendo en cuenta que el grado del polinomio será del orden del menor término que haya presente, en este caso <math>a_{n-[1]}</math> tomamos el 1 como grado del polinomio pues el menor término es <math>a_{n-1}</math>, si hubiese un <math>a_{n-k}</math> k sería el grado del polinomio.

* Antes de eso hay que tomar su homogénea asociada, es decir suprimimos el término independiente:

<math>a_{n} - 2*a_{n-1} = 0</math>

* Reescribimos la ecuación correspondiente: sustituyendo <math>Dado \, \, k \, \, \{0, 1, ... , rank(pol) \} \in a_{n-k} \implies r^{rank(pol)-k}  : </math>

<math>r - 2 = 0</math>

* Por tanto la raíz característica de dicha ecuación resulta ser:

<math>r = 2</math>

En este caso solo tenemos una raíz simple son multiplicidad 1.

Tenemos por tanto que aplicando la fórmula general:

<math>a_{n} = C*r_{n}^{n}    : r = 2</math>   En este caso solo existe una r,  por tanto,    <math>a_{n} = C*2^{n}</math>    donde falta hallar el coeficiente C


Ahora falta recuperar la no homogénea, es decir hay que recuperar: <math>a_{n} - 2*a_{n-1} - 1 = 0</math>.

Realizando un cambio de variable, es decir sustituyendo los términos temporales, <math>a_{n}, a_{n-1}, \, ... \, , a_{1}</math>:

<math>a_{n}^{p}\,\, =\,\, B\,\, =\,\, 2*B \,\,+\,\, 1</math>,  por lo tanto <math>B = -1</math>.

La variable obtenida es el término independiente necesario para completar la ecuación.

Recuperamos la homogénea asociada con <math>B = -1</math> y hallamos su resultado:

<math>a_{n} = C*2^{n} + B \,\,\,:\,\,\, a_{n} = C*2^{n} - 1</math>.

Igualamos a las condiciones iniciales.

<math>a_{1} = C*2^{n}-1 \implies 1 = C*2^{1}-1 \implies C = \frac{1+1}{2^{1}} \implies C = 1 </math>
 Nota: Se puede realizar también con <math>a_{0} = 0 </math> pero como tal una torre de Hanói con 0 discos carece de sentido por lo que se utiliza <math>a_{1} = 1 </math>, el cual es el primer elemento  de la sucesión. Si se utilizase otro <math>a_{k} : k \in \{2, 3, ... , n\} </math> el resultado no coincidiría pues es un polinomio de grado uno y se está utilizando un elemento de la sucesión que supera dicho rango.
Por tanto el resultado final obtenido es:

<math>a_{n} = 2^{n} - 1 </math>.

==== Comprobación por Inducción. ====
Para la inducción débil partimos de la misma premisa que en la fórmula general pero en este paso utilizaremos otro método de verificación que en casos más sencillos como este ejercicio puede resultar más útil pero no es válido para todo tipo de sucesiones o ecuaciones en diferencia.

Tenemos un primer movimiento: <math>a_{1} = 1 </math>.

y previamente debido a la anterior demostración sabemos que para el movimiento <math>a_{n} = 2*a_{n-1} + 1 </math>.

Por tanto vamos a efectuar una [[concatenación]] de movimientos.

<math>a_{1} = 1 </math>

<math>a_{2} = 2*a_{1} + 1 </math>

<math>a_{3} = 2*a_{2} + 1 </math>

<math>a_{n} = 2*a_{n-1} + 1 </math>

Aplicando recurrencia descendente podemos llegar a la conclusión que

<math>a_{n} = 2*a_{n-1} + 1 = 2*(2*a_{n-2} + 1) + 1 = 2*(2*(2*a_{n-3} + 1)+1) + 1 </math>

<math>a_{4} = 2*a_{3} + 1 = 2*(2*a_{2} + 1) + 1 = 2*(2*(2*a_{1} + 1)+1) + 1 </math>

El siguiente paso es el deductivo y es el más importante pues una mala deducción llevara a un resultado.

Podemos observar que para <math>a_{n} </math> tenemos un 2 multiplicando <math>a_{n-1} </math> y un 1 sumando.

si hacemos lo mismo en <math>a_{n-1} </math> obtenemos el mismo resultado respecto a <math>a_{n-2} </math>.

Vemos que para n elementos dados obtenemos (n-1) 'doses' multiplicándose entre sí y (n-1) 1 multiplicados por sucesivos 'doses' tenemos que

<math>a_{n} = 2^{n-1} + \sum_{k=0}^{k=n-2} 2^{k} = 2^{n-1} + 2^{n-1} - 1 = 2^{n} - 1  </math>

En este caso la dificultad proviene en hallar el resultado de la suma sucesiva de potencias de orden 2, <math>1 + 2 + 4 + 8 + ... +\{n-2\} = 2^{n-1} - 1  </math>

En último caso podemos aplicar inducción débil para verificar que el resultado obtenido es el correcto:

===== Inducción débil. =====
<math>a_{n} = 2^n-1</math>

Paso base: k=1

<math>a_1 = 2^1-1=1</math>

Paso inductivo:

<math>a_k = 2^k - 1</math>   ¿Se verifica <math>a_{k+1} = 2^{k+1}-1</math> ?

<math>a_{k+1} = 2*a_k + 1</math>; pues <math>a_k = 2^k - 1</math>; <math>a_{k+1} = 2*\{2^k - 1\} + 1 = 2*2^k - 1 = 2^{k+1} - 1 </math>

Se verifica por inducción la veracidad de la fórmula.


Llegamos a la conclusión que ambos métodos son igualmente válidos para obtener la cantidad de movimientos necesarios para n discos dados ordenados en la primera varilla.

==Rutas más cortas generales y el número 466/885==
Una curiosa generalización del objetivo original del rompecabezas es comenzar desde una configuración dada de los discos, donde todos los discos no están necesariamente en el mismo poste, y llegar en un número mínimo de movimientos a otra configuración determinada. En general, puede ser bastante difícil calcular una secuencia más corta de movimientos para resolver este problema. Andreas Hinz propuso una solución y se basa en la observación de que, en la secuencia más corta de movimientos, se debe mover el disco más grande (obviamente, pueden ignorarse todos los discos más grandes que ocuparán el mismo poste tanto en la configuraciones inicial como en la final) se moverá exactamente una vez o exactamente dos veces.

Las matemáticas relacionadas con este problema generalizado se vuelven aún más interesantes cuando se considera el número promedio de movimientos en la secuencia más corta de movimientos entre dos configuraciones de disco iniciales y finales que se eligen al azar. Hinz y Chan Hat-Tung descubrieron de forma independiente<ref>{{cita publicación |nombre=A. |apellido=Hinz |título=The Tower of Hanoi |publicación=L'Enseignement Mathématique |volumen=35 |año=1989 |páginas=289–321 |doi=10.5169/seals-57378 }}</ref><ref>{{cita publicación |nombre=T. |apellido=Chan |título=A statistical analysis of the towers of Hanoi problem |publicación=Internat. J. Comput. Math. |volumen=28 |año=1988 |páginas=57–65 |doi=10.1080/00207168908803728}}</ref> (véase también
<ref>{{cita libro |apellido=Stewart |nombre=Ian |título=Another Fine Math You've Got Me Into... |editorial=Courier Dover |año=2004 |isbn=0-7167-2342-5 |capítulo=}}</ref>{{rp|Chapter 1, p.&nbsp;14}}) que la cantidad promedio de movimientos en una torre de ''n'' discos viene dada por la siguiente fórmula exacta:

: <math> \frac{466}{885}\cdot 2^n - \frac{1}{3} - \frac{3}{5}\cdot \left(\frac{1}{3}\right)^n +
\left(\frac{12}{59} + \frac{18}{1003}\sqrt{17}\right)\left(\frac{5+\sqrt{17}}{18}\right)^n +
\left(\frac{12}{59} - \frac{18}{1003}\sqrt{17}\right)\left(\frac{5-\sqrt{17}}{18}\right)^n.</math>

Tenga en cuenta que para ''n'' lo suficientemente grande, solo el primer y el segundo término no convergen a cero, por lo que obtenemos un [[Análisis asintótico|expresión asintótica]]:<math>466/885\cdot 2^n - 1/3 + o(1)</math>, cuando <math>n \to \infty</math>. Así, intuitivamente, se podría interpretar que la fracción de <math>466/885\approx 52.6\%</math> representa la relación del trabajo que se debe realizar al pasar de una configuración elegida al azar a otra configuración elegida al azar, en relación con la dificultad de tener que cruzar la ruta de longitud "más difícil" <math>2^n-1</math> que implica mover todos los discos de un poste a otro. Una explicación alternativa para la aparición de la constante 466/885, así como un algoritmo nuevo y algo mejorado para calcular la ruta más corta, fue dada por Romik.<ref>{{cita publicación |nombre=D. |apellido=Romik |título=Shortest paths in the Tower of Hanoi graph and finite automata |publicación=[[SIAM Journal on Discrete Mathematics]] |volumen=20 |número=3 |año=2006 |páginas=610–622 |doi=10.1137/050628660|url=http://arxiv.org/pdf/math/0310109 }}</ref>

== Algoritmos ==
Se presentan varias funciones recursivas que permiten implementar directamente la solución al problema de las Torres de Hanói.

La primera solución es una función en lenguaje Java.

static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)

   {

       if (n == 1)

       {

           System.out.println("Move disk 1 from rod " +  from_rod + " to rod " + to_rod);

           return;

       }

       towerOfHanoi(n-1, from_rod, aux_rod, to_rod);

       System.out.println("Move disk " + n + " from rod " +  from_rod + " to rod " + to_rod);

       towerOfHanoi(n-1, aux_rod, to_rod, from_rod);

   }

La segunda solución es en lenguaje C.

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)

{

   if (n == 1)

   {

       printf("Mover disco 1 desde el eje %c al eje %c\n", from_rod, to_rod);

       return;

   }

   towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);

   printf("Mover disco %d desde el eje %c al eje %c\n", n, from_rod, to_rod);

   towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);

}

Comentario: el algoritmo que resuelve el problema de las torres de Hanói no es paralelizable, no es posible aplicar ninguna estrategia de paralelismo como con OpenMP o CUDA.

== Variantes ==
[[Henry Dudeney]] en su libro ''The Canterbury Puzzles'' (1907) propuso una variante (llamada «Problema del almojarife» o ''The reve's puzzle'') que usa cuatro postes en lugar de tres.<ref>{{cita publicación|autor=Paul Stockmeyer |título=Variations on the Four-Post Tower of Hanoi Puzzle |publicación=Congressus Numerantium |volumen=102 |año=1994 |páginas=3-12 |url=http://www.cs.wm.edu/~pkstoc/boca.ps}}</ref> En 1939, J.&nbsp;S.&nbsp;Frame y B.&nbsp;M.&nbsp;Stewart propusieron —en forma independiente— un algoritmo que resuelve el problema, dado un parámetro ''i'':
# Trasladar recursivamente una pila de ''n''&nbsp;–&nbsp;''i'' discos, desde el poste inicial a otro auxiliar, usando los cuatro postes en el proceso.
# Trasladar los ''i'' discos más grandes, desde el poste inicial hacia el poste final, usando el algoritmo estándar para tres postes e ignorando el cuarto.
# Recursivamente trasladar los ''n''&nbsp;–&nbsp;''i'' discos más pequeños, desde el poste auxiliar hacia el poste final, usando los cuatro postes en el proceso.
Y demostraron que, si ''n'' es igual al [[número triangular]] ''t''<sub>''k''</sub>, la elección óptima para ''i'' es justamente ''k'', y si ''t''<sub>''k''&nbsp;–&nbsp;1</sub> < ''n'' < ''t''<sub>''k''</sub>, tanto ''k''&nbsp;–&nbsp;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 [[problema abierto|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.<ref>{{cita publicación |autor=Richard E. Korf |autor2=Ariel Felner |título=Recent Progress in Heuristic Search: a Case Study of the Four-Peg Towers of Hanoi Problem |publicación=International Joint Conference on Artificial Intelligence |año=2007 |páginas=2324-2329 |url=http://www.ijcai.org/papers07/Papers/IJCAI07-374.pdf |fechaacceso=15 de abril de 2013 |urlarchivo=https://web.archive.org/web/20150924033454/http://www.ijcai.org/papers07/Papers/IJCAI07-374.pdf |fechaarchivo=24 de septiembre de 2015 }}</ref>

== Véase también ==

* [[Recursividad]]
* [[Crecimiento exponencial]]
* [[Relación de recurrencia#Por hipótesis comprobada|Ecuación recurrencia]]

== Notas y referencias ==
{{listaref}}

== Enlaces externos ==

* {{Commonscat|Tower of Hanoi|Torre de Hanói}}
* [http://olmo.pntic.mec.es/~aserra10/articulos/hanoi.html Artículo de Antonio Javier Serrano Mora sobre La Torre de Hanói]
* [http://www.rodoval.com/heureka/hanoi/index.html Artículo de Rodolfo Valeiras sobre La Torre de Hanói]
*[http://verso.mat.uam.es/~pablo.fernandez/cap6-recurrencias.pdf Ecuaciones de recurrencia: (PDF)]
*[https://personal.us.es/pnadal/Informacion/leccion5ecdiferencias.pdf Ecuaciones en diferencia: (PDF)]
{{no más enlaces}}

{{Control de autoridades}}
[[Categoría:Rompecabezas]]