Python: Iterative Towers of Hanoi

This is an implementation of an iterative solution to the Towers of Hanoi Puzzle (THP).

The recursive solution to THP is very common:

• Move n-1 disks to the auxilliary peg using the destination peg.
• Move the bottommost disk.
• Move the n-1 disks on the auxilliary peg to the destination peg using the source peg.

Being recursive, this is terribly inefficient spacewise at runtime. Hence, an iterative solution.

The iterative solution goes:

• If the number of disks is odd, the topmost disk on the source peg always moves left, else it always moves right. This movement assumes a wraparound behavior.
• Make a legal move not involving the disk just moved.

Note that in either case, the algorithm still runs in O(2ⁿ) time. The iterative solution only reduces the space complexity of the algorithm.

Alternatively, the iterative solution may be stated as:

• Number the disks from 1 to n, 1 being the smallest/topmost disk. If the disk is numbered by an odd number, the disk always moves leftwards, otherwise, always rightwards.
• Alternate between moving the smallest disk and moving the other disks, keeping in mind the rule above until the all disks have been transferred to the destination peg.

This implementation follows the first form of the solution given above.

Downloads

• Download source. Source is written in Python3.