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.

Learn how to make beautiful GUI apps

in Python using the Kivy framework.

Comprehensive, for Kivy beginners, easy to follow.

Get the book here (PDF) or on Amazon:

ebook / paperback (black and white) / paperback (full color)

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:

Here we have a tower of 3 disks, but there is a general rule that applies to any tower with any number of disks:  

If the tower consists of n disks, we should move a tower of n-1 disks (so all the disks except the largest one at the bottom) from source to temp. This leaves us with the largest ring on the source rod.  

Then we move the largest disk to the target rod.  

Finally we have to move the tower of n-1 disks from temp to target.

Your Panda3D Magazine

Make Awesome Games and Other 3D Apps

with Panda3D and Blender using Python.

Cool stuff, easy to follow articles.

Get the magazine here (PDF).

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.

Python Jumpstart Course

Learn the basics of Python, including OOP.

with lots of exercises, easy to follow

The course is available on Udemy.

Blender Jumpstart Course

Learn the basics of 3D modeling in Blender.

step-by-step, easy to follow, visually rich

The course is available on Udemy and on Skillshare.