¿Es posible resolver el problema de Towers of Hanoi de forma iterativa? En caso afirmativo, ¿cómo?

Algo que desarrollé antes de aprender sobre la recursividad (1977 más o menos), especialmente porque solo tenía acceso a BASIC para hacer esto:

Comience con una torre llena. Marque los discos en orden de tamaño de 1 a N. Marque las posiciones como A, B, C (no es realmente necesario, pero es un recordatorio de que solo hay 3 posiciones). En cualquier momento, solo habrá un movimiento “correcto”. Ese movimiento correcto es:

1) No es el último disco que se movió. Por lo tanto, solo se pueden mover dos posiciones.

2) Realice el movimiento que coloca un disco impar encima de un disco par o un disco par encima de un disco impar. (ref: todos los discos están numerados del 1 al N según el tamaño)

2a) Si hay más de una opción, mueva el disco con el número más alto.

2b) Nunca ponga un par encima de par o impar encima de impar.

(Estoy escribiendo esto de memoria.) Pero básicamente, 2a y 2b y moverás la torre.

Cortesía de Wikipedia:
“Alternando entre los discos más pequeños y los siguientes, siga los pasos para el caso apropiado:
Para un número par de discos:

  • hacer el movimiento legal entre las clavijas A y B
  • hacer el movimiento legal entre las clavijas A y C
  • hacer el movimiento legal entre las clavijas B y C
  • repetir hasta completar

Para un número impar de discos:

  • hacer el movimiento legal entre las clavijas A y C
  • hacer el movimiento legal entre las clavijas A y B
  • hacer el movimiento legal entre las clavijas C y B
  • repetir hasta completar

En cada caso, se realizan un total de 2n-1 movimientos “.
Torre de Hanoi

Sí. Cualquier problema recursivo también se puede representar de forma iterativa, aunque la representación iterativa puede ser más complicada.