Torres de Hanói

Torres de Hanói
Torres de Hanói.
Etapas de la resolución del problema con 4 discos.

Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.[1] Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. 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 algoritmos.

Contenido

Descripción

El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas 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.

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

Se cuenta que un templo de Benarés (Uttar Pradesh, India), se encontraba una cúpula que señalaba el centro del mundo. Allí estaba una bandeja sobre la cual existían tres agujas de diamante. En una mañana lluviosa, un rey mandó a poner 64 discos de oro, siendo ordenados por tamaño: el mayor en la base de la bandeja y el menor arriba de todos los discos.Tras la colocación, los sacerdotes del templo intentaron mover los discos entre las agujas, según las leyes que se les habían entregado: "El sacerdote de turno no debe mover más de un disco a la vez, y no puede situar un disco de mayor diámetro encima de otro de menor diámetro". Hoy no existe tal templo, pero el juego aún perduró en el tiempo...

Otra leyenda cuenta que Dios al crear el mundo, colocó tres varillas de diamante con 64 discos en la primera. También creó un monasterio con monjes, los cuales tienen la tarea de resolver esta Torre de Hanói divina. El día que estos monjes consigan terminar el juego, el mundo acabará. No obstante, esta leyenda resultó ser un invento publicitario del creador del juego, el matemático Éduard Lucas. En aquella época, era muy común encontrar matemáticos ganándose la vida de forma itinerante con juegos de su invención, de la misma forma que los juglares hacían con su música. No obstante, la falacia resultó ser tan efectista y tan bonita, que ha perdurado hasta nuestros días. Además, invita a realizarse la pregunta: "si la leyenda fuera cierta, ¿cuándo será el fin del mundo?".

El mínimo número de movimientos que se necesita para resolver este problema es de 264-1. Si los monjes hicieran un movimiento por segundo, los 64 discos estarían en la tercera varilla en algo menos de 585 mil millones de años. Como comparación para ver la magnitud de esta cifra, la Tierra tiene como 5 mil millones de años, y el Universo entre 15 y 20 mil millones de años de antigüedad, sólo una pequeña fracción de esa cifra.

Resolución

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 algunas 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.

Solución simple

Una forma de resolver la colocación de la torre es fundamentá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:

  1. Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.
  2. Si no: hanoi({0...n-1},destino, auxiliar)     //mover todas las fichas menos la más grande (n) a la varilla auxiliar
  3. mover disco n a destino                //mover la ficha grande hasta la varilla final
  4. hanoi (auxiliar, origen, destino)          //mover todas las fichas restantes, {0...n-1}, encima de la ficha grande (n)
  5. terminar

C++

[cita requerida]

/*
{Pre: discos > 1 ^ discos = número de discos ^ ini,dest,aux = caracteres que identifiquen las torres}
{Post: Se escribe por el canal estándar de salida los movimientos a realizar, indicados a partir de
los caracteres que identifican las torres, para llevar todos los discos desde la torre inicial
a la de destino}
*/
void hanoi(int discos, char ini, char dest, char aux) {
    if (discos == 1) cout << ini << " --> " << dest << endl;
    else {
        hanoi(discos - 1, ini, aux, dest);
        cout << ini << " --> " << dest << endl;
        hanoi(discos - 1, aux, dest, ini);
    }
}
 
/*
Ejemplo de función que llama automáticamente a hanoi(int, char, char, char) solo dándole el número de discos
{Pre: discos > 1}
{Post: Se escribe por el canal estándar de salida los movimientos a realizar para llevar todos los discos
desde la torre de inicio hasta la de destino. Las torres serán identificadascomo M A V siendo la inicial M
y la de destino V}
*/
void hanoi(int discos) {
    hanoi(discos, 'M', 'A', 'V');
}

C#

[cita requerida]

using System;
using System.IO;
 
namespace TorresHanoi
{
    public class Hanoi
    {
 
        public static void Main(string[] args)
        {         
            int n;            
 
            Console.Write("Escriba el número de discos en la torre de hanoi: ");
            n = Leer.datoInt();
 
            {
                Console.Write("Error, reescriba el número de discos en la torre: ");
                n = Leer.datoInt();
            }
 
        }
 
        public static void algoritmoHanoi(int n, String from, String temp, String to) 
        {
            if (n == 0) return;
            algoritmoHanoi(n-1, from, to, temp);
            System.Console.WriteLine("Mover disco " + n + " de " + from + " a " + to);
            algoritmoHanoi(n-1, temp, from, to);
        } 
    }
 
