Torre de Hanoi

Una solución sencilla para el rompecabezas de juguete es alternar entre 1) mover la pieza superior y 2) mover otra pieza.

En el caso 1, siempre que movemos la parte superior, la desplazamos a la siguiente posición en la misma dirección. Esto es hacia la derecha si el número inicial de piezas es par, o hacia la izquierda si el número inicial de piezas es impar.

Imaginamos que las torres están dispuestas en círculo, o que la imagen del rompecabezas se extiende horizontalmente, de modo que al movernos hacia la izquierda desde la primera torre llegamos a la tercera, y al movernos hacia la derecha desde la tercera torre llegamos a la primera.

En otras palabras, los pasos 1, 3, 5, 7... colocarán la parte superior de A > B > C > A ... (para un número par de piezas) o A > C > B > A ... repetir (para un número impar de piezas).

Para el 2, siempre que movemos otra pieza, siempre hay solo un movimiento legal, ya que ninguna pieza puede moverse a la más pequeña, y de cualquier combinación de otras piezas, solo una encajará con la otra.

Siguiendo correctamente los pasos 1, 2, 1, 2, ... se completará el rompecabezas en el menor número de movimientos. ^{[ 13 ]}

La clave para resolver un problema recursivamente reside en reconocer que puede descomponerse en un conjunto de subproblemas más pequeños, a cada uno de los cuales se aplica el mismo procedimiento general de resolución que buscamos , y la solución total se halla de forma sencilla a partir de las soluciones de dichos subproblemas. El hecho de que cada uno de estos subproblemas creados sea "más pequeño" garantiza que, finalmente, se alcanzará el caso base. Para las Torres de Hanoi:

• etiqueta las clavijas A, B, C,
• Sea n el número total de discos, y
• Numera los discos del 1 (el más pequeño, el de arriba) al n (el más grande, el de abajo).

Suponiendo que los n discos están distribuidos en arreglos válidos entre las clavijas; suponiendo que hay m discos superiores en una clavija de origen , y que todos los demás discos son más grandes que m , por lo que pueden ignorarse con seguridad; mover m discos de una clavija de origen a una clavija de destino usando una clavija de repuesto , sin violar las reglas:

1. Traslada m − 1 discos desde la clavija de origen a la clavija de reserva , siguiendo el mismo procedimiento general de resolución . Por supuesto, no se infringen las reglas. Esto deja el disco m como disco superior en la clavija de origen.
2. Mover el disco m desde la clavija de origen hasta la clavija de destino , lo cual está garantizado que es un movimiento válido, según las suposiciones, es un paso simple .
3. Mueva los m − 1 discos que acabamos de colocar en el repuesto, desde el repuesto hasta la clavija objetivo mediante el mismo procedimiento general de resolución , de modo que se coloquen encima del disco m sin violar las reglas.
4. El caso base consiste en mover 0 discos (en los pasos 1 y 3), es decir, no hacer nada, lo cual no infringe las reglas.

La solución completa de la Torre de Hanoi consiste en mover n discos desde la clavija de origen A hasta la clavija de destino C, utilizando B como clavija de reserva.

Este enfoque puede demostrarse matemáticamente de forma rigurosa mediante inducción matemática y se utiliza con frecuencia como ejemplo de recursión al enseñar programación.

Las posiciones de los discos en un rompecabezas de n discos se pueden determinar directamente a partir de la representación binaria del número de movimiento, m . Por ejemplo, todos los detalles del movimiento m = 216 de la Torre de Hanoi de 8 discos se pueden calcular sin iteración ni recursión, y sin referencia a movimientos previos ni a la distribución de discos. A la inversa, dada una distribución válida de discos, se puede calcular el número de movimiento necesario para lograr dicha distribución.

Sean los discos numerados del n al 1 , del n al n al 1, en orden decreciente de tamaño. Sean las clavijas A , B y C numeradas del 0 al 2, respectivamente, siendo el 0 la clavija inicial y el 2 la clavija final. Además, sean las bases de las clavijas sobre las que se apilan los discos numeradas del n al 1, del n al 2 y del n al 3, respectivamente.

Las posiciones del disco después del movimiento m se pueden mapear a partir de la representación binaria de m mediante las siguientes reglas: ^{[ 14 ]}

• Hay 1 dígito binario (bit) en m para cada disco.

