Tower of Hanoi Puzzle

Introduction

Tower of Hanoi, invented by E. Lucas in 1883, is a mathematical puzzle where we have three rods and n disks. The objective is to move the entire stack to another rod, and follow some simple rules below:

1. Only one disk can be moved at a time.
2. A disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.

Strategy

Let’s assume the left rod called “source”, the middle rod called “dest”, and the right rod called “aux.” We can use a recursive solution for Tower of Hanoi. We assume that the number of moves required to solve the puzzle of n disks. First move the top disk, let’s call it disk 1, from source to dest. If there’s only one disk, then it is done. Otherwise, we should move n-1 disks from source to aux, which means that we will have moves. Next, move the nth disk from source to dest, thich means there’s one move. Finally, move n-1 disks from aux to dest, which means that we will have moves. To conclude, we have in total. Given by the recurrence relation,

We also have . Solving this gives

which is also known as the Mersenne numbers.

Implementation

Here’s how the Python code looks:

def tower_of_hanoi(n, source, dest, aux):
    # Base Case
    if n == 1:
        print(f"Move disk 1 from {source} to {dest}", end="\n")
        return
    # Move (n-1) disks from source to aux.
    tower_of_hanoi(n - 1, source, aux, dest)
    # Move nth disk from source to dest.
    print(f"Move disk {n} from {source} to {dest}", end="\n")
    # Move (n-1) disks from aux to dest.
    tower_of_hanoi(n - 1, aux, dest, source)

tower_of_hanoi(5, "source", "dest", "aux")

Here’s how the JavaScript code looks:

function tower_of_hanoi(n, source, dest, aux) {
  if (n == 1) {
    // base case of 1 disk, we know how to solve that
    document.write("Move disk 1 from " + source + " to " + dest + ".<br/>");
  } else {
    // Move (n-1) disks from source to aux.
    tower_of_hanoi(n - 1, source, aux, dest);
    // now move the last disk
    document.write("Move disk " + n  + " from " + source + " to " + dest + ".<br/>");
    // Move (n-1) disks from aux to dest.
    tower_of_hanoi(n - 1, aux, dest, source);
  }
}

Conclusion

The Tower of Hanoi puzzle is a great example of how recursion can more easily solve a problem. Recursion can be used for a variety of tasks including computations, sorting values, and quickly finding a value in a sorted list. The ability to break a problem into smaller pieces (Divide-and-conquer Algorithm) is a valuable skill for computer programming.

References

1. https://mathworld.wolfram.com/TowerofHanoi.html
2. https://www.instructables.com/Write-Code-to-Solve-the-Tower-of-Hanoi-Puzzle/