    public class Leer
    {
        public static int datoInt()
        {
            string dato;
            dato = System.Console.ReadLine();
            return int.Parse(dato);
        }
    }
}

Java

[cita requerida]

import java.util.*;
 
public class Hanoi {
 
        public static void main(String args[]){
                int n;
                Scanner sc=new Scanner(System.in);
 
                System.out.print("Escriba el número de discos en la torre de hanoi: ");
                n=sc.nextInt();
                while(n<0){
                        System.out.print("Error, reescriba el número de discos en la torre: ");
                        n=sc.nextInt();
                }
 
                algoritmoHanoi(n,"Primera Torre","Segunda Torre","Tercera Torre");
        }
 
    public static void algoritmoHanoi(int n, String from, String temp, String to) {
        if (n == 0) return;
        algoritmoHanoi(n-1, from, to, temp);
        System.out.println("Mover disco " + n + " de " + from + " a " + to);
        algoritmoHanoi(n-1, temp, from, to);
    }
 
 
}

Prolog

[cita requerida]

%Hanoi usando recursividad en lenguaje Prolog
 
hanoi(N):- move(N,'A','C','B').
 
move(0,_,_,_):-!.
 
move(N, Src, Dest, Spare):- M is N-1, move(M, Src, Spare, Dest), primitive(Src, Dest), move(M, Spare, Dest, Src).
 
primitive(X, Y):- writelist([mueve, un, disco, desde, X, hasta, Y]), nl.
 
writelist([]).
 
writelist([H|T]):- write(H), write(' '), writelist(T).
 
%

Ensamblador

[cita requerida]

;Realizado por Javier Muñoz y Wilson Moreno
;Hanoi usando recursividad en lenguaje Ensamblador
;Se supone una correcta implementacion del proc Imprimir tal que imprima:
;[BP].Inicio "->" [BP].Destino
;Juéguesela como pueda para imprimirlo, lo importante es el proc Hanoi
;El llamado sería     
        ;Mov Ax, 3;en ax esta la cantidad de discos
        ;Mov Bx, 'I';El inicio se representa con I
        ;Mov Cx, 'D';El destino se representa con D
        ;Mov Dx, 'A';El aux se representa con A
        ;Los valores se ingresan en orden inverso a como estan en el struc
        ;el primero que se mete en la pila es el ultimo que esta declarado en el struc
        ;Push Ax      ;Meto la cantidad de discos
        ;Push bx;Meto el inicio "letra I"
        ;push cx;Meto el destino "letra D"
        ;push dx      ;Meto el aux "letra A"
        ;Call Hanoi
 
 
;Struc que utiliza la estructura de la pila
     Param Struc
        BPViejo Dw ?
        DirRet  DW ?
        Aux     Dw ?              
        Destino Dw ?
        Inicio  Dw ? 
        Discos  Dw ?  
     Param Ends
 
;AQUI ESTÁ EL CÓDIGO
     Hanoi Proc Near
        Push BP;
        Mov BP,SP           
        ;Recupero en los registros los valores en el orden 
        ;que le había asignado antes de meterlos en la pila
        Mov Ax, [BP].Discos
        Mov BX,[BP].Inicio
        Mov Cx,[BP].Destino
        Mov Dx,[BP].aux
 
        Cmp Ax,1;Si la cantidad de discos = 1
        JE parada;Voy a la condicion de parada
 
        Dec Ax        ;Primero decremento la cantidad de discos en 1
        ;Ahora voy a llamarlo con los parametros en diferente orden
        Push Ax;Primero la cantidad de discos (discos-1)
        Push bx;Despues la variable correspondiente a inicio
        Push dx;Despues la variable correspondiente a aux
        Push cx;;Despues la variable correspondiente a destino
        Call Hanoi;Llamo al algoritmo con el nuevo orden
        Call imprimir ; cout << ini << " --> " << dest << endl;
 
        ;Saco todos los valores de la pila
        Pop cx
        Pop dx
        pop bx
        pop ax
 
    ;Ahora voy a llamarlo con los parametros en diferente orden
        Push Ax; YA ESTABA DECREMENTADO DESDE EL LLAMADO ANTERIOR 
        Push Dx;Despues la variable correspondiente a aux
        Push Cx;Despues la variable correspondiente a destino
        Push BX;Despues la variable correspondiente a inicio
        Call Hanoi;Llamo a Hanoi con el nuevo orden
 
        ;saco todos los valores de la pila
        Pop bx
        Pop cx
        pop dx
        pop ax
        ;Termina el algoritmo después del segundo llamado
    Jmp Salir
 
Parada:   
        call imprimir
