Resolucion del algoritmo de las Torres de Hanoi

Tecnológico Nacional de México

Instituto Tecnológico de la Laguna
División de Estudios de Posgrado e Investigación

Ivan Alejandro López Mercado

04 de Marzo 2019
División de Estudios de Posgrado
Instituto Tecnológico de La Laguna
Apartado Postal 681
Boulevard Revolución y Avenida Instituto Tecnológico de La Laguna
Torreón, Coahuila, México. C.P. 27000.

Division of Postgraduate Studies

La Laguna Institute of Technology
P.O. Box 681
Boulevard Revolucion and Avenida Instituto Tecnologico de La Laguna
Torreon, Coahuila, Mexico. C.P. 27000

1
Índice general

1. Torres de Hanoi 3

2. TIpos de Resolución 4
2.1. Metodo siemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2. Metodo de Recursividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3. Metodo Iterativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4. Metodo Matemático . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3. Desarrollo 7

4. Resultados. 8

5. Conclusiones 9

Anexos 10

A. Codigo Torres de Hanoi 11

B. Codigo Mover la pieza Menor a la izquierda 13

C. Codigo Mover la pieza Menor a la Derecha 14

D. Codigo Comparacion de vectores y cambio de valores 15

E. Codigo Ordenar Numeros de los vectores 19

2
Capítulo 1

Torres de Hanoi

El rompecabezas fue inventado por el matemático francés Édouard Lucas en 1883. Se cuenta
una historia sobre un templo en la India en Kashi Vishwanath que contiene una gran sala con tres
postes gastados por el tiempo, rodeada de 64 discos dorados. Los sacerdotes de Brahma, actuando
bajo 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 acertijo también se conoce como
el rompecabezas de la Torre de Brahma. Según la leyenda, cuando se complete el último movi-
miento del rompecabezas, el mundo se terminará. No está claro si Lucas inventó esta leyenda o si
se inspiró en ella.

Si la leyenda fuera cierta, y si los sacerdotes pudieran mover los discos a una velocidad de uno
por segundo, utilizando el menor número de movimientos, completar la tarea les llevaría 26 4 − 1
segundos, o aproximadamente 585.000 millones de años, que es aproximadamente 42 veces la
edad actual del Universo.

El juego, en su forma más tradicional, consiste en tres postes verticales. En uno de los postes
se apila un número indeterminado de discos perforados por su centro (elaborados de madera), que
determinará la complejidad de la solución. Por regla general se consideran siete discos. Los discos
se apilan sobre uno de los postes en tamaño decreciente de abajo a arriba. No hay dos discos
iguales, y todos ellos están apilados de mayor a menor radio -desde la base del poste hacia arriba-
en uno de los postes, quedando los otros dos postes vacíos. El juego consiste en pasar todos los
discos desde el poste ocupado (es decir, el que posee la torre) a uno de los otros postes vacíos. Para
realizar este objetivo, es necesario seguir tres simples reglas:
Solo se puede mover un disco cada vez y para mover otro los demás tienen que estar en postes.
Un disco de mayor tamaño no puede estar sobre uno más pequeño que él mismo. Solo se puede
desplazar el disco que se encuentre arriba en cada poste. Existen diversas formas de llegar a la
solución final, todas ellas siguiendo estrategias diversas.

3
Capítulo 2

TIpos de Resolución

La solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el núme-
ro de pasos para resolver el problema crece exponencialmente conforme aumenta el número de
discos.Como ya se ha indicado, el número mínimo de movimientos necesarios para resolver un
rompecabezas de la Torre de Hanoi es 2n − 1, donde n es la cantidad de discos.
Una manera sencilla para saber si es posible terminar el "juego.es que si la cantidad de discos
es impar la pieza inicial ira a destino y si es par a auxiliar.

2.1. Metodo siemple

