¿Cómo hacer las torres de Hanoi

en Visual Basic?

 

Rafael Nieto Yosten

 

Debido a la gran demanda de programas que hagan las torres de Hanoi, decidí hacer esta pequeña guía(para tumbaburros), para hacer un programa que permita manejar, resolver y desplegar las torres de Hanoi en Visual Basic.

 

Primero que nada, las torres de Hanoi consisten en tres “torres” donde se supone que colocamos aros, cada aro tiene diferente tamaño.  El juego empieza teniendo todos los aros en la primer torre.  El aro mas grande esta hasta mero abajo, y el mas pequeño está hasta mero arriba.  El objetivo del juego es pasar todos los aros desde la torre que esté mas a la izquierda, hasta la torres que esté mas a la derecha.  Pero hay ciertas reglas:

 

• Solo se puede mover un aro a la vez
• Nunca, pero nunca, se puede colocar un aro mas grande sobre otro mas pequeño.

 

Ciertamente, para nuestras cabezas es difícil pensar si no tememos una imagen gráfica de que es lo que estamos hablando.  Así que lo pondré así: la manera en que nos estamos imaginando a las torres de Hanoi en Visual Basic sería mas o menos así:

 

 

Las torres las simulamos con 3 objetos line verticales.  Y los aros vienen siendo objetos shape.  La linea de abajo no es tan importante, sólo es un line horizontal para simular la base de las torres.

 

Los numeros que están dentro de cada shape no aparecen realmente en Visual Basic, se los puse yo para poder identificar a cada aro.  El aro mas pequeño le dí el numero 1, y el aro mas grande le di en numero 5.  Con esto quiero, indicar que esos cinco aros, son una matriz de controles, y el índice para el aro mas pequeño es el 1 y el índice del aro mas grande es el 5.

Así como la llevamos, debemos tener los siguientes objetos en nuestro formulario:

 

Tipo	Nombre	Descripción
Line	LineaVer(1)	La línea vertical de la primera torre
Line	LineaVer(2)	La línea vertical de la segunda torre
Line	LineaVer(3)	La línea vertical de la tercera torre
Line	LineaBase	La línea que sirve de base para las 3 torres
Shape	ShpAro(1)	El aro mas chiquito (el blanco)
Shape	ShpAro(2)	El aro que sigue en chiquito (el rojo)
Shape	ShpAro(3)	El aro verde
Shape	ShpAro(4)	El aro azul
Shape	ShpAro(5)	El aro mas grande (el amarillo)

 

 

En el formulario tenemos 5 aros representados con objetos shape.  Que información útil tenemos de cada shape?.. pues tenemos las coordenadas de la esquina superior izquierda de cada shape: las propiedades left y top nos dan estas coordenadas., pero que diablos hago con estas coordenadas?, que tal si yo quiero mover un aro de la torre 1 a la torre 2?, como sé que aro mover, y a qué coordenadas moverlo..? mas aún, cómo se si es válido hacer tal movimiento? (recuerda: las reglas del juego…).  Ok, ok, se que tienes ganas de llorar, pero no lo hagas todavía.. espera, todavía hay esperanza.

 

Mira, el chiste es este: si tratas de pensar como vas a jugar con las coordenadas de estos objetos gráficos, estas completamente perdido, pues estas lidiando directamente con el aspecto gráfico del programa, y todos sabemos que manejar una interfaz gráfica es un dolor en el trasero!.. así que para que complicarse?, la clave esta en que no tienes que concentrarte tanto en el aspecto grafico; sino que tienes que manejar el asunto de manera abstracta, y utilizar una estructura de datos que te permita fácilmente lidiar con estas torres y sus mentados aros.

 

Así que olvida completamente el formulario, y esos shapes y todo el rollo aquél.  Piensa ahora abstractamente.  Tienes 5 aros…, pero aro es demasiado concreto para una computadora.. recuerda, la computadora solo puede pensar en 0s y 1s, y tu le pides que piense en aros?.. a la compu no le vas a decir: muéveme este aro de aquí para acá: Tú eres el que tiene que sufrir!.  Entonces pues, en lugar de pensar que tienes cinco aros, tienes que pensar en los aros, como si fueran números.  El numero 1 corresponde a tu aro mas chiquito, y el numero 5 corresponde a tu aro mas grande.  Y como vas a acomodar estos cinco números en las torres?.. pues que mejor que una matriz!.. digamos, una matriz bidimensional que mida 3 x 5.  (3 torres x 5 espacios).

 

