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:
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
muy bueno
ResponderEliminarMe alegra que te haya sido de utilidad. Saludos.
ResponderEliminar