Una forma de resolver el problema se fundamenta en el disco más pequeño, el de más arriba en
la varilla de origen. En un juego con un número par de discos, el movimiento inicial de la varilla
origen es hacia la varilla auxiliar. El disco 2° n− 1 se debe mover, por regla, a la varilla destino.
Luego, el disco n° 1 se mueve también a la varilla destino para que quede sobre el disco n° 2. A
continuación, se mueve el disco que sigue de la varilla origen, en este caso el disco n°3, y se coloca
en la varilla auxiliar. Finalmente, el disco n°1 regresa de la varilla destino a la origen (sin pasar por
la auxiliar), y así sucesivamente. Es decir, el truco está en el disco más pequeño.

2.2. Metodo de Recursividad

Este problema se suele plantear a menudo en programación, especialmente para explicar la
recursividad. Si numeramos los discos desde 1 hasta n, si llamamos origen a la primera pila de
discos, destino a la tercera y auxiliar a la intermedia, y si a la función la denomináramos hanoi,
con origen, auxiliar y destino como parámetros, el algoritmo de la función sería el siguiente:

4
 Figura 2.1: Recursividad

El número de movimientos mínimo a realizar para resolver el problema de este modo es de

2n ˘1,siendo n el número de discos.

2.3. Metodo Iterativo

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 solo 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, etc.

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

2.4. Metodo Matemático

Reglas matematicas de desplazamientos.
A la hora de resolver matemáticamente el problema, se producen numerosas circunstancias mate-
máticas particulares respecto a la resolución. Son las siguientes:

5
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á cada2n 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(2n ) − 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 se quiere 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, se sabe siempre qué pieza hay que mover y a qué
columna hay que desplazarla, por lo que el problema queda resuelto.

6
Capítulo 3

Desarrollo

Utilizamos el metodo iterativo, entonces se desarollo un codigo principal en el que como en-
trada se pide el numero de discos. Ese numero representa n en la formula (2n ) − 1 y llegamos al
numero de pasos deseados, entonces usamos un ciclo for desde 1 hasta el numero de pasos (ver
apendice A). En cada paso hacemos una funcion diferente, dependiendo del numero de discos si
es par o impar, recordemos que si es par en los pasos impares iremos moviendo la pieza menor se
ira moviendo hacia la torre de la derecha y en los pases impares veremos el disco que tendremos
hasta arriba, los comparamos y cambiamos el de menor valor sobre el de mayor valor( Ver apen-
dice C y D). Mientras que para el numero de discos impares, el movimiento de la pieza 1 o menor
en los pasos impares sera hacia la izquierda mientras que en los numeros pares de pasos haremos
exactamente la mismacomparacion (ver apendice B y D). Entonces el codigo realizara una serie de
n pasos, dependiendo del numero de discos y encada paso una accion diferente hasta dejar todos
los discos en la torre destino.

7
Capítulo 4

Resultados.

Como podemos ver en la figura 4.1 al final nos da el numero de pasos, que corresponde a la
formula 2n − 1 = 7, donde n es igual a 3 que son los discos.

Figura 4.1: Moivimientos realizados con 3 discos

Ademas si vemos la serie de matrices podemos observar que se cumplen las reglas, es decir
nunca queda una pieza mayor sobre una menor ademas de que solo se mueve una solo pieza en
cada movimiento.

8
Capítulo 5

Conclusiones

El metodo iterativo aunque fisicamente pueda ser facil de hacerse, el algoritmo puede ser com-
plicado o al menos muy extenso. Se dividio en funciones que utilizamos para hacer ciertas opera-
ciones en el codigo principal y asi ahorrarnos espacio o por lo menos si habia algun tipo de error
podia ser mas facil encontrarlo
Habria que intentar por otro medio de resolucion para compararlos y llegar a una conclusió sobre
cual pueda ser mas efectivo ademas de mas simple a la hora de realizarse.

9
Anexos

10
Anexos A

Codigo Torres de Hanoi

1 n = input('Introduzca el numero de discos para las Torres de hanoi: ');

