Continuación de Torres de Hanoi en Lisp...

En el post anterior planteé el problema e hice un planteamiento inicial, pero no llegué a terminarlo. En este post espero llegar a la resolución en pseudocódigo.

Dejé el tema planteando el problema para 4 discos.
Recordemos que el planteamiento de 3 discos se puede resumir así:

1. Si hay 3 discos en la torre A, conseguir mover los 2 de arriba a la torre B.
2. Una vez que estén en la torre B, mover el disco grande de la torre A a la C.
3. Para terminar mover los 2 discos de la torre B a la torre C.

Sabiendo que hay solución RECURSIVA, ¿podemos extrapolar esta solución a N discos?

Sería tanto como decir que si hay 4 discos tenemos que hacer...

1. Conseguir como podamos mover los 3 discos más pequeños a la torre B.
2. Mover el disco más grande de la torre A a la C.
3. Mover los 3 discos más pequeños de la torre B a la C

Ahora nos centramos en el problema de como mover los 3 discos más pequeños de la Torre A y colocarlos perfectamente en la Torre B. Esto antes de escribirlo voy a pensarlo...

1. Mover el más pequeño a la torre B.
2. Mover el mediano a la torre C.
3. Mover el pequeño a la C encima del mediano.
4. Mover el grande a la B.
5. Mover el pequeño a la A.
6. Mover el mediano a la B.
7. Mover el pequeño a la B.

¡Eh, para, para!
Ya veo la luz...
Resulta que el caso de 3 discos es un caso muy similar al de 4.

En ambos casos se hace lo siquiente:

1. Miramos cuantos discos hay en la Torre A. Movemos todos menos el más grande a la
   Torre C.
2. Mover el disco más grande de todos a la torre B.
   
3. Mover los otros discos a la torre B.

¡UY! Ahora veo otra cosa. Antes me he centrado en mover los discos de forma ordenada a la torre C, y en cambio en otras ocasiones tengo que mover de forma ordenada a la torre B. Sin embargo el algoritmo curiosamente es el mismo. Voy a simplificar renombrando las torres. En lugar de torre A, B y C, las llamaré torre origen, destino y auxiliar. Esto se debe a que dependiendo del movimiento general que queramos hacer las torres origen, destino y auxiliar varían.

Por lo tanto, para mover una pirámide de discos de ORIGEN a DESTINO debemos hacer lo siguiente:

1. Si hay N discos, hay que mover N-1 discos de ORIGEN a AUXILIAR.
2. El disco más grande de todos lo movemos directamente de ORIGEN a DESTINO.
3. Por último movemos los N-1 discos de AUXILIAR a DESTINO.

Ya vemos que el caso más sencillo va a ser el de 2 discos.
Luego en el de 3 discos hay que mover primero los 2 de arriba como hemos visto y luego mover el que queda.
Con 4, hay que mover los 3 de arriba (como hemos visto en la línea anterior) y por último el más grande.
Así hasta el infinito.

En el post de mañana la solución lisp.
A ver si alguien se anima y cuelga la solución en forma de comentario...

Saludos.