Salir:  
;Cuando llega a este punto, la pila tiene el siguiente orden (inverso al struc)
        ;     |Discos AX      |
        ;     |Inicio BX      |
        ;     |Destino CX     |
        ;     |Aux DX         |
        ;     |DirRet         |
        ;     |BPViejo        | <- Tope
;Al sacar el BP viejo, tengo la direccion de retorno de donde "venia"
        Pop BP        ;Saco BPViejo del tope de la pila
        Ret;Regreso de donde venia
Hanoi EndP

Batch

[cita requerida]

@echo off
setlocal enabledelayedexpansion
:::::::::::::::::::::::::::::::::::::::::
::Script Para Resolver Torres de Hanoi.::
::Creado por Hugo Guerrero (Guerrerohgp):
:::::::::::::::::::::::::::::::::::::::::
::::::::::::::::::::::::::::::::
::Script to solve Hanoi Towers::
::   Created By Guerrerohgp   ::
::           2011             ::
::::::::::::::::::::::::::::::::
:ini
        set/p "cantidad=Ingrese el numero de discos en la torre: "
        if not defined cantidad goto:ini
        if !cantidad! lss 0 goto:ini
        call:algoritmoHanoi !cantidad! Torre_1 Torre_2 Torre_3
        pause>nul
exit
 
 
 
:algoritmoHanoi
        setlocal
                if "%1" equ "0" goto:eof
                set/a "cnt=%1-1"
                call:algoritmoHanoi !cnt! % class="re2">2 %4 %3
                echo.Mover disco %1 de %2 a %4
                call:algoritmoHanoi !cnt! % class="re2">3 %2 %4
        endlocal
goto:eof

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,


Una forma equivalente de resolverlo es la siguiente: coloreando los discos pares de un color y los impares de otro; se resuelve el problema añadiendo la siguiente regla: no colocar dos discos del mismo color juntos. De esta manera sólo queda un movimiento posible (además del de volver hacia atrás).

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, 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 queremos 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, sabemos siempre qué pieza hay que mover y a qué columna hay que desplazarla, luego el problema está resuelto.

Referencias

  1. Walter William Rouse Ball, Harold Scott Macdonald Coxeter, (1987), «Mathematical recreations and essays»,Dover Publications, ISBN 0-486-25357-0

Véase también

  • Recursividad
  • Exponencial

Enlaces externos


Wikimedia foundation. 2010.

См. также в других словарях:

  • Torres de Hanoi — Las Torres de Hanoi es un juego cuyos elementos son 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… …   Enciclopedia Universal

  • Hanói — Torre de la Tortuga …   Wikipedia Español

  • Anexo:Torres gemelas — Torres Petronas, las torres gemelas más altas del mundo. Las llamadas torres gemelas son edificios o estructuras que poseen un diseño similar e idénticas características. En esta lista se exponen las torres gemelas más altas del mundo a partir de …   Wikipedia Español

  • Keangnam Hanoi Landmark Tower — es un rascacielos que se está construyendo en el bulevar Pham Hung, perteneciente al distrito Cau Giay de Hanoi, Vietnam. Esta zona se reserva para las oficinas centrales de grandes corporaciones como Agribank y VNPT. La torre es parte de un… …   Wikipedia Español

  • Ecuación recurrente — Saltar a navegación, búsqueda En matemática, una relación de recurrencia es una ecuación que define una secuencia recursiva; cada término de la secuencia es definido como una función de términos anteriores. Contenido 1 Definición 2 Resolución 2.1 …   Wikipedia Español

  • Édouard Lucas — François Édouard Anatole Lucas (Amiens, 4 de abril de 1842 París, 3 de octubre de 1891) fue un reconocido matemático francés. Trabajó en el observatorio de París y más tarde fue profesor de matemáticas en la capital del Sena. Se le conoce sobre… …   Wikipedia Español

  • Matemática recreativa — La matemática recreativa es un área de las matemáticas que se concentra en la obtención de resultados acerca de actividades lúdicas, y también la que se dedica a difundir o divulgar de manera entretenida y divertida los conocimientos o ideas o… …   Wikipedia Español

  • 1810 (reality show) — 1810 Harán historia Título original 1810 Licencia original Canal 13 Género Reality show País …   Wikipedia Español

  • Algoritmo divide y vencerás — En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución… …   Wikipedia Español

  • Código Gray — de dos bits 00 01 11 10 Código Gray de tres bits 000 001 011 010 110 111 101 100 Código Gray de cuatro bits 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 El código binario reflejado o código Gray, nombrado así en …   Wikipedia Español


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»