2 m = zeros(n,3);
3 p = (2^n)-1;
4 d = 1:1:n;
5 m(:,1)=d;
6 disp(m)
7 s = 0;
8 cont = 0;
9 if mod(n,2) == 1
10 m(1) = 0;
11 m(3*n) = 1;
12 disp(m)
13 cont = cont + 1;
14 for k = 1 : (p-1)
15 par = mod(k,2);
16 if par == 0
17 [m,s] = mov_izq(m);
18 disp(m)
19 elseif par == 1
20 m = mov_vec(m);
21 disp(m)
22 end
23 cont = cont + 1;
24 end
25 elseif mod(n,2)== 0
26 m(1) = 0;
27 m(2*n) = 1;
28 disp(m)
29 cont = cont + 1;
30 for k = 1 : (p-1)
31 par = mod(k,2);
32 if par == 0
33 [m,s] = mov_der(m);
34 disp(m)
35 elseif par == 1
36 m = mov_vec(m);
37 disp(m)

11
38 end
39 cont = cont + 1;
40 end
41 end

12
Anexos B

Codigo Mover la pieza Menor a la izquierda

1 function [x,s] = mov_izq(M)

2 % Mover un valor igual 1 de derecha a izquierda entre una matriz de 3
3 % columnas
4 a = M(:,1);
5 b = M(:,2);
6 c = M(:,3);
7 n = length(a);
8 aux = 0;
9 for k = 1 : n
10 if a(k) == 1
11 c(1) = 1;
12 a(k) = 0;
13 aux = 3;
14 c = ordenarnum(c,2);
15 break
16 elseif b(k) == 1
17 a(1) = 1;
18 b(k) = 0;
19 aux = 1;
20 a = ordenarnum(a,2);
21 break
22 elseif c(k) == 1
23 b(1) = 1;
24 c(k) = 0;
25 aux = 2;
26 b = ordenarnum(b,2);
27 break
28 end
29 end
30
31 M(:,1) = a;
32 M(:,2) = b;
33 M(:,3) = c;
34 x = M;
35 s = aux;
36 end

13
Anexos C

Codigo Mover la pieza Menor a la Derecha

1 function [x,s] = mov_der(M)

2 % Mover un valor igual a 1 de izquierda a derecha entre una matriz de 3
3 % columnas.
4 a = M(:,1);
5 b = M(:,2);
6 c = M(:,3);
7 n = length(a);
8
9 for k = 1:n
10 if a(k) == 1 % a -> b
11 b(1) = 1;
12 a(k) = 0;
13 b = ordenarnum(b,2);
14 aux = 2;
15 break
16 elseif b(k) == 1 % b -> c
17 c(1) = 1;
18 b(k) = 0;
19 c = ordenarnum(c,2);
20 aux = 3;
21 break
22 elseif c(k) == 1 % c -> a
23 a(1) = 1;
24 c(k) = 0;
25 a = ordenarnum(a,2);
26 aux = 1;
27 break
28 end
29 end
30
31 M(:,1) = a;
32 M(:,2) = b;
33 M(:,3) = c;
34 x = M;
35 s = aux;
36 end

14
Anexos D

Codigo Comparacion de vectores y cambio

de valores

1 function x = Mov_vec(M)
2 % Comparacion de los dos vectores en los que no se encuentra
3 % la pieza mas chica (1), Toma el valor proximo de los vectores
4 % los compara e intercambia el de menor valor al otro vector.
5 a = M(:,1);
6 b = M(:,2);
7 c = M(:,3);
8 n = length(a);
9 x1 = 0;
10 x2 = 0;
11 x3 = 0;
12 s1 = 0;
13 s2 = 0;
14 s3 = 0;
15 c1 = 0;
16 c2 = 0;
17 c3 = 0;
18 for k = 1:n;
19 if a(k) == 1
20 for kk = 1:n
21 if b(kk) 6= 0
22 x2 = b(kk);
23 s2 = kk;
24 c2 = n;
25 break
26 else x2 = 0;
27 s2 = 1;
28 end
29 c2 = c2 + 1;
30 end
31 for kk = 1:n
32 if c(kk) 6= 0
33 x3 = c(kk);
34 s3 = kk;

