Las Torres de Hanoi / [programa PASCAL]




La leyenda de las Torres de Hanoi es imprecisa y su origen parece incierto, pero algunos tienen por seguro que Dios, durante la creación del mundo, colocó tres varillas de diamante con 64 discos de oro dispuestos en la primera de ellas en un templo de una antigua ciudad de la India. Confió la obligación de mover los 64 discos sagrados a los monjes del templo siguiendo unas normas muy concretas y les advirtió que cuando el último disco hubiera sido movido a su posición final el mundo se acabaría.
Esta es al menos la historia que difundió el matemático Édouard Lucas, bajo el pseudónimo N. Claus de Siam (anagrama de Lucas d'Amiens) junto con el juego de las Torres de Hanoi que él mismo inventó en 1883. Su intención era puramente propagandística, una artimaña publicitaria de las que abundaban a finales del siglo XIX, pero tuvo tanto éxito que perduró.
Según la leyenda los discos únicamente podrían moverse de uno en uno. Además, nunca podría colocarse un disco sobre otro más pequeño que él y sólo podrían depositarse los discos sagrados ensartados en las varillas de diamante, jamás en otro lugar.
Con estas sencillas reglas Lucas compuso un juego matemático de gran atractivo que se convirtió con el tiempo de uno de los problemas favoritos de la matemática recreativa por su versatilidad para explicar conceptos de campos muy diversos, desde la computación a la combinatoria, pasando por otros muchos.


El juego original propuesto por Édouard Lucas constaba de 8 discos de madera y pretendía ser originario de Oriente. Se supone que había sido traído desde los territorios de la Indochina colonial francesa y fue bautizado con el nombre de “La Torre de Hanoi”, en singular. Sin embargo, con el paso del tiempo, pasó a llamarse las Torres de Hanoi, en plural, algo que sólo se puede atribuir a un efecto colateral de su popularidad: mientras se juega no es una torre sino varias las que se forman, por lo que es comprensible que la gente usara el plural. El nombre en singular, atribuido por Lucas, acabaría rindiéndose ante el clamor popular.



El programa:

El juego matemático de las Torres de Hanoi puede resolverse mediante diversos algoritmos. En el siguiente programa se calcula con un algoritmo recursivo la solución y a la vez se representan gráficamente los movimientos realizados con los discos. El número de movimientos mínimo que se deben realizar para resolver el problema con este algoritmo es de 2n – 1, siendo n el número de discos.


Ejemplo de ejecución del programa

La posición de cada disco en cada una de las 3 varillas se almacena en una matriz que se actualiza con cada movimiento. El número máximo de discos es 9 por una cuestión práctica, dado que el tiempo de resolución se incrementa exponencialmente. Además el programa permite regular la velocidad a la que se visualiza la resolución del problema.

            El código del programa completo en lenguaje Turbo PASCAL es el siguiente:


PROGRAM torres_hanoi;
{por TDM para arqui-2.blogspot.com.es (2009)}


USES CRT;


CONST ndiscosmax  = 10;
      nvarillas = 3;

      esperabase = 1440;

      cx = 10; cy = 20;

TYPE tmatriz = ARRAY [1..ndiscosmax, 1..nvarillas] OF INTEGER;

VAR

   matriz :tmatriz;

   ndiscos, velocidad, h :INTEGER;



FUNCTION valor_obligado (limiteinf, limitesup :INTEGER; texto :STRING):INTEGER;


VAR valor :INTEGER;


BEGIN

     REPEAT

           WRITE(texto);
           READLN(valor)


     UNTIL (valor > limiteinf) AND (valor < limitesup);

     valor_obligado := valor

END;



PROCEDURE introducir_datos (VAR ndiscos, velocidad :INTEGER);


BEGIN

     CLRSCR;
     TEXTCOLOR(7);

     ndiscos := valor_obligado (0, ndiscosmax, 'Introduzca el numero de discos (de 1 a 9): ');

     velocidad := valor_obligado (0, 6, 'Velocidad de ejecucion del programa (de 1 a 5): ');

END;


PROCEDURE cargarmatriz;

VAR i  :INTEGER;

BEGIN

           FOR i := 1 TO ndiscos DO

           matriz[i,1] := ndiscos-i+1;
END;



PROCEDURE intercambio (r, i, s, j :INTEGER);


BEGIN

     matriz[s,j] := matriz[r,i]+ matriz[s,j];
     matriz[r,i] := -(matriz[r,i] - matriz[s,j]);
     matriz[s,j] := matriz[s,j] - matriz[r,i]

END;


PROCEDURE dibmatriz(matrizp :tmatriz);

VAR i,j,k :INTEGER;

BEGIN

     CLRSCR;

     FOR i:=ndiscos DOWNTO 1 DO BEGIN

         FOR j:=1 TO nvarillas DO BEGIN

             IF matrizp[i,j] = 0 THEN BEGIN

                GOTOXY(cx + j*ndiscos*2, cy-i);
                TEXTCOLOR(7);
                WRITE('│')

                END

             ELSE BEGIN

                GOTOXY(cx + j*ndiscos*2 - matrizp[i,j] +1, cy-i);

                FOR k:= 1 TO matrizp[i,j]*2-1 DO BEGIN
                    TEXTCOLOR(matrizp[i,j]+1);
                    WRITE('▄')
                    END;
             END;

         END;


     END;

     GOTOXY(cx + ndiscos, cy);

     FOR k := 1 TO ndiscos*2*nvarillas +1 DO BEGIN

         TEXTCOLOR(7);
         WRITE('═')
         END;

     WRITELN;

END;




PROCEDURE mover (r,s :INTEGER);

VAR i, j :INTEGER;


BEGIN

     i:=0;

     WHILE matriz[i+1,r] <> 0 DO  {Busca el primer elemento no 0}
           i:= i+1;

     j:=1;

     WHILE matriz[j,s] <> 0 DO  {Busca el primer elemento 0}
           j:= j+1;

     intercambio(i,r,j,s);

     dibmatriz(matriz);


     DELAY(TRUNC(esperabase/velocidad))

END;




PROCEDURE hanoi (discos, a, b :INTEGER);


BEGIN

     IF discos=1 THEN mover(a,b)

     ELSE BEGIN
        hanoi(discos-1, a, 6-a-b); mover(a,b); hanoi(discos-1, 6-a-b, b)
     END;


END;




BEGIN

     CLRSCR;

     introducir_datos (ndiscos, velocidad);

     cargarmatriz;

     dibmatriz(matriz);
     DELAY(1000);


     hanoi (ndiscos,1,3);

     READKEY

END.



2 comentarios: