Iterative solution to Towers of Hanoi

When I was going through SICP, one of the early assignments was to come up with an iterative solution (rather than the traditional recursive one) to the classic Towers of Hanoi puzzle.

The first thing to understand (something I didn't before going through that chapter) is that "iterative" doesn't mean that it doesn't make use of recursive functions. A recursive solution is one that relies on the previous executions of some function; an iterative one does not. So an iterative solution can take the towers in any legal state and complete the puzzle (regardless of whether it makes recursive calls); a recursive one cannot. The challenge was to discover some local rule that would determine the next move.

It took me awhile to discover one. After examining the only other example I could find, I realize that mine is probably naive (story of my life). Nonetheless, I figured I'd post it since it does work and I would imagine may be of interest to someone else.

The rule is two-fold (Consider that the rings are numbered from smallest = 1 to largest = total count of rings):

1. Odd / even rings always travel in opposite directions. The direction each ring travels varies with the odd/even count of total rings. If you have four total rings, then:
• Odd rings: next move is always to the left (circling around to the other side when no more remain to the left).
• Even rings: next move is always to the right.
2. When deciding which piece to move next, scan the tops of each pile and move the largest ring which may legally move following the above rule.