• La cadena de bits para m se lee de izquierda a derecha, y cada bit se puede usar para mapear la ubicación del disco correspondiente, desde el disco n hasta el disco 1.
• El bit más significativo (el de la izquierda) representa el disco más grande, el disco n . Un valor de 0 indica que el disco más grande está en la clavija inicial 0 ( A ), mientras que un 1 indica que está en la clavija final 2 ( C ).
• Después de cualquier movimiento:

1. Cada disco se apila sobre otro disco, o sobre una base vacía, en orden de paridad opuesto . Es decir: 5>4>3 (3 sobre 4 sobre 5) es válido; 5>4>2 (con 2 sobre 4) no es válido.
2. Exactamente 1 de las etiquetas superiores (número de disco o base vacía) es par (para n par; de lo contrario, exactamente 1 es impar).
3. Un bit con el mismo valor que el dígito anterior significa que el disco correspondiente está apilado encima del anterior. Es decir: una secuencia contigua de 1s o 0s significa que los discos correspondientes están todos en la misma clavija.

• Un bit con un valor diferente al anterior significa que el disco correspondiente está en otra clavija y no en la pila anterior. Dado lo anterior (1), solo una de las dos clavijas restantes es una colocación válida. Cabe destacar que, tras la colocación del primer conjunto de discos, cada ronda de colocación comienza y termina con una de las clavijas potenciales con paridad par y la otra con paridad impar.

Por ejemplo, en la Torre de Hanoi de 8 discos:

• Mover 0 = 00000000.
  • El bit más grande del disco (el de más a la izquierda) es 0, por lo que está en la clavija inicial (0).
  • Todos los demás discos también son 0, por lo que se apilan encima. Por lo tanto, todos los discos están en la clavija inicial, en la configuración inicial del rompecabezas.
• Mover 255 ₁₀ (2 ⁸ − 1) = 11111111.
  • El bit más grande del disco es 1, por lo que está en la clavija final (2).
  • Todos los demás discos también valen 1, así que se apilan encima. Por lo tanto, todos los discos están en la última clavija y el rompecabezas está resuelto.
• Mover 216 ₁₀ = 11011000.
  • El bit más grande del disco es 1, por lo que el disco 8 está en la clavija final (2). Nótese que se encuentra en la base número 11 (11>8).
  • El disco 7 también es 1, por lo que está apilado encima del disco 8 (11>8>7).
  • El disco 6 es 0, por lo que se coloca en otra clavija. La clavija 1 está vacía, pero su base es 10. El disco 6 no puede colocarse en la base 10 (ambas son pares). Por lo tanto, el disco 6 se coloca en la clavija 0 (9 > 6).
  • El disco 5 es 1, por lo que se coloca en otra clavija. Dado que la clavija 2 ahora tiene un 7, no puede ir allí. Por lo tanto, el disco 5 se coloca en la clavija 1 (10 > 5).
  • El disco 4 también es 1, por lo que está apilado encima del disco 5 (10>5>4).
  • El disco 3 es 0, por lo que está en otra clavija. Como la clavija 2 tiene un 7 encima, no puede ir allí. El disco 3 se coloca en la clavija 0 (9>6>3).
  • Los discos 2 y 1 también son 0, por lo que están apilados encima del disco 3 (9>3>2>1).

Los puntos de origen y destino para el m -ésimo movimiento (excluyendo el movimiento 0) se pueden encontrar elegantemente a partir de la representación binaria de m usando operaciones bit a bit . Para usar la sintaxis del lenguaje de programación C , el movimiento m es:

de clavija a clavija .(m & m - 1) % 3((m | m - 1) + 1) % 3

Otra formulación para esto es:

de clavija a clavija .(m - (m & -m)) % 3(m + (m & -m)) % 3

Esto se aplica a los rompecabezas con n impar . Para los rompecabezas con n par , las referencias de salida a las clavijas 1 y 2 deben invertirse.

Además, el disco único que se moverá para cualquier movimiento específico se determina por la cantidad de veces que el contador de movimientos ( m ) se puede dividir por 2 (es decir, la cantidad de bits cero consecutivos a la derecha de m ) y luego sumar 1. En el ejemplo anterior para el movimiento 216, con 3 0 a la derecha, el disco 4 (3 + 1) se mueve de la clavija 2 a la clavija 1.

