Algoritmos iterativos

Antes de buscar un algoritmo iterativo resaltemos de nuevo un detalle importante. Aunque estamos hablando de varios algoritmos, la solución óptima (la de menos movimientos, que como hemos visto antes, para n = 8 es de 255) es única. O sea, la serie de movimientos que resulta de aplicar un algoritmo (óptimo) cualquiera será siempre la misma.Una observación clave para encontrar un algoritmo iterativo es que el disco más pequeño se mueve una vez sí, una vez no.
El primer movimiento hay que hacerlo con el disco 1. Está claro que después de mover el disco 1 (en cualquier ocasión) se debe mover un disco distinto (si no queremos perder el tiempo moviendo el mismo disco varias veces). Este movimiento debe hacerse entre los dos postes que no contienen el disco 1. A continuación no nos quedan más que dos alternativas: deshacer el último movimiento, lo que no tiene sentido, o volver a mover el disco 1.
Además, cuando le toque le toque el turno a un disco distinto de 1, el movimiento estará perfectamente determinado ya que sólo intervendrán dos postes, y entre dos postes sólo hay un movimiento posible. Así que sólo puede haber duda cuando hay que mover el disco menor. Se sale de esta duda respetando una cualquiera de las siguientes reglas.

-El disco pequeño se debe mover siempre cíclicamente en el mismo sentido: hacia la derecha (de A a B, de B a C y de C a A) o hacia la izquierda (de A a C, de C a B y de B a A), según el número de discos sea par o impar respectivamente.
-El disco pequeño se debe colocar siempre, bien sobre un disco de número par, bien como único disco en el poste de destino (C) si el número de discos es impar o en el otro (B) si es par.

Teniendo en cuenta la primera regla se construye un algoritmo descubierto por Peter Buneman y Leon Levy.

1.-Si n es par, mueve el disco 1 hacia la derecha. Si es impar, muévelo hacia la izquierda.
2.-Si todos los discos están en C, fin. Si no, mueve un disco que no sea el 1 y vuelve al paso 1.

Teniendo en cuenta la segunda regla, el algoritmo podría ser el siguiente.

1.-Si es posible, lleva el disco 1 sobre un disco de número par. Si no es posible, llévalo al poste B si n es par o a C si n es impar.
2.-Si todos los discos están en C, fin. Si no, mueve un disco que no sea el 1 y vuelve al paso 1.

Para hacer este algoritmo más fácil de aplicar se pueden pintar los discos pares e impares de dos colores distintos. Incluso se puede pintar la base en tres trozos, como se ve en el dibujo (es como si los trozos de base fueran los discos n+1, n+2 y n+3).