La tentación de todo mundo sería declarar la matriz de esta forma:

 

Dim torres(1 to 3, 4) as aro

 

Pero no!, recuerda, no estamos manejando aros.. sino números, asi que la manera correcta de declarar la matriz sería así:

 

Dim torres(1 to 3, 4) as integer

 

Una matriz de 2 dimensiones, es simplemente una tabla:

 

        

torres
	1	2	3
0	5	0	0
1	4	0	0
2	3	0	0
3	2	0	0
4	1	0	0

 

Los números en negrita son los índices.  Por ejemplo torres(1,0) es igual a 5, por que si vemos la columna 1, en la fila 0, hay un 5.

 

La correspondiente representación grafica de esta matriz sería así:

 

 

Esos numeritos: 0, 1, 2, 3 y 4 al nivel de cada aro son los índices para cada “posición”.

Y los números 1, 2 y 3 arriba de cada torre, son los índices de cada torre.

 

1. En la torre 1, en la posición 0, está el aro 5.
2. En la torre 1, en la posición 3, está el aro 2.
3. En la torre 2, en la posición 0, no hay aro!
4. En la torre 3, en la posición 4, tampoco hay aro!.
5. En la torre 1, en la posición 4, está el aro 1.

 

Bueno, pues esto es lo que almacenamos en la matriz torres.  Expresando los 5 enunciados anteriores ya en términos mas específicos de código diríamos:

 

1. torres(1, 0) = 5
2. torres(1, 3) = 2
3. torres(2, 0) = 0
4. torres(3, 4) = 0
5. torres(1, 4) = 1

 

Ahora, pues, nuestro código tiene que estar enfocado a manejar los números dentro de esta matriz, pero antes de empezar, sucede que necesitamos un dato mas: cuantos aros hay en cada torre. ¿por qué?, pues simple, en programación, llevar la cuenta de objetos siempre es una técnica muy recurrida pues puede servir muchas cosas, y sobre todo para la validación.  He aquí lo que podemos hacer si tenemos el dato de cuantos aros hay en cada torre:

 

• Podemos saber cuando una torre está vacía (no tiene aros).  Esto significa que, en caso de querer mover un aro a esta torre, no hay que hacer ninguna validación adicional, pues la torre no tiene ningún aro aún, por lo tanto, podemos meter ahí cualquier aro sin importar su tamaño.  También significa que, en caso de querer sacar un aro de esa torre, no podemos, pues no hay ningún aro en esa torre, y podemos informarle eso al usuario.
• Podemos saber cuál es el aro que esta a mero arriba en una torre (si es que la torre no esta vacía)
• Podemos saber cuál es el siguiente espacio disponible para colocar un aro en una torre.

 

Como no necesitamos saber cuantos aros hay en un solo una torre, sino, en cada una de las 3 torres.  Vamos a crear un pequeño arreglo que almacene la cuenta de aros para cada torre, la declaración sería así:

 

Dim nAros(1 to 3) as integer

 

Asi pues, nAros(1) me dice cuantos aros tengo en la torre 1, nAros(2) me dice cuantos aros tengo en la torre 2.. etc.  Veamos como quedarían las matrices torres y nAros, inicialmente:

 

torres
	1	2	3
0	5	0	0
1	4	0	0
2	3	0	0
3	2	0	0
4	1	0	0

 

nAros
1	2	3
5	0	0

 

En la torre 1 tenemos 5 aros, en la torre 2, 0 aros, y en la torre 3, 0 aros también.

Ok, yo dije que teniendo esta información, yo podía saber cual es el aro mas arriba en una torre y cual es el siguiente espacio disponible para colocar un aro en una torre, veamos como: supongamos que tenemos nuestros aros así:

 

 

Las información correspondiente en las matrices sería así:

 

torres
	1	2	3
0	3	4	5
1	1	0	2
2	0	0	0
3	0	0	0
4	0	0	0

 

nAros
1	2	3
2	1	2

 