El sistema numérico binario de los códigos Gray ofrece una forma alternativa de resolver el rompecabezas. En el sistema Gray, los números se expresan mediante una combinación binaria de 0 y 1, pero en lugar de ser un sistema numérico posicional estándar , el código Gray se basa en la premisa de que cada valor difiere de su predecesor en un solo bit.

Si se cuenta en código Gray con un tamaño de bit igual al número de discos en una Torre de Hanoi en particular, comenzando en cero y contando hacia arriba, entonces el bit que cambia en cada movimiento corresponde al disco que se mueve, donde el bit menos significativo es el disco más pequeño y el bit más significativo es el más grande.

Contando los movimientos desde 1 e identificando los discos por números que comienzan desde 0 en orden de tamaño creciente, el ordinal del disco que se va a mover durante el movimiento m es el número de veces que m se puede dividir por 2.

Esta técnica identifica qué disco mover, pero no a dónde moverlo. Para el disco más pequeño, siempre hay dos posibilidades. Para los demás discos, siempre hay una posibilidad, excepto cuando todos los discos están en la misma clavija, pero en ese caso o bien es el disco más pequeño el que debe moverse o el objetivo ya se ha logrado. Por suerte, existe una regla que sí indica a dónde mover el disco más pequeño. Sea f la clavija de inicio, t la clavija de destino y r la tercera clavija restante. Si el número de discos es impar, el disco más pequeño recorre las clavijas en el orden f → t → r → f → t → r , etc. Si el número de discos es par, esto debe invertirse: f → r → t → f → r → t , etc. ^{[ 15 ]}

La posición del cambio de bit en la solución del código Gray da el tamaño del disco movido en cada paso: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, ... (secuencia A001511 en la OEIS ) , ^{[ 16 ]} una secuencia también conocida como la función de regla , o uno más que la potencia de 2 dentro del número de movimiento. En el lenguaje Wolfram , IntegerExponent[Range[2^8 - 1], 2] + 1da los movimientos para el rompecabezas de 8 discos.

Si todos los movimientos deben realizarse entre clavijas adyacentes (es decir, dadas las clavijas A, B y C, no se puede mover directamente entre las clavijas A y C), entonces mover una pila de n discos de la clavija A a la clavija C requiere 3n ⁻ 1 movimientos. La solución utiliza las 3n ^posiciones válidas, tomando siempre el único movimiento que no deshace el anterior. La posición con todos los discos en la clavija B se alcanza a la mitad, es decir, después de (3n ⁻ 1) / 2 movimientos. ^{[ 17 ] [ 18 ]}

En el problema de Hanoi Cíclico, se nos dan tres clavijas (A, B, C), dispuestas en círculo, con las direcciones en sentido horario y antihorario definidas como A – B – C – A y A – C – B – A, respectivamente. La dirección de movimiento del disco debe ser en sentido horario. ^{[ 19 ]} Basta con representar la secuencia de discos que se deben mover. La solución se puede encontrar utilizando dos procedimientos mutuamente recursivos:

Para mover n discos en sentido contrario a las agujas del reloj hasta la clavija objetivo vecina:

1. mover n − 1 discos en sentido contrario a las agujas del reloj hasta la clavija objetivo
2. Mueva el disco n .° un paso en el sentido de las agujas del reloj.
3. mover n − 1 discos en sentido horario hasta la clavija de inicio
4. Mueva el disco n .° un paso en el sentido de las agujas del reloj.
5. mover n − 1 discos en sentido contrario a las agujas del reloj hasta la clavija objetivo

Para mover n discos en el sentido de las agujas del reloj hasta la clavija objetivo vecina:

1. mover n − 1 discos en sentido contrario a las agujas del reloj hasta una clavija libre
2. Mueva el disco n .° un paso en el sentido de las agujas del reloj.
3. mover n − 1 discos en sentido contrario a las agujas del reloj hasta la clavija objetivo

Si C(n) y A(n) representan el movimiento de n discos en sentido horario y antihorario, entonces podemos escribir ambas fórmulas:

La solución para el Hanoi Cíclico tiene algunas propiedades interesantes:

1. Los patrones de movimiento para transferir una torre de discos de una clavija a otra son simétricos con respecto a los puntos centrales.
2. El disco más pequeño es el primero y el último en moverse.
3. Los grupos de movimientos de los discos más pequeños se alternan con movimientos individuales de otros discos.
4. El número de movimientos de discos especificados por C(n) y A(n) es mínimo.

