Towers of Hanoi is a simple programming riddle often used in programming courses to introduce recursion. Not many people are aware that Towers of Hanoi has also a beautiful iterative solution.
Here I assume that you already know this problem if not please check Wikipedia Tower of Hanoi page.
The key to discover how iterative algorithm work is to actually observe how
disks are moved by recursive algorithm.
To make move patterns more visible we will put rots
on a circle, we will be moving discs from rot marked by FROM label to
rot marked by TO label using third rot only to temporary store discs.
We will use animation below to
observe how disks move. We will start by observing how the smallest disk (red)
is moving when total number of disk is even (so try it for 2, 4, 6 and 8 disks).
After you find the pattern how smallest disk moves try to find out how other
disk are moving - this should not be difficult.
Then repeat observation for odd number of disks (1,3,5 and 7).
TIP: Patterns may be more easily revealed when you use x3 or x5 animation speed
Scroll below when you have enough of pattern finding or if want to check if your patterns are correct.
For any number of disks we start by moving the smallest disk. For even total number of disks we move the smallest disk clockwise for odd total number of disks we move the smallest disk counterclockwise. After every move that involves the smallest disk we perform one valid move (we move smaller disk on top of bigger, or we move disk to empty rod) that doesn’t involve the smallest disk. We stop when all disks were moved to TO rod.
Formal proof that above algorithm works can be found in The Associativity of Equivalence and the Towers of Hanoi Problem.