Para saber cuál, aro esta a mero arriba, necesitamos saber la posición del aro mas arriba, y esta posición corresponde al numero de aros que hay en esa torre – 1.  Mas especifico:

Posición del aro mas arriba en la torre n = nAros(n) – 1

Numero del aro mas arriba de la torre n = torres(n, nAros(n) – 1)

 

Por ejemplo, el numero de aros de la torre 1 es = nAros(1) = 2, la posición del aro mas alto es la posición 1, o sea nAros(1) – 1 = 2 – 1 = 1.

 

Ahora, para saber la posición del siguiente espacio libre en una torre (el espacio que está justamente arriba del espacio ocupado por el aro mas arriba de una torre), simplemente utilizamos el numero de aros de esa torre como posición:

 

Posición del siguiente espacio disponible en la torre n = nAros(n)

Siguiente espacio disponible en la torre n = torres(n, nAros(n))

Y sí, ciertamente la siguiente posición disponible en la torre 1, es la posición 2; en la torre 2, es la posición 1, y en la torre 3, es la posición 2.

 

Ahora pues, empecemos a hacer nuestra primera operación con las matrices torres y nAros: Inicializarlas.

Necesitamos una función que nos deje a estas matrices tal y como están en la pagina 4.  Aquí esta esa función:

 

Sub InicializarTorres()

      Dim i as integer

      Erase torres

      For i = 0 to 4

            torres(0, i) = 5 – i

      Next i

      nAros(0) = 5

      nAros(1) = 0

      nAros(2) = 0

End Sub

 

Ahora, necesitamos una función que mueva un aro de una torre a otra torre.  Esta función va a tomar el aro que está mas arriba en la torre origen y lo va a colocar en la siguiente posición disponible en la torre destino.

 

Sub MoverAro(ByVal origen as Integer, ByVal destino as Integer)

torres(destino, nAros(destino)) = torres(origen, nAros(origen) – 1)

      torres(origen, nAros(origen) – 1) = 0

      nAros(origen) = nAros(origen) – 1

      nAros(destino) = nAros(destino) + 1

End Sub

 

En la primera línea, tomo el aro que esta mas arriba en la torre origen, y lo asigno a la siguiente posición disponible en la torre destino.

En la segunda línea, borro el aro que acabo de copiar de la torre origen. (si no la borro, voy a tener 2 aros repetidos, y eso no es lo que quiero).  Para borrarla, solo le asigno un 0, como no hay ningún aro que tenga el número 0, entonces ya sé que cuando vea un 0, significa que no hay ningún aro ahí.

 

En las 2 últimas líneas, actualizo mis contadores.  Al la cuenta de aros en el origen le resto 1, y a la cuenta de aros en el destino le sumo 1.  Si en la torre origen tenía 4 aros y en la torre destino tengo 1 aro, entonces después de mover el aro, en la torre origen voy a tener 3 aros y en la destino 2 aros.

 

Ahora, a esta función le falta algo: validación!. Oh Si!..  Resulta que no siempre puedo mover un aro de una torre a otra torre.  Si la torre origen no tiene aros, entonces no puedo mover nada.  Y si la torre destino tiene en su aro mas alto, un aro mas pequeño que el aro que quiero ponerle, tampoco puedo hacer el movimiento.  Así que la función ya con validación quedaría así:

 

Sub MoverAro(ByVal origen as Integer, ByVal destino as Integer)

      If nAros(origen) = 0 then Exit Sub

      If nAros(destino) <> 0 then

            If torres(destino, nAros(destino) – 1) < _

               torres(origen, nAros(origen) – 1) then

                  Exit Sub

            End If

      End If

