Tower of Hanoi

In this puzzle we have three rods and n disks of different sizes. At the beginning all disks are at the same rod in a decreasing order and the objective is to move all of them to another rod. The only constraint is we can not place a bigger disk on top of a smaller disk.

The typical solution strategy for this puzzle is to use recursion. If we want to move the nth disk to the target rod, we first need to move disks 1 through n-1 to the auxiliary rod. Once that is achieved, we can move the nth disk to the target rod. As a final step, we move disks 1 through n-1 from the auxiliary rod to the target rod.

At this point, we can disregard the nth disk, as it is already in place. With the remaining n-1 disks, we repeat the same strategy. However, we must be careful, as the starting rod for the n-1 disks has now changed, and the roles of the starting rod and the auxiliary rod are swapped.

For the base case, when there is only one disk, we can simply move it to the target rod, as it is the smallest disk in the entire stack.

              
def tower(n, source, target, auxiliary):
    if n == 1:
        # "Move disk 1 from {source} to {target}"
        move_list.append([1, source, target])
    else:
        tower(n-1, source, auxiliary, target)
        
        # "Move disk {n} from {source} to {target}"
        move_list.append([n, source, target])
        
        tower(n-1, auxiliary, target, source)  
              
            

The moves of disks have special patterns. ith disk moves 2n-i times. For instance the biggest disk will move once since 2n-n = 1. The smallest disk moves in every other time. The total number of moves is $$ \sum_{i=1}^n 2^{n-i} = 2^n -1 $$.

There is another interesting pattern. The disks are always moving on the same direction. Let's call three pegs as "A", "B" and "C". A move from "A" to "B" (resp. "B" to "A") is a clockwise (resp. counter-clockwise) move.

Disc Orientation # Moves
1 Counter-Clockwise 16
2 Clockwise 8
3 Counter-Clockwise 4
4 Clockwise 2
5 Counter-Clockwise 1

We use this observation to generate an iterative (instead of a recursive) algorithm.

        
1. Move odd disks clockwise, even disks counterclockwise.
2. Don’t move the same disk twice in a row.
3. Larger disks can't be on smaller disks.