Recursive Implementation of the Towers of Hanoi Game

Today we’ll write a program that will recursively implement the Towers of Hanoi game.

If you prefer to watch the video version first, here it is:

The Rules of the Towers of Hanoi Game

What is the game all about? The rules are as follows:

There are 3 rods, let’s call them source, temp (for temporary) and target, counting from left to right.

On the source rod there are some disks. There may be any number of disks, but in our example we’ll have just 3 to keep things simple. They are stacked on top of one another in descending order, so the largest disk is at the bottom and the smallest is at the top, like in the following image:

The goal of the game is to move the tower of disks to the target rod (the one on the right). But you have to obey the following rules:

– You can move only one disk at a time.

– You can only move a disk from the top.

– You can put the disk on an empty rod or on another disk on another rod, but only if the disk you’re moving is smaller than the one you want to put it on.

The minimum number of moves necessary to move the whole tower from the source rod to the target rod can be calculated as 2 ** n – 1, where n is the number of disks.

So, if there is only one disk, you need just 2 ** 1 – 1 = 1 move. If there are two disks, you need 2 ** 2 – 1 = 3 moves.

The Case with Three Disks

In our case, with 3 disks, the minimum number of moves is 2 ** 3 – 1 = 7. Here’s how you can move the disks from source to target in 7 moves:

Implementation

As you can see we have a good candidate for a recursive function here. Our base case will be when the number of disks is equal to 0. Our recursive case is if the number of disks is greater than 0.

If you need a refresher on recursive functions, make sure to read my article about them.

And here’s the code:

def toh(n, source, temp, target): # toh stands for Towers of Hanoi
    # test base case
    if n > 0:
        # recursively move a tower of n-1 disks to temp
        toh(n - 1, source, target, temp)

        # move the largest disk from source to target
        disk = source["disks"].pop()
        print(f"moving {disk} from {source['name']} to {target['name']}")            
        target["disks"].append(disk)

        # recursively move the tower of n-1 disks from temp to target
        toh(n - 1, temp, source, target)        

source = {"disks": ["disk 1", "disk 2", "disk 3"], "name": "source"}
temp = {"disks": [], "name": "temp"}
target = {"disks": [], "name": "target"}

print("Before the game:\n")
print(f"source = {source['disks']}")
print(f"temp = {temp['disks']}")
print(f"target = {target['disks']}")
print()

toh(len(source["disks"]), source, temp, target)

print("\nAfter the game:\n")
print(f"source = {source['disks']}")
print(f"temp = {temp['disks']}")
print(f"target = {target['disks']}")

And here’s the output:

Before the game:

source = ['disk 1', 'disk 2', 'disk 3']
temp = []
target = []

moving disk 3 from source to target
moving disk 2 from source to temp
moving disk 3 from target to temp
moving disk 1 from source to target
moving disk 3 from temp to source
moving disk 2 from temp to target
moving disk 3 from source to target

After the game:

source = []
temp = []
target = ['disk 1', 'disk 2', 'disk 3']

Now you can play with the program and run it for towers consisting of more disks.