torres(destino, nAros(destino) = torres(origen, nAros(origen) – 1)

      torres(origen, nAros(origen) – 1) = 0

      nAros(origen) = nAros(origen) – 1

      nAros(destino) = nAros(destino) + 1

End Sub

 

Bueno, ahora estarás diciendo, bueno, que bonito que se mueven los numeritos dentro de las matrices, pero ahora quiero que se vea!.. ok ok, a eso iba.  Lo que tu necesitas es una función que te permita hacer realidad tus sueños.  Bueno, mas bien, una función que acomode tus shapes (que simulan aros), en las coordenadas apropiadas de acuerdo a la información que tienes en tus matrices de torres y nAros.

 

Las coordenadas se pueden calcular fácilmente si tu conoces en que torre, en que posición, y que aro quieres colocar.

Lo que haces al calcular las coordenadas es centrar el aro en la torre.  El centro está dado por la propiedad X1 o X2 de el objeto lineaVer.. recuerdas?.

Vamos a darle un vistazo a la declaración de la función que calcula las coordenadas:

 

Private Function CalcCoord(nTorre as Integer, pos as Integer, nAro as integer) as TPoint

 

Que es ese TPoint?.. es un type que almacena las coordenadas de un punto. Aquí está la el código para la declaración del TPoint:

 

Private Type TPoint

         X as Integer

         Y as Integer

End Type

 

Esta declaración la pones arriba en el general.

Ahora si, el código para calcular la coordenada sería así:

 

Private Function CalcCoord(ByVal nTorre as Integer, ByVal pos as Integer, ByVal nAro as integer) as TPoint

 

      CalcCoord.X = lineaVer(nTorre).X1 – (shpAro(nAro).Width / 2)

      CalcCoord.Y = lineaVer(nTorre).Y2 – (pos + 1) * shpAro(1).Height

End Function

 

Para que este código funcione, tuviste que haber dibujado las líneas verticales de arriba hacia abajo.. así como lo oyes.. de arriba hacia abajo.  Así, propiedad Y1 es la coordenada superior, y la propiedad Y2 es la coordenada inferior.

 

Teniendo esta función de CalcCoord, ya podemos hacer la función que acomode nuestros aros de acuerdo a la info en las matrices.  Iteramos por la matriz, y cuando hallamos un aro, calculamos sus coordenadas, y lo movemos a esas coordenadas.  Para ya no hacer mas bla bla bla.. aquí está el código:

Sub AcomodarAros()

      Dim i, j as Integer

      Dim p as TPoint

      For i = 1 to 3

            For j = 0 to 4

                  If torres(i, j) <> 0 then

                        p = CalcCoord(i, j, torres(i, j))

                        shpAro(torres(i, j)).Move p.X, p.Y

                  End If

            Next j

      Next i

End Sub

 

Estos 2 ciclos for anidados sirven para ir iterando por toda la matriz de torres, lo que hacemos en cada iteración es buscar los aros.  Cuando encontramos un aro (o sea que torres(i, j) <> 0), entonces calculamos las coordenadas para ese aro (el numero del aro está dado por torres(i, j)) en la torre i en la posición j.  Las coordenadas quedan almacenadas en la variable p (que es un TPoint).  Lo que hacemos después es mover el shape correspondiente a las coordenadas almacenadas en p (p.X y p.Y).  El shpAro que vamos a mover está dado por torres(i, j), es por eso que utilizamos esta expresión como índice de shpAro.

 

Arrastrando los Aros con el mouse

 

Y hora que?.. los puedo escuchar como lloran. Waa waa.. , quiero que pueda arrastrar los aros de una torre a la otra torre!!!.  Bueno, ustedes lo pidieron, van a tener que escribir otro buen pedazote de código! Eh!.

 

El proceso de arrastrar un aro de una torre a otra torre consiste en los siguientes pasos:

 

1. El usuario da clic con el mouse a un aro, el programa detecta el clic y detecta en cual aro se dio clic, además, valida si se puede “agarrar” ese aro.
2. El usuario (con el botón del mouse aún aplanado), mueve el mouse.  El programa va moviendo el aro conforme el usuario mueve el mouse.
3. El usuario “suelta” el botón del mouse, el programa recibe un evento “MouseUp”, y detecta si las coordenadas donde soltó el mouse, corresponden al “bounding rectangle” de una torre.  Si así es, entonces checa si es válido soltar el aro en esa torre.  Si así es, entonces realiza el movimiento internamente en las matrices.
4. Al final, el programa refleja los cambios hechos internamente en la matriz llamando al procedimiento AcomodarAros

 

Primero, hay que definir algunas estructuras de datos que representan objetos básicos en geometría.. recuerdas el día en que te dijeron que todo eso que te metían en la escuela de geometría analítica te iba a servir para algo?, bueno si tuviste fe, pronto serás salvado., pero si no, ya puedes empezar a llorar de nuevo.

 

Bueno, primero que nada, el sistema de coordenadas de una PC está asi:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Las Y incrementan hacia abajo y disminuyen hacia arriba.  Las X funcionan igual: aumentan hacia la derecha y disminuyen hacia a la izquierda

 

Ahora, necesitamos una estructura que nos defina un rectángulo:

 

Type TRect

(left, top)

         left as Integer

         top as Integer

         right as Integer

         bottom as Integer

End Type

 

 

 

 

 

 

 

 

Las coordenadas (left, top) nos dan el punto que está en la esquina superior izquierda del rectángulo.  Las coordenadas (right, bottom) nos dan el punto que está en la esquina inferior derecha del rectángulo.

 

Por convención, se dice que un rectángulo no incluye a sus lados right y bottom.  Esto se utiliza para saber como determinar si un punto se encuentra dentro de un rectángulo.  Un punto que esté en el lado left o el lado top, o dentro de cualquiera de los 4 lados, se dice que está dentro del rectángulo.  Un punto que se encuentre sobre el lado right, o el lado bottom, se le considera fuera del rectángulo.

 

Asi que ya estamos listos para hacer una función que nos diga si un punto está dentro de un rectángulo:

Private Function IsPointInRect(ByVal p as TPoint, ByVal r as TRect) as Boolean

 

      If (p.X >= r.left and p.X < r.right and _

          p.Y >= r.top and p.Y < r.bottom) then

            IsPointInRect = True

      Else

            IsPointInRect = False

      End If

End Function

 

Esta función toma como parámetros un punto (p) y un rectángulo (r).  Y devuelve True si p está dentro de r, y False en caso de que no.

 

Antes de empezar a escribir algo de código en el MouseDown, necesitamos una función que nos diga si un aro está a mero arriba de una torre.  Por ejemplo.. el usuario hace clic al aro 3.. entonces yo quiero saber si el aro 3 está a mero arriba en una de las torres.  Tengo 3 torres, y cada torre (si no está vacía), tiene un aro a mero arriba, lo único que tengo que checar, es si esa torre es la torre que estoy buscando.

 

Aquí esta la función:

 

Private Function EstaArriba(ByVal n as Integer) as Integer

      Dim i as Integer

      For i = 1 to 3

            If nAros(i) <> 0 then

                  If torres(i, nAros(i)) = n then

                        EstaArriba = True

                        Exit Function

                  End If

            End If

      Next i

End Function

 

Esta función nos sirve porque el usuario solo debe de poder agarrar el aro que esté mas arriba en una torre, y debemos checar si el aro que se está intentando agarrar es efectivamente un aro de los que están arriba.

 

Ahora si, ya podemos empezar a escribir código para el evento MouseDown, y detectar, si el punto donde se hizo clic, está dentro del rectángulo que define a uno de nuestros shapes.

 

Necesitamos además una variable donde almacenar que aro es el que el usuario está “arrastrando”, si es que el usuario hizo clic a uno de los shapes.

Asi que declara esta variable en el general:

 

Dim aroAgarrado as Integer

 

También hay que inicializarlo a –1, por eso, agrega esta línea al Form_Load:

 

AroAgarrado = -1

 

También declara las siguientes variables en el general:

Dim offx, offy as Integer

 

 

Mas adelante explico que onda con el offx y el offy.

Ahora escribe algo de código para el MouseDown:

 

Private Sub Form_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)

 

      Dim i as Integer