Aunque la versión de tres clavijas tiene una solución recursiva simple que se conoce desde hace mucho tiempo, la solución óptima para el problema de la Torre de Hanoi con cuatro clavijas (llamado rompecabezas de Reve) no fue verificada hasta 2014 por Bousch. ^{[ 20 ]}

Sin embargo, en caso de cuatro o más clavijas, el algoritmo Frame-Stewart se conoce sin prueba de optimalidad desde 1941. ^{[ 21 ]}

Para la derivación formal del número exacto de movimientos mínimos necesarios para resolver el problema aplicando el algoritmo de Frame-Stewart (y otros métodos equivalentes), consulte el siguiente artículo. ^{[ 22 ]}

Para otras variantes del problema de la Torre de Hanoi de cuatro clavijas, véase el artículo de revisión de Paul Stockmeyer. ^{[ 23 ]}

Las denominadas configuraciones de juego Torres de Bucarest y Torres de Klagenfurt producen códigos Gray ternarios y pentarios . ^{[ 24 ]}

Una curiosa generalización del objetivo original del rompecabezas consiste en partir de una configuración dada de los discos, donde no todos los discos están necesariamente en la misma clavija, y llegar, con un número mínimo de movimientos, a otra configuración dada. En general, puede resultar bastante difícil calcular la secuencia más corta de movimientos para resolver este problema. Andreas Hinz propuso una solución basada en la observación de que, en la secuencia más corta de movimientos, el disco más grande que debe moverse (obviamente, se pueden ignorar todos los discos más grandes que ocuparán la misma clavija tanto en la configuración inicial como en la final) se moverá exactamente una o exactamente dos veces. ^{[ 27 ]}

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 una secuencia más corta de movimientos entre dos configuraciones de discos inicial y final elegidas al azar. Hinz y Chan Tat-Hung descubrieron independientemente ^{[ 28 ] [ 29 ]} (véase también ^{[ 30 ] : Capítulo 1, pág. 14} ) que el número promedio de movimientos en una Torre de n discos viene dado por la siguiente fórmula exacta:

${\displaystyle {\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}.}$

Para valores de n suficientemente grandes , solo el primer y el segundo término no convergen a cero, por lo que obtenemos una expresión asintótica :${\displaystyle 466/885\cdot 2^{n}-1/3+o(1)}$, como${\displaystyle n\to \infty }$. Por lo tanto, intuitivamente, podríamos interpretar la fracción de${\displaystyle 466/885\approx 52.6\%}$como representativa de la relación del trabajo que uno tiene que 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 el camino "más difícil" de longitud${\displaystyle 2^{n}-1}$lo cual implica mover todos los discos de una clavija a otra. Romik ofreció una explicación alternativa para la aparición de la constante 466/885, así como un algoritmo nuevo y algo mejorado para calcular el camino más corto. ^{[ 31 ]}

En la Torre Magnética de Hanoi, cada disco tiene dos caras distintas, Norte y Sur (generalmente de color rojo y azul). No se deben colocar los discos con polos iguales juntos, ya que los imanes en cada disco impiden esta acción. Además, cada disco debe voltearse al moverlo.

Esta variación del famoso rompecabezas de la Torre de Hanoi se ofreció a estudiantes de 3.º a 6.º grado en el 2ème Championnat de France des Jeux Mathématiques et Logiques, celebrado en julio de 1988. ^{[ 32 ]}

Las reglas del rompecabezas son esencialmente las mismas: los discos se transfieren entre las clavijas de uno en uno. En ningún caso se puede colocar un disco más grande encima de uno más pequeño. La diferencia radica en que ahora, para cada tamaño, hay dos discos: uno negro y uno blanco. Además, ahora hay dos torres de discos de colores alternos. El objetivo del rompecabezas es lograr que las torres sean monocromáticas (del mismo color). Se supone que los discos más grandes en la base de las torres intercambian posiciones.

Una variante del rompecabezas se ha adaptado como un juego de solitario con nueve cartas bajo el nombre de Torre de Hanoy . ^{[ 33 ] [ 34 ]} Se desconoce si la ortografía alterada del nombre original es deliberada o accidental. ^{[ 35 ]}