15
35 c3 = n;
36 break
37 else x3 = 0;
38 s3 = 1;
39 end
40 c3 = c3 + 1;
41 end
42 if c2 == n && c3 == n
43 if x2 > x3 && x2 6= 0 && x3 6= 0
44 b(1) = x3;
45 c(s3) = 0;
46 b = ordenarnum(b,2);
47 break
48 elseif x2 < x3 && x2 6= 0 && x3 6= 0
49 c(1) = x2;
50 b(s2) = 0;
51 c = ordenarnum(c,2);
52 break
53 elseif x2 == 0
54 b(1) = x3;
55 c(s3) = 0;
56 b = ordenarnum(b,2);
57 elseif x3 == 0
58 c(1) = x2;
59 b(s2) = 0;
60 c = ordenarnum(c,2);
61
62 end
63 end
64 end
65 if b(k) == 1
66 for kk = 1:n
67 if a(kk) 6= 0
68 x1 = a(kk);
69 s1 = kk;
70 c1 = n;
71 break
72 else x1 = 0;
73 s1 = 1;
74 end
75 c1 = c1 + 1;
76 end
77 for kk = 1:n
78 if c(kk) 6= 0
79 x3 = c(kk);
80 s3 = kk;
81 c3 = n;
82 break
83 else x3 = 0;
84 s3 = 1;
85 end
86 c3 = c3 + 1;
87 end
88
89 if c1 == n && c3 == n

16
 90 if x1 > x3 && x1 6= 0 && x3 6= 0
91 a(1) = x3;
92 c(s3) = 0;
93 a = ordenarnum(a,2);
94 break
95 elseif x1 < x3 && x1 6= 0 && x3 6= 0
96 c(1) = x1;
97 a(s1) = 0;
98 c = ordenarnum(c,2);
99 break
100 elseif x1 == 0
101 a(1) = x3;
102 c(s3) = 0;
103 a = ordenarnum(a,2);
104 elseif x3 == 0
105 c(1) = x1;
106 a(s1) = 0;
107 c = ordenarnum(c,2);
108
109 end
110 end
111 end
112 if c(k) == 1
113 for kk = 1:n
114 if a(kk) 6= 0
115 x1 = a(kk);
116 s1 = kk;
117 c1 = n;
118 break
119 else x1 = 0;
120 s1 = 1;
121 end
122 c1 = c1 + 1;
123 end
124 for kk = 1:n
125 if b(kk) 6= 0
126 x2 = b(kk);
127 s2 = kk;
128 c2 = n;
129 break
130 else x2 = 0;
131 s2 = 1;
132 end
133 c2 = c2 + 1;
134 end
135

136 if c1 == n && c2 == n
137 if x1 > x2 && x1 6= 0 && x2 6= 0
138 a(1) = x2;
139 b(s2) = 0;
140 a = ordenarnum(a,2);
141 break
142 elseif x1 < x2 && x1 6= 0 && x2 6= 0
143 b(1) = x1;
144 a(s1) = 0;

17
145 b = ordenarnum(b,2);
146 break
147 elseif x1 == 0
148 a(1) = x2;
149 b(s2) = 0;
150 a = ordenarnum(a,2);
151 elseif x2 == 0
152 b(1) = x1;
153 a(s1) = 0;
154 b = ordenarnum(b,2);
155

156 end
157 end
158 end
159 end
160 M(:,1) = a;
161 M(:,2) = b;
162 M(:,3) = c;
163
164 x = M;
165 end

18
Anexos E

Codigo Ordenar Numeros de los vectores

1 function x = ordenarnum(y,o);
2 % ordernar de una matriz
3 % declare una matriz o vector
4 % 1 para ascendete - descenente
5 % 2 para descendente -ascendene
6 % ejemplo ordenarnum(x,1) donde x es la matriz
7 [i,j] = size (y);
8 n = i*j;
9 if o == 1
10 for kk = 0 : n
11 for k = 1 : n-1
12 if (y(k) < y(k+1))
13 aux = y(k);
14 y(k) = y(k+1);
15 y(k+1) = aux;
16 end
17 end
18 end
19 elseif o == 2
20 for kk = 0 : n
21 for k = 1 : n-1
22 if (y(k) > y(k+1))
23 aux = y(k);
24 y(k) = y(k+1);
25 y(k+1) = aux;
26 end
27 end
28 end
29 end
30 x = y;
31 end

19