Dim p as TPoint

Dim r as TRect

      p.X = X

      p.Y = Y

      For i = 1 to 5

            r.left = shpAro(i).left

            r.top = shpAro(i).top

            r.right = shpAro(i).left + shpAro(i).Width

            r.bottom = shpAro(i).top + shpAro(i).Height

            If EstaArriba(i) and IsPointInRect(p, r) then

                  aroAgarrado = i

                  offx = p.X – r.left

                  offy = p.Y – r.top

                  Exit Sub

            End If

      Next i

End Sub

 

En las primeras líneas, declaro un iterador (i), un punto (p), y un rectángulo (r), también lleno mi variable p con las coordenadas donde dio clic el usuario.

Luego empiezo un ciclo for, en este ciclo voy a checar si el usuario dio clic a uno de mis 5 shapes que simulan aros.  El for va checar aro por aro, desde el primer aro hasta el quinto aro, a ver si el punto p (el punto donde se dio clic) está dentro del rectángulo que encierra a esos aros.  Las primeras líneas dentro del ciclo for llenan los datos para el rectángulo que encierra al shape del aro (r).  Notarás que la sentencia If tiene 2 condiciones.  Una condición checa si el punto p esta dentro del rectángulo r., y la otra checa si el aro numero i es uno de los aros mas arriba en una torre.  Esto se logra llamando a las funciones que previamente escribimos: EstaArriba, y IsPointInRect.

 

