La Torre de Hanoi (también llamada Torre de Brahma o Torre de Lucas [1] ya veces pluralizada como Torres , o simplemente rompecabezas piramidal [2] ) es un juego o rompecabezas matemático . Consta de tres varillas y varios discos de diferentes diámetros , que pueden deslizarse sobre cualquier varilla. El rompecabezas comienza con los discos apilados en una varilla en orden de tamaño decreciente, el más pequeño en la parte superior, aproximándose así a una forma cónica .
El objetivo del rompecabezas es mover toda la pila hasta la última barra, obedeciendo las siguientes reglas simples:
- Solo se puede mover un disco a la vez.
- Cada movimiento consiste en tomar el disco superior de una de las pilas y colocarlo encima de otra pila o barra vacía.
- No se puede colocar ningún disco encima de un disco que sea más pequeño que él.
Con 3 discos, el rompecabezas se puede resolver en 7 movimientos. El número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanoi es 2 n - 1, donde n es el número de discos.
Orígenes
El rompecabezas fue inventado por el matemático francés Édouard Lucas en 1883. Numerosos mitos sobre la naturaleza antigua y mística del rompecabezas surgieron casi de inmediato. [3] Hay una historia sobre un templo indio en Kashi Vishwanath que contiene una gran sala con tres postes gastados por el tiempo, rodeada por 64 discos dorados. Los sacerdotes brahmanes , cumpliendo 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 rompecabezas 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 terminará. [4]
Si la leyenda fuera cierta, y si los sacerdotes pudieran mover discos a una velocidad de uno por segundo, usando el menor número de movimientos, tardarían 2 64 - 1 segundos o aproximadamente 585 mil millones de años en terminar, [5] lo cual es aproximadamente 42 veces la edad actual del universo.
Hay muchas variaciones en esta leyenda. Por ejemplo, en algunos relatos, el templo es un monasterio y los sacerdotes son monjes . Se puede decir que el templo o monasterio se encuentra en diferentes partes del mundo, incluido Hanoi , 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 al principio del mundo, o que los sacerdotes o monjes pueden hacer solo un movimiento por día.
Solución
El rompecabezas se puede jugar con cualquier cantidad de discos, aunque muchas versiones de juguetes tienen entre 7 y 9 de ellos. El número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanoi es 2 n - 1, donde n es el número de discos. [6] Este es precisamente el n- ésimo número de Mersenne .
Solución iterativa
Una solución simple para el rompecabezas de juguete es alternar movimientos entre la pieza más pequeña y una pieza no más pequeña. Cuando mueva la pieza más pequeña, muévala siempre a la siguiente posición en la misma dirección (a la derecha si el número inicial de piezas es par, a la izquierda si el número inicial de piezas es impar). Si no hay una posición de la torre en la dirección elegida, mueva la pieza al extremo opuesto, pero luego continúe moviéndose en la dirección correcta. Por ejemplo, si comenzó con tres piezas, movería la pieza más pequeña al extremo opuesto y luego continuaría en la dirección izquierda después de eso. Cuando el turno es para mover la pieza que no sea la más pequeña, solo hay un movimiento legal. Hacer esto completará el rompecabezas en la menor cantidad de movimientos. [7]
Declaración más simple de solución iterativa
Para un número par de discos:
- hacer el movimiento legal entre las clavijas A y B (en cualquier dirección),
- hacer el movimiento legal entre las clavijas A y C (en cualquier dirección),
- hacer el movimiento legal entre las clavijas B y C (en cualquier dirección),
- repita hasta completar.
Para un número impar de discos:
- hacer el movimiento legal entre las clavijas A y C (en cualquier dirección),
- hacer el movimiento legal entre las clavijas A y B (en cualquier dirección),
- hacer el movimiento legal entre las clavijas B y C (en cualquier dirección),
- repita hasta completar.
En cada caso, se realizan un total de 2 n - 1 movimientos.
Solución iterativa equivalente
Otra forma de generar la solución iterativa óptima única:
Numere los discos del 1 al n (de mayor a menor).
- Si n es impar, el primer movimiento es de la clavija A a la clavija C.
- Si n es par, el primer movimiento es de la clavija A a la clavija B.
Ahora, agregue estas restricciones:
- No se puede colocar ningún disco impar directamente sobre un disco impar.
- Ningún disco par se puede colocar directamente en un disco par.
- A veces habrá dos clavijas posibles: una tendrá discos y la otra estará vacía. Coloque el disco en la clavija que no esté vacía.
- Nunca mueva un disco dos veces seguidas.
Teniendo en cuenta esas limitaciones después del primer movimiento, solo hay un movimiento legal en cada turno posterior.
La secuencia de estos movimientos únicos es una solución óptima al problema equivalente a la solución iterativa descrita anteriormente. [8]
Solución recursiva
La clave para resolver un problema de forma recursiva es reconocer que se puede dividir en una colección de subproblemas más pequeños, a cada uno de los cuales se aplica el mismo procedimiento de resolución general que estamos buscando , y la solución total se encuentra entonces en algún método simple. lejos de las soluciones de esos subproblemas. Cada uno de estos subproblemas creados al ser "más pequeños" garantiza que eventualmente se alcanzarán los casos base. Desde allí, para las Torres de Hanoi:
- etiquetar las clavijas A, B, C,
- sea n el número total de discos,
- número de los discos de 1 (el más pequeño, superior) a n (más grande, más inferior).
Suponiendo que todos los n discos se distribuyen 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; para mover m discos de una clavija de origen a una clavija de destino usando una clavija de repuesto , sin violar las reglas:
- Mueva los discos m - 1 de la fuente a la clavija de repuesto , mediante el mismo procedimiento de solución general . Las reglas no se violan, por suposición. Esto deja el disco m como un disco superior en la clavija de origen.
- Mueva el disco m desde la fuente a la clavija de destino , lo que está garantizado como un movimiento válido, según los supuestos: un paso simple .
- Mueva los discos m - 1 que acabamos de colocar en el repuesto, desde el repuesto a la clavija de destino mediante el mismo procedimiento de resolución general , para que se coloquen encima del disco m sin violar las reglas.
- El caso base es mover 0 discos (en los pasos 1 y 3), es decir, no hacer nada, lo que obviamente no viola las reglas.
La solución completa de Tower of Hanoi consiste en mover n discos desde la clavija de origen A a la clavija de destino C, utilizando B como la clavija de repuesto.
A este enfoque se le puede dar una prueba matemática rigurosa con inducción matemática y se usa a menudo como un ejemplo de recursividad cuando se enseña programación.
Análisis lógico de la solución recursiva
Como en muchos acertijos matemáticos, encontrar una solución se hace más fácil resolviendo un problema un poco más general: cómo mover una torre de h (altura) discos desde una clavija de inicio f = A (desde) a una clavija de destino t = C (a ), Siendo B la tercera clavija restante y asumiendo t ≠ f . Primero, observe que el problema es simétrico para las permutaciones de los nombres de las clavijas ( grupo simétrico S 3 ). Si se conoce una solución que se mueve de la clavija A a la clavija C , entonces, al cambiar el nombre de las clavijas, se puede usar la misma solución para cualquier otra opción de clavija de inicio y de destino. Si solo hay un disco (o incluso ninguno), el problema es trivial. Si h = 1, entonces simplemente mover el disco a partir de PEG A a PEG C . Si h > 1, entonces en algún punto de la secuencia de movimientos, el disco más grande debe ser movido de PEG Una de otro palo, preferentemente a PEG C . La única situación que permite este movimiento es más pequeña cuando todo h - 1 discos están en paridad B . Por lo tanto, el primer h - 1 discos más pequeños deben ir de A a B . A continuación, mueva el disco más grande y finalmente mover el h - 1 discos más pequeños de clavija B a PEG C . La presencia del disco más grande no impide ningún movimiento de los discos h - 1 más pequeños y puede ignorarse temporalmente. Ahora el problema se reduce a mover discos h - 1 de una clavija a otra, primero de A a B y luego de B a C , pero el mismo método se puede utilizar en ambas ocasiones cambiando el nombre de las clavijas. Se puede utilizar la misma estrategia para reducir el problema h - 1 a h - 2, h - 3, y así sucesivamente hasta que solo quede un disco. A esto se le llama recursividad. Este algoritmo se puede esquematizar de la siguiente manera.
Identifique los discos en orden de tamaño creciente por los números naturales desde 0 hasta pero sin incluir h . Por tanto, el disco 0 es el más pequeño y el disco h - 1 el más grande.
El siguiente es un procedimiento para mover una torre de h discos de una clavija A a una clavija C , siendo B la tercera clavija restante:
- Si h > 1, a continuación, utilizar por primera vez este procedimiento para mover el h - 1 discos más pequeños de clavija A a PEG B .
- Ahora, el más grande de disco, es decir de disco h se puede mover de clavija A con PEG C .
- Si h > 1, a continuación, de nuevo utilizar este procedimiento para mover el h - 1 discos más pequeños de PEG B a PEG C .
Mediante inducción matemática , se demuestra fácilmente que el procedimiento anterior requiere el mínimo número de movimientos posibles y que la solución producida es la única con este mínimo número de movimientos. Usando relaciones de recurrencia , el número exacto de movimientos que requiere esta solución se puede calcular mediante:. Este resultado se obtiene observando que los pasos 1 y 3 toman se mueve, y el paso 2 toma un movimiento, dando .
Implementación recursiva
El siguiente código de Python destaca una función esencial de la solución recursiva, que de otro modo podría malinterpretarse o pasarse por alto. Es decir, con cada nivel de recursividad, la primera llamada recursiva invierte las pilas de destino y auxiliares , mientras que en la segunda llamada recursiva se invierten las pilas de origen y auxiliares .
A = [ 3 , 2 , 1 ] B = [] C = []def mover ( n , origen , destino , auxiliar ): si n > 0 : # Mueve n - 1 discos desde el origen al auxiliar, para que estén fuera del camino mover ( n - 1 , origen , auxiliar , destino ) # Mueva el disco n del origen al destino de destino . añadir ( fuente . pop ()) # Mostrar nuestra impresión de progreso ( A , B , C , '##############' , sep = ' \ n ' ) # Mover los n - 1 discos que dejamos en el auxiliar al movimiento de destino ( n - 1 , auxiliar , destino , fuente )# Iniciar la llamada desde la fuente A al objetivo C con el movimiento auxiliar B ( 3 , A , C , B )
Solución no recursiva
La lista de movimientos de una torre que se lleva de una clavija a otra, tal como la produce el algoritmo recursivo, tiene muchas regularidades. Cuando se cuentan los movimientos a partir de 1, el ordinal del disco que se moverá durante el movimiento m es el número de veces que m se puede dividir entre 2. Por lo tanto, cada movimiento impar involucra el disco más pequeño. También se puede observar que el disco más pequeño atraviesa las clavijas f , t , r , f , t , r , etc. para alturas impares de la torre y atraviesa las clavijas f , r , t , f , r , t , etc. para una altura uniforme de la torre. Esto proporciona el siguiente algoritmo, que es más fácil, realizado a mano, que el algoritmo recursivo.
En movimientos alternativos:
- Mueva el disco más pequeño a la clavija de la que no ha salido recientemente.
- Mueva otro disco legalmente (solo habrá una posibilidad).
Para el primer movimiento, el disco más pequeño va a la clavija t si h es impar y a la clavija r si h es par.
También observe que:
- Los discos cuyos ordinales tienen paridad par se mueven en el mismo sentido que el disco más pequeño.
- Los discos cuyos ordinales tienen paridad impar se mueven en sentido opuesto.
- Si h es par, la tercera clavija restante durante movimientos sucesivos es t , r , f , t , r , f , etc.
- Si h es impar, la tercera clavija restante durante movimientos sucesivos es r , t , f , r , t , f , etc.
Con este conocimiento, se puede recuperar un conjunto de discos en medio de una solución óptima sin más información de estado que las posiciones de cada disco:
- Llame a los movimientos detallados arriba del movimiento "natural" de un disco.
- Examine el disco superior más pequeño que no sea el disco 0 y observe cuál sería su único movimiento (legal): si no existe tal disco, entonces estamos en el primer o en el último movimiento.
- Si ese movimiento es el movimiento "natural" del disco, entonces el disco no se ha movido desde el último movimiento del disco 0, y ese movimiento debe realizarse.
- Si ese movimiento no es el movimiento "natural" del disco, mueva el disco 0.
Solución binaria
Las posiciones del disco se pueden determinar más directamente a partir de la representación binaria (base-2) del número de movimiento (el estado inicial es el movimiento # 0, con todos los dígitos 0 y el estado final con todos los dígitos 1), utilizando las siguientes reglas:
- Hay un dígito binario ( bit ) para cada disco.
- El bit más significativo (más a la izquierda) representa el disco más grande. Un valor de 0 indica que el disco más grande está en la clavija inicial, mientras que un 1 indica que está en la clavija final (la clavija derecha si el número de discos es impar y la clavija del medio en caso contrario).
- La cadena de bits se lee de izquierda a derecha y cada bit se puede utilizar para determinar la ubicación del disco correspondiente.
- Un bit con el mismo valor que el anterior significa que el disco correspondiente se apila sobre el disco anterior en la misma clavija.
- (Es decir: una secuencia recta de unos o ceros 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á una posición a la izquierda o derecha del anterior. Esta regla determina si es izquierda o derecha:
- Suponga que la clavija inicial está a la izquierda.
- Suponga también "envoltura", por lo que la clavija derecha cuenta como una clavija "izquierda" de la clavija izquierda, y viceversa.
- Sea n el número de discos mayores que se encuentran en la misma clavija que su primer disco mayor y agregue 1 si el disco más grande está en la clavija izquierda. Si n es par, el disco se ubica una clavija a la derecha, si n es impar, el disco se ubica una clavija a la izquierda (en el caso de un número par de discos y viceversa en caso contrario).
Por ejemplo, en un Hanoi de 8 discos:
- Mueve 0 = 00000000.
- El disco más grande es 0, por lo que está en la clavija izquierda (inicial).
- 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.
- Mueve 2 8 - 1 = 11111111.
- El disco más grande es 1, por lo que está en la clavija del medio (final).
- Todos los demás discos también son 1, por lo que se apilan encima. Por lo tanto, todos los discos están en la clavija final y el rompecabezas está completo.
- Mueve 216 10 = 11011000.
- El disco más grande es 1, por lo que está en la clavija del medio (final).
- El disco dos también es 1, por lo que se apila sobre él, en la clavija del medio.
- El disco tres es 0, por lo que está en otra clavija. Dado que n es impar ( n = 1), es una clavija a la izquierda, es decir, a la clavija izquierda.
- El disco cuatro es 1, por lo que está en otra clavija. Dado que n es impar ( n = 1), es una clavija a la izquierda, es decir, a la derecha.
- El disco cinco también es 1, por lo que se apila encima, en la clavija derecha.
- El disco seis es 0, por lo que está en otra clavija. Como n es par ( n = 2), el disco está una clavija a la derecha, es decir, a la izquierda.
- Los discos siete y ocho también son 0, por lo que se apilan encima, en la clavija izquierda.
Las clavijas de origen y destino para el m- ésimo movimiento también 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 (m & m - 1) % 3
a clavija ((m | m - 1) + 1) % 3
, donde los discos comienzan en la clavija 0 y terminan en la clavija 1 o 2 según si el número de discos es par o impar. Otra formulación es de clavija (m - (m & -m)) % 3
a clavija (m + (m & -m)) % 3
.
Además, el disco que se va a mover está determinado por el número de veces que el recuento de movimientos ( m ) se puede dividir por 2 (es decir, el número de bits cero a la derecha), contando el primer movimiento como 1 e identificando los discos por los números. 0, 1, 2, etc. en orden de tamaño creciente. Esto permite una implementación de computadora no recursiva muy rápida para encontrar las posiciones de los discos después de m movimientos sin referencia a ningún movimiento previo o distribución de discos.
La operación, que cuenta el número de ceros consecutivos al final de un número binario, da una solución simple al problema: los discos se numeran desde cero, y en el movimiento m , los ceros finales del recuento del número de disco se mueven la distancia mínima posible a la derecha (dando vueltas hacia la izquierda según sea necesario). [9]
Solución de código gris
El sistema de numeración binaria de los códigos Gray ofrece una forma alternativa de resolver el rompecabezas. En el sistema Gray, los números se expresan en una combinación binaria de 0 y 1, pero en lugar de ser un sistema numérico posicional estándar , el código Gray opera con la premisa de que cada valor difiere de su predecesor en solo un (y exactamente un) bit cambiado. .
Si uno cuenta en código Gray de un tamaño de bit igual al número de discos en una Torre de Hanoi en particular, comienza en cero y cuenta hacia arriba, entonces el bit cambiado cada movimiento corresponde al disco a mover, 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 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 dónde moverlo. Para el disco más pequeño, siempre hay dos posibilidades. Para los otros discos siempre hay una posibilidad, excepto cuando todos los discos están en la misma clavija, pero en ese caso o es el disco más pequeño el que debe moverse o el objetivo ya se ha logrado. Afortunadamente, existe una regla que dice dónde mover el disco más pequeño. Sea f la clavija inicial, 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. [10]
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 ), [11] una secuencia también conocida como función de regla , o una más que la potencia de 2 dentro del número de movimiento. En Wolfram Language , IntegerExponent[Range[2^8 - 1], 2] + 1
da movimientos para el rompecabezas de 8 discos.
Representación grafica
El juego se puede representar mediante un gráfico no dirigido , los nodos representan distribuciones de discos y los bordes representan movimientos. Para un disco, la gráfica es un triángulo:
La gráfica de dos discos son tres triángulos conectados para formar las esquinas de un triángulo más grande.
Se agrega una segunda letra para representar el disco más grande. Claramente, inicialmente no se puede mover.
El pequeño triángulo superior ahora representa las posibilidades de un movimiento con dos discos:
Los nodos en los vértices del triángulo más externo representan distribuciones con todos los discos en la misma clavija.
Para h + 1 discos, tome la gráfica de h discos y reemplace cada triángulo pequeño con la gráfica de dos discos.
Para tres discos, el gráfico es:
- llamar a las clavijas a, byc
- enumerar las posiciones del disco de izquierda a derecha en orden de tamaño creciente
Los lados del triángulo más externo representan las formas más cortas de mover una torre de una clavija a otra. El borde en el medio de los lados del triángulo más grande representa un movimiento del disco más grande. El borde en el medio de los lados de cada triángulo más pequeño siguiente representa un movimiento de cada disco más pequeño siguiente. Los lados de los triángulos más pequeños representan los movimientos del disco más pequeño.
En general, para un rompecabezas con n discos, hay 3 n nodos en el gráfico; cada nodo tiene tres bordes con respecto a otros nodos, excepto los tres nodos de esquina, que tienen dos: siempre es posible mover el disco más pequeño a una de las otras dos clavijas, y es posible mover un disco entre esas dos clavijas excepto en la situación en la que todos los discos están apilados en una clavija. Los nodos de las esquinas representan los tres casos en los que todos los discos están apilados en una clavija. El diagrama para n 1 discos + se obtiene tomando tres copias de la n -disk diagrama de cada uno en representación de todos los estados y movimientos de los discos más pequeños para una posición particular de la nueva más grande de disco y unirse a ellos en las esquinas con tres nuevos bordes, que representan las únicas tres oportunidades para mover el disco más grande. Por lo tanto, la figura resultante tiene 3 n +1 nodos y todavía le quedan tres esquinas con solo dos bordes.
A medida que se agregan más discos, la representación gráfica del juego se parecerá a una figura fractal , el triángulo de Sierpiński . Está claro que la gran mayoría de posiciones en el rompecabezas nunca se alcanzarán cuando se utilice la solución más corta posible; de hecho, si los sacerdotes de la leyenda están usando la solución más larga posible (sin volver a visitar ninguna posición), les tomará 3 64 - 1 movimientos, o más de 10 23 años.
La forma no repetitiva más larga para tres discos se puede visualizar borrando los bordes no utilizados:
Por cierto, este camino no repetitivo más largo se puede obtener prohibiendo todos los movimientos de la a a la c .
El ciclo hamiltoniano para tres discos es:
Los gráficos muestran claramente que:
- De cada distribución arbitraria de discos, existe exactamente una forma más corta de mover todos los discos a una de las tres clavijas.
- Entre cada par de distribuciones arbitrarias de discos hay una o dos rutas más cortas diferentes.
- De cada distribución arbitraria de discos, hay una o dos rutas no autocruzadas más largas diferentes para mover todos los discos a una de las tres clavijas.
- Entre cada par de distribuciones arbitrarias de discos hay uno o dos caminos diferentes más largos que no se cruzan automáticamente.
- Sea N h el número de caminos que no se cruzan automáticamente para mover una torre de h discos de una clavija a otra. Luego:
- N 1 = 2
- N h +1 = ( N h ) 2 + ( N h ) 3
Esto le da a N h 2, 12, 1872, 6563711232, ... (secuencia A125295 en la OEIS )
Variaciones
Clavijas adyacentes
Si todos los movimientos deben ser entre clavijas adyacentes (es decir, dadas las clavijas A, B, C, uno no puede moverse directamente entre las clavijas A y C), entonces mover una pila de n discos de la clavija A a la clavija C requiere 3 n - 1 movimientos. La solución utiliza las 3 n posiciones válidas, siempre tomando el movimiento único que no deshace el movimiento anterior. La posición con todos los discos en la clavija B se alcanza a la mitad, es decir, después de (3 n - 1) / 2 movimientos. [ cita requerida ]
Hanoi cíclico
En Cyclic Hanoi, se nos dan tres clavijas (A, B, C), que están dispuestas como un 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 el sentido de las agujas del reloj. [12] Basta con representar la secuencia de discos a mover. La solución se puede encontrar utilizando dos procedimientos recursivos entre sí:
Para mover n discos en sentido antihorario hasta la clavija de destino vecina:
- mover n - 1 discos en sentido antihorario hasta la clavija de destino
- mueva el disco # n un paso en el sentido de las agujas del reloj
- mover n - 1 discos en el sentido de las agujas del reloj hasta la clavija de inicio
- mueva el disco # n un paso en el sentido de las agujas del reloj
- mover n - 1 discos en sentido antihorario hasta la clavija de destino
Para mover n discos en el sentido de las agujas del reloj hasta la clavija de destino vecina:
- mueva n - 1 discos en sentido antihorario a una clavija de repuesto
- mueva el disco # n un paso en el sentido de las agujas del reloj
- mover n - 1 discos en sentido antihorario hasta la clavija de destino
Dejemos que C (n) y A (n) representen el movimiento de n discos en sentido horario y antihorario, entonces podemos escribir ambas fórmulas:
C (n) = A (n-1) n A (n-1) y A (n) = A (n-1) n C (n-1) n A (n-1).
Por tanto, C (1) = 1 y A (1) = 1 1, C (2) = 1 1 2 1 1 y A (2) = 1 1 2 1 2 1 1.
La solución para el Hanoi cíclico tiene algunas propiedades interesantes:
1) Los patrones de movimiento de transferir una torre de discos de una clavija a otra clavija son simétricos con respecto a los puntos centrales.
2) El disco más pequeño es el primer y último disco que se mueve.
3) Los grupos de movimientos de disco 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.
Con cuatro clavijas y más
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. [13]
Sin embargo, en el caso de cuatro o más clavijas, el algoritmo Frame-Stewart se conoce sin prueba de optimalidad desde 1941. [14]
Para la derivación formal del número exacto de movimientos mínimos necesarios para resolver el problema mediante la aplicación del algoritmo Frame-Stewart (y otros métodos equivalentes), consulte el artículo siguiente. [15]
Para conocer otras variantes del problema de la Torre de Hanoi de cuatro clavijas, consulte el documento de encuesta de Paul Stockmeyer. [dieciséis]
Las configuraciones de juego de las llamadas Torres de Bucarest y Torres de Klagenfurt producen códigos Gray ternarios y pentarios. [17]
Algoritmo Frame-Stewart
El algoritmo Frame-Stewart se describe a continuación:
- Dejar sea el número de discos.
- Dejar sea el número de clavijas.
- Definir para ser el número mínimo de movimientos necesarios para transferir n discos usando r clavijas.
El algoritmo se puede describir de forma recursiva:
- Para algunos , , transfiera la parte superior discos a una sola clavija que no sea la clavija de inicio o de destino, tomando se mueve.
- Sin molestar la clavija que ahora contiene la tapa discos, transfiera el resto discos a la clavija de destino, utilizando solo el resto clavijas, tomando se mueve.
- Finalmente, transfiera la parte superior discos a la clavija de destino, tomando se mueve.
Todo el proceso lleva se mueve. Por lo tanto, el recuentodeben ser recogidos para los que esta cantidad sea mínima. En el caso de 4 clavijas, el óptimo es igual a , dónde es la función entera más cercana . [18] Por ejemplo, en el curso UPenn CIS 194 sobre Haskell, la primera página de asignación [19] enumera la solución óptima para el caso de 15 discos y 4 clavijas como 129 pasos, que se obtiene para el valor anterior de k .
Se supone que este algoritmo es óptimo para cualquier número de clavijas; su número de movimientos es 2 Θ ( n 1 / ( r −2) ) (para r fijo ).
Caminos generales más cortos y el número 466/885
Una curiosa generalización del objetivo original del rompecabezas es partir de una configuración dada de los discos donde todos los discos no están necesariamente en la misma clavija y llegar en un número mínimo de movimientos a otra configuración dada. En general, puede ser bastante difícil calcular una secuencia de movimientos más corta para resolver este problema. Andreas Hinz propuso una solución basada en la observación de que en una secuencia más corta de movimientos, el disco más grande que necesita ser movido (obviamente uno puede ignorar todos los discos más grandes que ocuparán la misma clavija tanto en la inicial como en la inicial). configuraciones finales) se moverán 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 una secuencia más corta de movimientos entre dos configuraciones de disco inicial y final que se eligen al azar. Hinz y Chan Tat-Hung descubrieron independientemente [20] [21] (ver también [22] : Capítulo 1, p. 14 ) que el número promedio de movimientos en una Torre de n discos viene dado por la siguiente fórmula exacta:
Para n lo suficientemente grande , solo el primer y segundo términos no convergen a cero, por lo que obtenemos una expresión asintótica :, como . Así, intuitivamente, podríamos interpretar la fracción de como representando la proporción del trabajo que uno tiene que realizar cuando se pasa 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 de longitud "más difícil" lo que implica mover todos los discos de una clavija a otra. Romik dio 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. [23]
Hanoi magnético
En Magnetic Tower of Hanoi, cada disco tiene dos lados distintos, el norte y el sur (normalmente de color "rojo" y "azul"). Los discos no deben colocarse con los polos similares juntos; los imanes en cada disco evitan este movimiento ilegal. Además, cada disco debe voltearse a medida que se mueve.
Torres bicolores de Hanoi
Esta variación del famoso rompecabezas de la Torre de Hanoi se ofreció a los estudiantes de tercer a sexto grado en el 2ème Championnat de France des Jeux Mathématiques et Logiques, celebrado en julio de 1988. [24]
Las reglas del rompecabezas son esencialmente las mismas: los discos se transfieren entre clavijas de uno en uno. En ningún momento se puede colocar un disco más grande sobre uno más pequeño. La diferencia es que ahora para cada tamaño hay dos discos: uno negro y otro blanco. Además, ahora hay dos torres de discos de colores alternos. El objetivo del rompecabezas es hacer que las torres sean monocromáticas (del mismo color). Se supone que los discos más grandes en la parte inferior de las torres intercambian posiciones.
Torre de hanoy
Se ha adaptado una variación del rompecabezas como un juego de solitario con nueve cartas bajo el nombre de Tower of Hanoy . [25] [26] No se sabe si la alteración ortográfica del nombre original es deliberada o accidental. [27]
Aplicaciones
La Torre de Hanoi se utiliza con frecuencia en la investigación psicológica sobre resolución de problemas . También existe una variante de esta tarea denominada Torre de Londres para el diagnóstico neuropsicológico y el tratamiento de las funciones ejecutivas.
Zhang y Norman [29] utilizaron varias representaciones isomórficas (equivalentes) del juego para estudiar el impacto del efecto de representación en el diseño de tareas. Demostraron un impacto en el rendimiento del usuario al cambiar la forma en que se representan las reglas del juego, utilizando variaciones en el diseño físico de los componentes del juego. Este conocimiento ha tenido un impacto en el desarrollo del marco TURF [30] para la representación de la interacción humano-computadora .
La Torre de Hanoi también se utiliza como un esquema de rotación de copias de seguridad cuando se realizan copias de seguridad de datos informáticos en las que se utilizan varias cintas / medios.
Como se mencionó anteriormente, la Torre de Hanoi es popular para enseñar algoritmos recursivos a estudiantes principiantes de programación. Una versión pictórica de este rompecabezas está programada en el editor de emacs , al que se accede escribiendo Mx hanoi. También hay un algoritmo de muestra escrito en Prolog .
La Torre de Hanoi también es utilizada como prueba por neuropsicólogos que intentan evaluar los déficits del lóbulo frontal . [31]
En 2010, los investigadores publicaron los resultados de un experimento que encontró que la especie de hormiga Linepithema humile pudo resolver con éxito la versión de 3 discos del problema de la Torre de Hanoi a través de dinámicas no lineales y señales de feromonas. [32]
En 2014, los científicos sintetizaron nanohojas de paladio de varias capas con una estructura similar a la de la Torre de Hanoi. [28]
En la cultura popular
En la historia de ciencia ficción "Now Inhale", de Eric Frank Russell , un humano está prisionero en un planeta donde la costumbre local es hacer que el prisionero juegue un juego hasta que lo gane o lo pierda antes de su ejecución. El protagonista sabe que un barco de rescate puede tardar un año o más en llegar, por lo que elige jugar Towers of Hanoi con 64 discos. Esta historia hace referencia a la leyenda sobre los monjes budistas que jugaron hasta el fin del mundo. [33] [34] [35]
En la historia de 1966 de Doctor Who, The Celestial Toymaker , el villano homónimo obliga al Doctor a jugar un juego de 1023 movimientos de la Torre de Hanoi de diez piezas titulado The Trilogic Game con las piezas formando una forma de pirámide cuando se apilan. [34] [36]
En 2007, el concepto del problema de las Torres de Hanoi se utilizó en el profesor Layton y la caja diabólica en los rompecabezas 6, 83 y 84, pero los discos se habían cambiado a panqueques. El rompecabezas se basaba en un dilema en el que el chef de un restaurante tenía que mover una pila de panqueques de un plato a otro con los principios básicos del rompecabezas original (es decir, tres platos a los que se podían mover los panqueques, sin poder poner un panqueque más grande sobre uno más pequeño, etc.)
En la película Rise of the Planet of the Apes (2011), este rompecabezas, llamado en la película la "Torre Lucas", se utiliza como prueba para estudiar la inteligencia de los simios. [34] [37]
El rompecabezas aparece regularmente en juegos de aventuras y rompecabezas . Dado que es fácil de implementar y se reconoce fácilmente, es adecuado para usarlo como un rompecabezas en un juego gráfico más grande (por ejemplo, Star Wars: Knights of the Old Republic y Mass Effect ). [38] Algunas implementaciones usan discos rectos, pero otras disfrazan el rompecabezas de alguna otra forma. Hay una versión arcade de Sega . [39]
Una versión de 15 discos del rompecabezas aparece en el juego Sunless Sea como un candado a una tumba. El jugador tiene la opción de hacer clic en cada movimiento del rompecabezas para resolverlo, pero el juego señala que se necesitarán 32767 movimientos para completarlo. Si un jugador especialmente dedicado hace clic hasta el final del rompecabezas, se revela que completar el rompecabezas no abre la puerta.
¡En Yu-Gi-Oh! VRAINS , un grupo de piratería llamado "Caballero de Hanoi" crea una estructura llamada "Torre de Hanoi" dentro de la red de realidad virtual del mismo nombre VRAINS.
Esto se usó por primera vez como desafío en Survivor Thailand en 2002, pero en lugar de anillos, las piezas se hicieron para parecerse a un templo. Sook Jai lanzó el desafío de deshacerse de Jed a pesar de que Shii-Ann sabía muy bien cómo completar el rompecabezas. El problema aparece como parte de un desafío de recompensa en un episodio de 2011 de la versión estadounidense de la serie de televisión Survivor . Ambos jugadores ( Ozzy Lusth y Benjamin "Coach" Wade ) lucharon por entender cómo resolver el rompecabezas y son ayudados por los miembros de su tribu.
Ver también
- Patrón ABACABA
- Esquema de rotación de respaldo , una aplicación TOH
- Baguenaudier
- Recursión (informática)
Notas
- ^ Hofstadter, Douglas R. (1985). Temas metamágicos: búsqueda de la esencia de la mente y el patrón . Nueva York: Basic Books. ISBN 978-0-465-04540-2.
- ^ Cohn, Ernst M. (1963). "Un dispositivo para demostrar algunas propiedades elementales de los números enteros" . El profesor de matemáticas . Consejo Nacional de Profesores de Matemáticas. 56 (2): 84. doi : 10.5951 / MT.56.2.0084 . ISSN 0025-5769 . Consultado el 9 de marzo de 2021 .
- ^ Hinz, Andreas M .; Klavžar, Sandi; Milutinović, Uroš; Petr, Ciril (31 de enero de 2013). La torre de Hanoi: mitos y matemáticas . ISBN 978-3034802369.
- ^ Spitznagel, Edward L. (1971). Temas seleccionados en matemáticas . Holt, Rinehart y Winston. pag. 137 . ISBN 978-0-03-084693-9.
- ^ Moscovich, Ivan (2001). 1000 ideas de juego: acertijos, paradojas, ilusiones y juegos . Obrero. ISBN 978-0-7611-1826-8.
- ^ Petković, Miodrag (2009). Famosos rompecabezas de grandes matemáticos . Librería AMS. pag. 197. ISBN 978-0-8218-4814-2.
- ^ Troshkin, M. "Llega el fin del mundo: un análisis no recursivo del problema recursivo de las torres de Hanoi". Focus (en ruso). 95 (2): 10-14.
- ^ Mayer, Herbert; Perkins, Don (1984). "Torres de Hanoi revisitadas". Avisos SIGPLAN . 19 (2): 80–84. doi : 10.1145 / 948566.948573 . S2CID 2304761 .
- ^ Warren, Henry S. (2003). "Sección 5-4: Contar ceros finales". Delicia del hacker (1ª ed.). Boston MA: Addison-Wesley. ISBN 978-0-201-91465-8.
- ^ Miller, Charles D. (2000). "Cap. 4: Números binarios y el código gris estándar" . Ideas matemáticas (9 ed.). Addison Wesley Longman. ISBN 978-0-321-07607-6. Comprobar
|archive-url=
valor ( ayuda ) - ^ Gros, L. (1872). Théorie du Baguenodier . Lyon: Aimé Vingtrinier.
- ^ Gedeon, TD (1996). "Las torres cíclicas de Hanoi: una solución iterativa producida por transformación". The Computer Journal . 39 (4): 353–356. doi : 10.1093 / comjnl / 39.4.353 .
- ^ Bousch, T. (2014). "La quatrieme tour de Hanoi" (PDF) . Toro. Belg. Matemáticas. Soc. Simon Stevin . 21 : 895–912. doi : 10.36045 / bbms / 1420071861 . S2CID 14243013 . Archivado desde el original (PDF) el 21 de septiembre de 2017.
- ^ Stewart, BM; Frame, JS (marzo de 1941). "Solución al problema avanzado 3819". American Mathematical Monthly . 48 (3): 216–9. doi : 10.2307 / 2304268 . JSTOR 2304268 .
- ^ Klavzar, Sandi; Milutinovi, Uro; Petrb, Ciril (2002). "Variaciones sobre el rompecabezas de la torre de cuatro postes de Hanoi" (posdata) . Congressus Numerantium . 102 .
- ^ Stockmeyer, Paul (1994). "Variaciones sobre el rompecabezas de la torre de cuatro postes de Hanoi" (posdata) . Congressus Numerantium . 102 : 3-12.
- ^ Herter, Felix; Rote, Günter (2018-11-14) [2018-08-09, 2017-12, 2017-08-09, 2016-04-22]. "Enumeración de código gris sin bucles y la torre de Bucarest" (PDF) . Informática Teórica . Berlín, Alemania. 748 : 40–54. arXiv : 1604.06707 . doi : 10.1016 / j.tcs.2017.11.017 . ISSN 0304-3975 . S2CID 4014870 . Archivado (PDF) desde el original el 16 de diciembre de 2020 . Consultado el 16 de diciembre de 2020 . [1] (15/18/19/24 páginas)
- ^ "Universidad de Toronto CSC148 Slog" . 5 de abril de 2014 . Consultado el 22 de julio de 2015 .
- ^ "UPenn CIS 194 Introducción a Haskell Assignment 1" (PDF) . Consultado el 31 de enero de 2016 .
- ^ Hinz, A. (1989). "La Torre de Hanoi". L'Enseignement Mathématique . 35 : 289–321. doi : 10.5169 / seals-57378 .
- ^ Chan, T. (1988). "Un análisis estadístico del problema de las torres de Hanoi". Internat. J. Comput. Matemáticas . 28 (1–4): 57–65. doi : 10.1080 / 00207168908803728 .
- ^ Stewart, Ian (2004). Otro Bellas Matemáticas Me tienes .. En . Mensajero Dover. ISBN 978-0-7167-2342-4.
- ^ Romik, D. (2006). "Caminos más cortos en el gráfico de la Torre de Hanoi y autómatas finitos". Revista SIAM de Matemática Discreta . 20 (3): 610–622. arXiv : matemáticas / 0310109 . doi : 10.1137 / 050628660 . S2CID 8342396 .
- ^ Prasad Vithal Chaugule (2015). "Una solución recursiva al problema de las torres bicolores de Hanoi" (PDF) . Revista de matemáticas recreativas (4): 37–48. ISSN 2182-1976 .
- ^ Arnold, Peter (28 de mayo de 2003). Juegos de cartas para uno . Sterling Publishing Company. ISBN 978-0-600-60727-4.
- ^ Hedges, Sid G. (6 de marzo de 2018). Libro de pasatiempos de todos . Read Books Ltd. ISBN 978-1-5287-8344-6.
- ^ "Torre de la paciencia de Hanoy (también conocida como Torre de la paciencia de Hanoi)" . bbcmicro.co.uk . Consultado el 17 de octubre de 2020 .
- ^ a b Yin, Xi; Liu, Xinhong; Pan, Yung-Tin; Walsh, Kathleen A .; Yang, Hong (4 de noviembre de 2014). "Nanohojas de paladio ultrafinas multicapa tipo torre de Hanoi". Nano Letras . 14 (12): 7188–94. Código bibliográfico : 2014NanoL..14.7188Y . doi : 10.1021 / nl503879a . PMID 25369350 .
- ^ Zhang, J (1994). "Representaciones en tareas cognitivas distribuidas" (PDF) . Ciencia cognitiva . 18 : 87-122. doi : 10.1016 / 0364-0213 (94) 90021-3 .
- ^ Zhang, Jiajie; Walji, Muhammad F. (2011). "TURF: Hacia un marco unificado de usabilidad de EHR" . Revista de Informática Biomédica . 44 (6): 1056–67. doi : 10.1016 / j.jbi.2011.08.005 . PMID 21867774 .
- ^ Cervezas, SR; Rosenberg, DR; Dick, EL; Williams, T .; O'Hearn, KM; Birmaher, B .; Ryan, CM (1999). "Estudio neuropsicológico de la función del lóbulo frontal en niños sin experiencia psicotrópica con trastorno obsesivo compulsivo" . La Revista Estadounidense de Psiquiatría . 156 (5): 777–9. doi : 10.1176 / ajp.156.5.777 (inactivo 2021-01-19). PMID 10327915 .Mantenimiento de CS1: DOI inactivo a partir de enero de 2021 ( enlace )
- ^ Reid, CR; Sumpter, DJ; Beekman, M. (enero de 2011). "Optimización en un sistema natural: Hormigas argentinas resuelven las Torres de Hanoi". J. Exp. Biol . 214 (Pt 1): 50–8. CiteSeerX 10.1.1.231.9201 . doi : 10.1242 / jeb.048173 . PMID 21147968 . S2CID 18819977 .
- ^ Russell, Eric Frank (abril de 1959). "Ahora inhala" . Novelettes. Ciencia ficción asombrosa . Vol. 63 no. 2. págs. 31–77.
- Reimpreso: Russell, Eric Frank (2000). "Ahora inhala". En Katze, Rick (ed.). Ingredientes principales: las historias cortas seleccionadas de Eric Frank Russell . Framingham, Mass .: NESFA Press. págs. 399–417. ISBN 978-1-886778-10-8.
- ^ a b c Bonanome, Marianna C .; Dean, Margaret H .; Decano, Judith Putnam (2018). "Grupos auto-similares". Una muestra de grupos notables: Thompson, Self-similar, Lamplighter y Baumslag-Solitar . Libros de texto compactos en matemáticas. Cham, Suiza: Springer. pag. 96. doi : 10.1007 / 978-3-030-01978-5_3 . ISBN 978-3-030-01976-1.
- ^ Birtwistle, Graham (enero de 1985). "Las corrutinas de Hanoi". Avisos ACM SIGPLAN . 20 (1): 9-10. doi : 10.1145 / 988284.988286 . S2CID 7310661 .
- ^ "La cuarta dimensión: el fabricante de juguetes celestial" . Doctor Who . BBC One . Consultado el 2 de abril de 2021 .
- ^ Weisstein, Eric W. "Torre de Hanoi" . MathWorld . Wolfram . Consultado el 2 de abril de 2021 .
- ^ "Torre de Hanoi (concepto de videojuego)" . Giantbomb.com . Consultado el 5 de diciembre de 2010 .
- ^ "Torre de Hanoi / Andamiro" . Diversiones de Sega. Archivado desde el original el 1 de marzo de 2012 . Consultado el 26 de febrero de 2012 .
enlaces externos
- Weisstein, Eric W. "Torre de Hanoi" . MathWorld .