Offx y offy vienen a ser mi “offset”, o sea la distancia que hay desde la esquina superior izquierda del shape, hasta el punto donde yo di clic.  Gráficamente:

 

 

 

 

 

 

 

 

 

 

 

 

Imagina que el rectángulo ese es el rectángulo de un shape de uno de los aros, también imagina que esa flechita es el mouse que está dando clic en ese punto.

Y para que necesito estos offx y offy?., pues sucede que el evento MouseMove, me da las coordenadas del mouse, pero si estoy arrastrando el shape de un aro, necesito conocer las coordenadas de la esquina superior izquierda de ese shape, y para calcularlas, simplemente le resto el offx y el offy al punto que me da el evento MouseMove.  Aquí esta el código que lo hace:

 

Private Sub Form_MouseMove(Button As Integer, Shift As Integer, X As Single, Y As Single)

 

      If aroAgarrado > 0 then

            ShpAro(aroAgarrado).Move X – offx, Y – offy

      End If

End Sub

 

Si te acuerdas, al cargar el formulario aroAgarrado vale –1, eso significa que no hay ningún aro agarrado.  Así, cuando se generen los eventos de MouseMove, éste evento no va a mover ningún aro.

Cuando el usuario “agarra” un aro, entonces aroAgarrado va a tener el numero del aro que esta arrastrando, y ciertamente, el evento MouseMove se va a encargar de ir cambiando las coordenadas del shape correspondiente.

 

Ahora, nos falta la parte mas bonita de todas… cuando suelta el aro.  ¡Ahora si!,  se que estas llorando, pero… no te preocupes, esto va paso por paso, pronto saldrá.

 

Cuando el usuario “suelta” el clic del mouse, se genera el evento MouseUp.  Es en este evento en que tienes que meter mano para ver en que torre se soltó el aro agarrado (si es que el usuario tiene agarrado un aro).

 

A la hora de soltar el aro, tenemos que checar si el usuario soltó el aro en uno de los siguientes rectángulos:

 

 

El procedimiento del MouseUp se resume en los siguientes pasos:

 

1. Primero, checar si se esta agarrando un aro, sino, salir.
2. Luego, generar una variable tipo TRect para cada uno de los rectángulos que encapsulan a cada torre.
3. Checar si las coordenadas del punto donde se “soltó” el puntero, están dentro de uno de los rectángulos.
4. Hacer el movimiento llamando a MoverAro

 

Aquí está el código mas o menos:

 

Private Sub Form_MouseUp(Button As Integer, Shift As Integer, X As Single, Y As Single)

 

Dim i as Integer

Dim p as TPoint

Dim r as TRect

     

      p.X = X

      p.Y = Y

      r.top = lineaVer(0).Y1

      r.bottom = lineaVer(0).Y2

      For i = 1 to 3

            r.left = lineaVer.X1 + (lineaVer(1).X1 – lineaVer(0).X1) * _

   (i + 0.5)

            r.right = r.left + lineaVer(1).X1 – lineaVer(0).X1

            If IsPointInRect(p, r) then

                  Call MoverAro(BuscarAro(aroAgarrado), i)

            End If

      Next i

      aroAgarrado = -1

      Call AcomodarAros

End Sub

 

En las primeras líneas declaramos un iterador (i).  Un punto (p) y un rectángulo (r).  Justo después, asignamos la X y la Y que recibimos del evento y los almacenamos en p.  Asignamos el top y el bottom, de r pues siempre tienen el mismo valor.

Luego en cada iteración de i, calculamos el left y el right de r, pues son los que cambian, dependiendo de la torre.  Para que las formulas funcionen, cada torre tiene que tener la misma distancia entre si.  Trata de echarle coco para entender las fórmulas, ya verás por qué.

 

Al final, hago que aroAgarrado sea –1, para que “suelte” el aro, y así el MouseMove no me siga arrastrando el aro.

Además, llamo la función AcomodarAros, para reflejar el cambio de la matriz interna, gráficamente.

 

AutoResolución de las torres de Hanoi

 

Okay, esto de la auto resolución si tiene su chiste, pero por favor ya deja de llorar.., la verdad esto es la parte mas fácil de todo el programa (uh, casi).

La auto resolución, es fácilmente implementada con una técnica llamada recursividad.  Aja.. si y eso con que se come?.. , bueno mas o menos significa que una función se implemente en términos de si misma…, (lee la oración anterior varias veces antes de continuar).

 

Primero que nada, vamos a ver la situación mas fácil para auto-resolver las torres de Hanoi:

 

 

Recuerda que tenemos una función que se llama MoverAro.

Si quisiéramos, resolver estas torres de Hanoi, haríamos lo siguiente (en español):

 

1.      Mover el aro blanco (el de arriba), a la segunda torre

2.      Mover el aro rojo (el de abajo), a la tercera torre

3.      Mover el aro blanco (que está en la segunda torre) a la tercera torre.

 

Ahora, expresado en código:

 

1.    Call MoverAro(1, 2)

2.    Call MoverAro(1, 3)

3.      Call MoverAro(2, 3)

 

Ahora, pasa algo, que cada llamada a MoverAro tiene números específicos, tenemos que escribir esto en términos genéricos.  Que tal si estos 2 aros estuvieran en la torre 2, y las quisiéramos mover a la torre 3?.  Es mas digamos, que origen es el numero de la torre donde están estos 2 aros, y que destino es el numero de la torre a donde queremos mover estos 2 aros.  Como expresaríamos la solución en términos de origen y destino?

 

Primero, necesitamos encontrar el numero de la torre que no sea origen, ni destino, y lo vamos a almacenar en la variable temp. Aquí el código:

 

 

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

 

Con este código, hacemos que temp sea la otra torre que no es ni origen ni destino.

 

Ahora si, ya podemos expresar la solución en términos de temp, origen y destino.

 

1.    Call MoverAro(origen, temp)

2.    Call MoverAro(origen, destino)

3.      Call MoverAro(temp, destino)

 

Entonces, ya podemos hacer un procedimiento que mueva 2 aros de una torre a otra torre:

 

Sub Mover2Aros(ByVal origen as integer, ByVal destino as integer)

 

      Dim temp as Integer

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

Call MoverAro(origen, temp)

Call MoverAro(origen, destino)

Call MoverAro(temp, destino)

End Sub

 

 

Bueno, ya tenemos código para resolver las torres de Hanoi cuando sólo hay 2 aros.

Si los dos aros estuvieran en la primera torre, llamaríamos la función de la siguiente manera:

Call Mover2Aros(1, 3)

 

Pero esto no sirve!-  vas a decir!., si yo quiero resolver las torres cuando tenga 3, 4, 5. etc. N torres!.

Por ejemplo, si tenemos la siguiente situación:

 

 

¿Cómo lo resolvemos?.. pues fácil!.  Tenemos una función que mueve 2 aros de una torre a otra torre, con esa podemos mover el aro blanco y el rojo a la torre 2, luego movemos el verde a la torre 3, y luego movemos el blanco y el rojo a la torre 3.

 

Ya expresado en código la solución quedaría así:

 

Call Mover2Aros(1, 2)

Call MoverAro(1, 3)

Call Mover2Aros(2, 3)

 

La primera línea, mueve el aro blanco y rojo, a la segunda torre; la segunda línea simplemente mueve el aro verde a la tercera torre, y la tercera línea mueve el aro blanco y rojo (que están en la segunda torre) a la tercera torre.  Y ya quedaron todos acomodados!, y siguiendo las reglas de Hanoi!.

 

Si te fijas, podrías hacer un procedimiento que mueva tres aros de una torre a otra torre:

 

Sub Mover3Aros(ByVal origen as integer, ByVal destino as integer)

Dim temp as Integer

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

Call Mover2Aros(origen, temp)

Call MoverAro(origen, destino)

Call Mover2Aros(temp, destino)

End Sub

 

Ahora, que tal si tenemos la siguiente situación:

 

 

Igualmente, podemos resolver estas torres fácilmente: Movemos los 3 aros de arriba (el blanco, el rojo y el verde) a la torre 2.  Luego agarramos el aro azul y lo movemos al tercer aro.  Luego Movemos los 3 aros que pusimos en la torre 2 (el blanco, el rojo y el verde), a la torre 3.

 

En código:

Call Mover3Aros(1, 2)

Call MoverAro(1, 3)

Call Mover3Aros(2, 3)

 

Podríamos hacer un procedimiento que mueva 4 aros de un lugar a otro:

 

Sub Mover4Aros(ByVal origen as integer, ByVal destino as integer)

      Dim temp as Integer

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

Call Mover3Aros(origen, temp)

Call MoverAro(origen, destino)

Call Mover3Aros(temp, destino)

End Sub

 

Ya para no hacer larga la historia, también podríamos hacer una función que mueva 5 aros de un lugar a otro, etc.  Si analizas un rato estas funciones, verás que Mover4Aros está implementado en términos de Mover3Aros, y Mover3Aros está implementado en términos de Mover2Aros.  Y si te fijas, el código en cada función es exactamente el mismo, sólo cambia el numero de aros que mueve la función.  Así pues, podríamos hacer una función genérica que mueva n aros.

 

La función estaría mas o menos así:

 

Sub MoverNAros(ByVal origen as integer, ByVal destino as integer, n as Integer)

      Dim temp as Integer

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

Call MoverNAros(origen, temp, n – 1)

Call MoverAro(origen, destino)

Call MoverNAros(temp, destino, n – 1)

End Sub

 

El último parámetro de esta función es n, n viene siendo el número de aros que quiero mover de un lugar a otro.  Ahora, la función MoverNAros está casi bien, sólo falta checar una condición, pues si llamamos esta función así como está, se va a seguir llamando a si misma para siempre (o bueno, hasta que se acabe la memoria del stack).  Sucede que si n = 1, entonces sólo tenemos que mover un aro!.

 

La función final está en la siguiente página.

 

Sub MoverNAros(ByVal origen as integer, ByVal destino as integer, n as Integer)

If n > 1 then

         Dim temp as Integer

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

Call MoverNAros(origen, temp, n – 1)

Call MoverAro(origen, destino)

Call MoverNAros(temp, destino, n – 1)

Else        ‘osea n = 1

      Call MoverAro(origen, destino)

End If     

End Sub

 

Ahora si, ese “If n > 1” hace que cuando n sea mayor que 1, entonces se haga la solución recursiva.  Y cuando n = 1, entonces se realiza un solo movimiento.

 

Otra cosa más, si quieres que se visualice el movimiento, y quieres contar el numero de movimientos, tienes que hacer unas modificaciones al código del procedimiento MoverAro:

 

Sub MoverAro(ByVal origen as Integer, ByVal destino as Integer)

      If nAros(origen) = 0 then Exit Sub

      If nAros(destino) <> 0 then

            If torres(destino, nAros(destino) – 1) < _

               torres(origen, nAros(origen) – 1) then

                  Exit Sub

            End If

      End If

torres(destino, nAros(destino) = torres(origen, nAros(origen) – 1)

      torres(origen, nAros(origen) – 1) = 0

      nAros(origen) = nAros(origen) – 1

      nAros(destino) = nAros(destino) + 1

      cuentaMov = cuentaMov + 1

      Call AcomodarAros

End Sub

 

cuentaMov es una variable que declaras en el general, y ahí llevas la cuenta de los movimientos.

La llamada a AcomodarAros sirve para desplegar el movimiento gráficamente (como se cambia la matriz internamente, entonces AcomodarAros lo refleja visualmente).

Es probable que la auto-solución se vea medio rápida, para hacer que se vea mas lenta, sólo agrega un “delay”.. osea un ciclo For que cuente del 1 al 1000000 o más, para tener a la maquina trabajando un rato.  Este ciclo For lo pondrías también dentro de la función MoverAro.

 

Oooo (¡_!) ooo0

 

Bueno, al parecer eso es todo por esta vez! Que te diviertas mucho! bugs y comentarios a Rafa:

 

Correo Electrónico:

rafanieto@hotmail.com

Hasta la próxima!.