code python tour hanoi

• Python Course
• Python Basics
• Interview Questions
• Python Quiz
• Popular Packages
• Python Projects
• Practice Python
• AI With Python
• Learn Python3
• Python Automation
• Python Web Dev
• DSA with Python
• Python OOPs
• Dictionaries

Python Program for Tower of Hanoi

The Tower of Hanoi is a classic mathematical puzzle that involves moving a set of disks from one rod to another, adhering to specific rules. In this Python program, we’ll explore how to solve the Tower of Hanoi using recursion, a fundamental programming technique that allows us to break down this complex problem into simpler, manageable sub-problems. The program will demonstrate the sequence of moves required to transfer the disks between the rods efficiently, providing a clear example of recursive problem-solving in action. This educational example not only enhances understanding of recursion but also offers insight into algorithmic thinking for solving puzzles.

What are the rules of the Tower of Hanoi?

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 

• Only one disk can be moved at a time. 
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack. 
• No disk may be placed on top of a smaller disk.

Note : Transferring the top n-1 disks from the source rod to the Auxiliary rod can again be thought of as a fresh problem and can be solved in the same manner. 

Tower of Hanoi Using Recursion

The function recursively breaks down the problem of moving n disks into smaller problems of moving n-1 disks. It alternates the roles of the rods (source, destination, auxiliary) in each recursive call to facilitate the step-by-step transfer of disks according to the rules of the Tower of Hanoi puzzle. The rules are that you can only move one disk at a time and a larger disk may not be placed on top of a smaller disk.

Time Complexity: O(2 n ) Auxiliary Space: O(n)

Practice Tower of Hanoi Problem Yourself

Please Login to comment...

Similar reads.

• Python Programs
• Python DSA-exercises
• PS5 Pro Launched: Controller, Price, Specs & Features, How to Pre-Order, and More
• How to Make Money on Twitch
• How to activate Twitch on smart TV
• 105 Funny Things to Do to Make Someone Laugh
• #geekstreak2024 – 21 Days POTD Challenge Powered By Deutsche Bank

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Tower of Hanoi in Python: Complete Step-by-Step

Tower of Hanoi is a mathematical problem (puzzle) that consists of 3 poles and ‘n’ number of discs, each disc having different diameters.

The Objective of the Tower of Hanoi Problem

The objective or goal of this problem is to transfer all the ‘n’ discs from source pole to the destination pole in such a way that we get the same arrangement of discs as before. But this goal must be achieved by sticking to the rules.

Rules and Constraints

The constraints that must be satisfied while solving the problem are –

• Only one disc can be moved at a time.
• Only the top-most disc can be removed
• The larger disc cannot be placed on top of the smaller disc.

Visual Representation of the Tower of Hanoi problem

The following picture shows the step-wise solution for a tower of Hanoi with 3 poles (source, intermediate, destination) and 3 discs. The goal is to move all the 3 discs from pole A to pole C.

As we can see from the above solution, the number of moves needed for 3 discs = 8. So, a generalized formula for a total number of moves we need is:

Total number of moves = n 2  – 1

Where ‘n’ is the total no. of discs.

Solving the Tower of Hanoi Problem in Python

In the above code, we call our function TowerOfHanoi recursively for 3 discs.

• s_pole: source pole
• i_pole: intermediate pole
• d_pole: destination pole

The output of the above code is:

So , this is how we solve the problem of Tower of Hanoi.

This code can be generalized for any number of discs. So if you want the solution for 4 discs, just change the value of n from 3 to 4 as n = 4, and the output will be displayed for 4 discs and so on.

• Online Python Compiler
• Hello World
• Console Operations
• Conditional Statements
• Loop Statements
• Builtin Functions
• Type Conversion

Collections

• Classes and Objects
• File Operations
• Global Variables
• Regular Expressions
• Multi-threading
• phonenumbers
• Breadcrumbs
• ► Python Examples
• ► ► Python Programs
• ► ► ► Tower of Hanoi Program
• Python Programs
• Python Basic Programs
• Python Sorting Programs
• Basic Programs
• Python - Add two numbers
• Python - Arrange given numbers to form a maximum number
• Python - Arrange given numbers to form a minimum number
• Python - Average of two numbers
• Python - Calculator program
• Python - Check if number is Armstrong
• Python - Check if number is even
• Python - Check if number is odd
• Python - Check if number is prime number
• Python - Check if number is positive or negative
• Python - Check if two numbers are equal
• Python - Fibonacci series using For-Loop
• Python - Fibonacci series using recursion
• Python - Find all factors of a number
• Python - Find area of circle
• Python - Find area of rectangle
• Python - Find area of square
• Python - Find factorial of a number
• Python - Find factorial of a number using recursion
• Python - Find if given year is Leap Year in Georgian calendar
• Python - Find maximum of two numbers
• Python - Find minimum of two numbers
• Python - Find Nth Fibonacci number
• Python - Find roots of a quadratic equation
• Python - Get unique digits in a number
• Python - Largest of three numbers
• Python - Matrix Transpose
• Python - Matrix Addition
• Python - Palindrome program
• Python - Pangram string
• Python - Print from A to Z
• Python - Print numbers 123..N
• Python - Print prime numbers between two given numbers
• Python - Reverse a number
• Python - Round a floating number to specific decimal places
• Python - Round a floating number to nearest integer
• Python - Smallest of three numbers
• Python - Star pattern programs
• Python - Sum of two numbers
• Python - Sum of first N natural numbers
• Python - Sum of cubes of first N natural numbers
• Python - Sum of squares of first N natural numbers
• Python - Swap two numbers
• Python - Tower of Hanoi
• Sorting Programs
• Python Bubble Sort Program
• Python Selection Sort Program
• Python Insertion Sort Program
• Python Merge Sort Program
• Python Quick Sort Program
• Python Heap Sort Program
• Character related programs
• Python - Get ASCII value of a character
• Python - Check if given character is vowel or consonant
• Python - Check if a given character is alphabet or not
• Other Programs
• Get Python version

Tower of Hanoi Program

Python program – tower of hanoi.

The Tower of Hanoi is a classic puzzle game consisting of three pegs and a number of disks of different sizes, which can slide onto any peg.

The puzzle starts with the disks in a neat stack in ascending order of size on one peg, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another peg.

And the movement of disks between the pegs must obey the following simple rules:

• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty peg.
• No disk may be placed on top of a smaller disk.

The puzzle is commonly used in computer science and programming as an example of a recursive function.

Tower of Hanoi Program using Recursion

In the following program, we will use recursion technique to solve the Tower of Hanoi problem.

tower_of_hanoi() function has four parameters.

• n – the number of disks.
• from_rod – The rod which has all the disks at the start.
• to_rod – The rod to which all the disks has to be moved.
• aux_rod – The auxiliary rod which can be used to place the disks temporarily.

Python Program

In this tutorial, we learned how to solve the problem of Tower of Hanoi using recursion, with examples.

Tower of Hanoi Implementation in Python

Hello coders!! In this article, we will explore and learn the coding of the game Tower of Hanoi in python. At first, we will learn about the game rules and then see the step by step implementation of the game in python. Without wasting any time, let’s dig into it.

What is the Tower of Hanoi in Python?

It is a mathematical puzzle game in which we use three identical rods and n disks, all of the different sizes. The discs are arranged in the first rod, such that the largest disc is placed at the bottom and the smallest at the top. To solve the puzzle, one needs to arrange the disc in the same order in the last rod via the middle rod.

Rules of Tower of Hanoi in Python:

• We can move only one disc at any given time
• Only the disc which is at the top can be moved and placed ontop at any other rod
• A disc can be placed on top of a bigger disc only

An illustration of the Game:

Let us consider that initially there are 3 discs arranged as follows:

At first, we will move the disc from A to C

Now, we will move the disc from A to B

Next, we will move the disc of rod C to B

After this, we will move the disc from A to C

Now, move the disc from B to A

Next, we need to move the disc of rod B to C

And for the last step, we will move the disc form A to C , thus solving the puzzle

Implementation of Tower of Hanoi in Python:

Explanation:

• Here, we have used recursive method for the implementation of the game
• Number of discs
• Auxiliary rod
• Destination rod
• It first checks the condition if the number of disc is 1, it directly moves it to the Destination rod and terminates the function
• Then, we have recursively called the function to move the remaining n-1 discs from source node to the auxiliary node, using the destination rod as the auxiliary
• After that, the 1 disk that is remaining is directly moved from the source rod to the auxiliary rod
• Lastly, we have again recursively called the the function to move the remaining n-1 rods from the auxiliary rod to the destination rod, using the source node as auxiliary

Is it possible to solve Tower Of Hanoi without recursion?

This question can pop into anyone’s mind. Well, it is definitely possible. The tower of Hanoi problem can be solved non recursively as well by a binary solution approach where the n number of discs is encoded and represented in binary form of numbers 0 – 2^n.

Time complexity for the recursive solution:

The time complexity for the recursive solution of Tower of Hanoi is O(2^n) , where n is the number of discs.

• Best Career Options With Python
• Rock Paper Scissors Game Development in Python
• Understanding Strand Sort in Python With Example

Conclusion:

In this article, we learned in detail about the game of Tower of Hanoi and learned its recursive implementation in Python. We also elaborated the game concept in detail and finally saw an easy python code to implement it.

However, if you have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.

Happy Pythoning!

Therre is an error. You can’t moving the third disk on the rod C because there’re already the other disks

Hi, thank you for pointing it out. Seems like there was a minor mistake in the code.

I’ve updated the code with correct logic and better name convention. Hope it helps!

Moves 1 to 7: A to C, A to B, C to B, A to C, B to A, B to C and A to C. This is not what the program returns

How to Solve Tower of Hanoi Probelem in Python

• Python How-To's
• How to Solve Tower of Hanoi Probelem in …

The Tower of Hanoi problem is a fundamental mathematical puzzle that is introduced to new programmers at the start for them to amplify their problem-solving quiz.

The problem is simple, involving three rods. One rod contains several disks in decreasing order, with the largest disk at the bottom and the smallest at the top. We have to transfer this from rod one to rod three using the second rod.

We have to keep certain rules in mind. We can move only one disk simultaneously and have to take the disk at the top of the rod. Also, we cannot place a larger disk on top of a smaller disk. Keeping all this in mind, we have to solve this problem and calculate the total number of moves taken to solve it.

In this tutorial, we will introduce how to solve this problem. We will use a recursive method to solve the Tower of Hanoi problem in Python.

This method will create a function that will call itself recursively based on some conditions to solve the Tower of Hanoi problem. We implement the logic for this in the following code.

In the above example, we move three disks from Rod A to Rod B using Rod C.

As you can see, the total number of moves taken in the above example is 7. For n number of disks, the total moves taken using this method are always equal to 2^n -1.

Over time, a few other solutions have emerged to solve the Tower of Hanoi problem using stacks. Still, it is not recommended to use them because such methods are very inefficient in time taken and speed.

Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.

The Tower of Hanoi: Recursion with Animation

The Tower of Hanoi is a classic game that is often emulated on computers to demonstrate recursion.

The game runs as follows. There are a number of discs each with a hole in the center. Each disc can fit on any of 3 pegs and each peg is high enough to hold all the discs in a stack. In the initial configuration all the discs are stacked on the first peg with the largest disc on the bottom and the smallest on top. A disc is never stacked on top of a smaller disc. The problem is to move the discs, one at a time from peg to peg in such a way that this is always true and to finally end up with all of the discs on peg 3 in the original order.

The solution is elegant. Let's call the three pegs A, B, and C. If you don't know how to move 5 discs from A to C (using B for intermediate storage), then just move 4 discs from A to B, one disk from A to C (this is really easy) and then move 4 discs from B to C. Can't do 4 discs? Well then, move just 3 ...

Guido's hanoi.py in the Python Demo area is a nice demonstration of this recursive process. The heart of the program is just this.

The other 99% of the program involves doing TK graphics to make it come alive. Here is a screen shot of the game in progress.

And here is a javascript animation . Use browser back-button to return.

I have tried a couple of times to teach the Hanoi puzzle as a good example of recursion. It is much better than the usual factorial example which does nothing more than use recursion to replace a simple for loop.

But students have a hard time getting it. And I think the problem is the difficulty in visualizing the nested context of the recursive calls. We’ll take it on slowly.

Model View and Controller

The MVC discipline strives to find separate responsibilities of a program into code modules that are independent and loosely linked with each other.

The Model is a structure for the data being manipulated by the program

The Control is makes changes to the contents of the model and also passes the changing model along with other signals to the view.

The View outputs the model, either presenting a visual repretation, outputting information from the model, responding to signals from the Control or all of these. Some applications may have multiple views.

In the Tower of Hanoi an object oriented model might consist of a class for a disc and another for a peg. Each disc might have attributes for its size and color along with which peg it is stacked. A peg object might have attributes for its position and which disc objects are attached to it. Along with the attributes might be methods to move a disc from peg to peg and to calculate which disc and which peg should be next.

But this model would be fairly involved. In this project we use a much simpler model, a list structure. This list has an entry for each peg. Each peg would also be a list with an integer for each disc. The discs sorted by size top to bottom (small to large) on the peg. At the start the model looks like the following with all discs stacked on the first peg (peg 0).

The Control

The control for the Tower of Hanoi will turn out be quite simple but tricky. We’ll use the simple version of the model and the initial view will simply print the model. That’s easy since it’s just a Python expression and the python print statement works fine. We won’t bother with separate module for it.

As we do in many of the projects, we want to start by finding a solution for the simplest case. If we need to move just one disc, it’s just a single step: move the disc from the source peg to the destination peg. Pop it off the source peg and append it to the destination peg. That can be done in a single statement.

For two discs (2-discs) we can invoke the 1-disc code three times: move the top (smallest) disc to the auxillary peg, then move the next to the destination peg. And finally move the disc on the auxillary peg to the destination peg. Done.

And with that solution we can make a 3-disc solution. 2-disc to the auxillary peg, 1-disc to the destination and 2-disc again to move discs from the auxillary peg to the destination peg. Done.

And with a 3-disc solution a 4-disc can be … I’m sure you have the idea.

Here’s our first attempt at some control code. A much better one will follow in bit. We are going to avoid recursion by limiting the number of disks and writing a separate function for each case.

code for hanoiNR.py

Recursion explained

When I started programming our only language (Fortran) did not support recursion. Each function had its own call frame , a workspace which was created when the program was compiled. Here the local variables including the parameters in the call were kept and manipulated. The code itself was read-only. A Fortran version of the code above worked fine with 4 discs. But for more discs more (virtually identical) functions must be created.

Recursion, which allows simultanious activations of a function, is made possible with a simple trick. Instead of the compiler creating the call frame for the function, a new call frame is created at runtime each time the function is invoked. When the function is finished and and the result returned to its caller the call frame can be discarded. There may be multiple invocations of a function each with their own call frame that can keep on going.

This is not the full story. Tail recursion reuses call frames, but that’s not an issue here

So, here is the real code for the control section. The functions move1, move2, move3 and move4 have been “folded” into a single function hanoi . The number of discs to move, ndiscs , is passed as the first parameter.

code for hanoi.py

So now, instead of just printing the model, our view module that animates the discs. Let’s look at that next.

A Better View

A python structure like [ [], [1,2,3,4], [] ] makes a great model but as a view it lacks a little something. With our graphics package we can create a dynamic view that is much more interesting.

The Zelle graphics does a lot of the heavy lifting for us. We can create rectangles for pegs and discs in different sizes and colors and gently move discs from peg to peg.

Generally an animation requires us to draw each frame completely. While one frame is on the screen the next is drawn on an invisible screen in the background. If some elements in the animation are moving then they change position between frames. At the right time and when the new frame is complete the screens are swapped. If the rate is 30 times a second or faster then our brains perceive it as smooth motion.

The graphics package does this for us in the background, as far as I can tell. We simply create objects such as rectangles, polygons, text blocks and more and simply draw them, undraw them or have them move. Objects that are created later sit “above” earlier ones. When objects move they can slide over other objects they are above or under other objects without disturbing them. Nothing gets “erased” until it’s undrawn.

Our view module creates an animation very similar to the one you saw earlier. Discs and pegs are simple rectangles. The discs can move along paths that we construct. And discs are created after the pegs so that a disc can slide up and down a peg without appearing to be behind it.

The control code in hanoi.py calls the view.init function with the initial model. It is called just once. Control makes subsequent calls to view.moveDisc passing the updated model and the start and stop pegs. It is always the top disc on the source peg that is moved and it becomes the top disc at the destination.

code for view.py

Let’s look at a few of the trickier bits.

view.init creates the rectangles for the discs and pegs and draws them. In the dictionary discAttr we have the width and color of each disc (up to 4). Another dictionary stores a reference for each disc of its associated rectangle (view.drawDisc) .

view.calcPath calculates the path for the top disc on the source peg to travel to the open area on the destination disc. It returns a reference to the disc and a triple of (steps,dx,dy) for the 3 segments of the path (up, over and down).

The rectangle for the disc is then moved pixel by pixel through the 3 segments of the path. After each move the program sleeps .01 seconds. Changing this will change the speed of the animation.

Function view.test is only run if view.py is run standalone.

The monks of Hanoi were said to play the game with 64 discs and when finished, the universe would end. How well does this jive with current cosmology? ;)

You can download this zip file for this project

If you have comments or suggestions You can email me at mail me

Copyright © 2021 Chris Meyers and Fred Obermann

Tower of Hanoi

Explore the different techniques used to solve the Tower of Hanoi problem.

Background story

• Understanding recursive algorithm
• Running time complexity

The Tower of Hanoi puzzle was first published as an actual physical puzzle by the French teacher and recreational mathematician Édouard Lucas in 1883 under the pseudonym “N. Claus (de Siam)” (an anagram of “Lucas d’Amiens”). The following year, Henri de Parville described the puzzle with a remarkable story:

In the great temple at Benares . . . beneath the dome which marks the centre of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy

• Runestone in social media: Follow @iRunestone Our Facebook Page
• Table of Contents
• Assignments
• Peer Instruction (Instructor)
• Peer Instruction (Student)
• Change Course
• Instructor's Page
• Progress Page
• Edit Profile
• Change Password
• Scratch ActiveCode
• Scratch Activecode
• Instructors Guide
• About Runestone
• Report A Problem
• 5.1 Objectives
• 5.2 What Is Recursion?
• 5.3 Calculating the Sum of a List of Numbers
• 5.4 The Three Laws of Recursion
• 5.5 Converting an Integer to a String in Any Base
• 5.6 Stack Frames: Implementing Recursion
• 5.7 Introduction: Visualizing Recursion
• 5.8 Sierpinski Triangle
• 5.9 Complex Recursive Problems
• 5.10 Tower of Hanoi
• 5.11 Exploring a Maze
• 5.12 Dynamic Programming
• 5.13 Summary
• 5.14 Key Terms
• 5.15 Discussion Questions
• 5.16 Glossary
• 5.17 Programming Exercises
• 5.9. Complex Recursive Problems" data-toggle="tooltip">
• 5.11. Exploring a Maze' data-toggle="tooltip" >

5.10. Tower of Hanoi ¶

The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. He was inspired by a legend that tells of a Hindu temple where the puzzle was presented to young priests. At the beginning of time, the priests were given three poles and a stack of 64 gold disks, each disk a little smaller than the one beneath it. Their assignment was to transfer all 64 disks from one of the three poles to another, with two important constraints. They could only move one disk at a time, and they could never place a larger disk on top of a smaller one. The priests worked very efficiently, day and night, moving one disk every second. When they finished their work, the legend said, the temple would crumble into dust and the world would vanish.

Although the legend is interesting, you need not worry about the world ending any time soon. The number of moves required to correctly move a tower of 64 disks is \(2^{64}-1 = 18,446,744,073,709,551,615\) . At a rate of one move per second, that is \(584,942,417,355\) years! Clearly there is more to this puzzle than meets the eye.

Figure 1 shows an example of a configuration of disks in the middle of a move from the first peg to the third. Notice that, as the rules specify, the disks on each peg are stacked so that smaller disks are always on top of the larger disks. If you have not tried to solve this puzzle before, you should try it now. You do not need fancy disks and poles–a pile of books or pieces of paper will work.

Figure 1: An Example Arrangement of Disks for the Tower of Hanoi ¶

How do we go about solving this problem recursively? How would you go about solving this problem at all? What is our base case? Let’s think about this problem from the bottom up. Suppose you have a tower of five disks, originally on peg one. If you already knew how to move a tower of four disks to peg two, you could then easily move the bottom disk to peg three, and then move the tower of four from peg two to peg three. But what if you do not know how to move a tower of height four? Suppose that you knew how to move a tower of height three to peg three; then it would be easy to move the fourth disk to peg two and move the three from peg three on top of it. But what if you do not know how to move a tower of three? How about moving a tower of two disks to peg two and then moving the third disk to peg three, and then moving the tower of height two on top of it? But what if you still do not know how to do this? Surely you would agree that moving a single disk to peg three is easy enough, trivial you might even say. This sounds like a base case in the making.

Here is a high-level outline of how to move a tower from the starting pole, to the goal pole, using an intermediate pole:

Move a tower of height-1 to an intermediate pole, using the final pole.

Move the remaining disk to the final pole.

Move the tower of height-1 from the intermediate pole to the final pole using the original pole.

As long as we always obey the rule that the larger disks remain on the bottom of the stack, we can use the three steps above recursively, treating any larger disks as though they were not even there. The only thing missing from the outline above is the identification of a base case. The simplest Tower of Hanoi problem is a tower of one disk. In this case, we need move only a single disk to its final destination. A tower of one disk will be our base case. In addition, the steps outlined above move us toward the base case by reducing the height of the tower in steps 1 and 3. Listing 1 shows the Python code to solve the Tower of Hanoi puzzle.

Notice that the code in Listing 1 is almost identical to the English description. The key to the simplicity of the algorithm is that we make two different recursive calls, one on line 3 and a second on line 5. On line 3 we move all but the bottom disk on the initial tower to an intermediate pole. The next line simply moves the bottom disk to its final resting place. Then on line 5 we move the tower from the intermediate pole to the top of the largest disk. The base case is detected when the tower height is 0; in this case there is nothing to do, so the moveTower function simply returns. The important thing to remember about handling the base case this way is that simply returning from moveTower is what finally allows the moveDisk function to be called.

The function moveDisk , shown in Listing 2 , is very simple. All it does is print out that it is moving a disk from one pole to another. If you type in and run the moveTower program you can see that it gives you a very efficient solution to the puzzle.

The program in ActiveCode 1 provides the entire solution for three disks.

Now that you have seen the code for both moveTower and moveDisk , you may be wondering why we do not have a data structure that explicitly keeps track of what disks are on what poles. Here is a hint: if you were going to explicitly keep track of the disks, you would probably use three Stack objects, one for each pole. The answer is that Python provides the stacks that we need implicitly through the call stack.

12. Towers of Hanoi

By Bernd Klein . Last modified: 01 Feb 2022.

On this page ➤

Introduction

Why do we present a Python implementation of the "Towers of Hanoi"? The hello-world of recursion is the Factorial. This means, you will hardly find any book or tutorial about programming languages which doesn't deal with the first and introductory example about recursive functions. Another one is the calculation of the n-th Fibonacci number. Both are well suited for a tutorial because of their simplicity but they can be easily written in an iterative way as well.

If you have problems in understanding recursion, we recommend that you go through the chapter " Recursive Functions " of our tutorial.

That's different with the "Towers of Hanoi". A recursive solution almost forces itself on the programmer, while the iterative solution of the game is hard to find and to grasp. So, with the Towers of Hanoi we present a recursive Python program, which is hard to program in an iterative way.

Live Python training

Enjoying this page? We offer live Python training courses covering the content of this site.

See: Live Python courses overview

There is an old legend about a temple or monastery, which contains three poles. One of them filled with 64 gold disks. The disks are of different sizes, and they are put on top of each other, according to their size, i.e. each disk on the pole a little smaller than the one beneath it. The priests, if the legend is about a temple, or the monks, if it is about a monastery, have to move this stack from one of the three poles to another one. But one rule has to be applied: a large disk can never be placed on top of a smaller one. When they would have finished their work, the legend tells, the temple would crumble into dust, and the world would end. But don't be afraid, it's not very likely that they will finish their work soon, because 264 - 1 moves are necessary, i.e. 18,446,744,073,709,551,615 to move the tower according to the rules. But there is - most probably - no ancient legend. The legend and the game "towers of Hanoi" had been conceived by the French mathematician Edouard Lucas in 1883.

Rules of the Game

The rules of the game are very simple, but the solution is not so obvious. The game "Towers of Hanoi" uses three rods. A number of disks is stacked in decreasing order from the bottom to the top of one rod, i.e. the largest disk at the bottom and the smallest one on top. The disks build a conical tower.

The aim of the game is to move the tower of disks from one rod to another rod.

The following rules have to be obeyed:

• Only one disk may be moved at a time.
• Only the most upper disk from one of the rods can be moved in a move
• It can be put on another rod, if this rod is empty or if the most upper disk of this rod is larger than the one which is moved.

Number of Moves

The number of moves necessary to move a tower with n disks can be calculated as: 2 n - 1

Playing around to Find a Solution From the formula above, we know that we need 7 moves to move a tower of size 3 from the most left rod (let's call it SOURCE to the most right tower (TARGET). The pole in the middle (we will call it AUX) is needed as an auxiliary stack to deposit disks temporarily. Before we examine the case with 3 disks, as it is depicted in the image on the right side, we will have a look at towers of size 1 (i.e. just one disk) and size 2. The solution for a tower with just one disk is straightforward: We will move the one disk on the SOURCE tower to the TARGET tower and we are finished. Let's look now at a tower with size 2, i.e. two disks. There are two possibilities to move the first disk, the disk on top of the stack of SOURCE: We can move this disk either to TARGET or to AUX.

We have seen in the cases n=1 and n=2 that it depends on the first move, if we will be able to successfully and with the minimal number of moves solve the riddle. We know from our formula that the minimal number of moves necessary to move a tower of size 3 from the SOURCE peg to the target peg is 7 (23 - 1) You can see in the solution, which we present in our image that the first disk has to be moved from the peg SOURCE to the peg TARGET. If your first step consists of moving the smallest disk to AUX, you will not be capable of finishing the task with less than 9 moves. Let's number the disks as D1 (smallest), D2 and D3 (largest) and name the pegs as S (SOURCE peg), A (AUX), T (TARGET). We can see that we move in three moves the tower of size 2 (the disks D1 and D2) to A. Now we can move D3 to T, where it is finally positioned. The last three moves move the tower consisting of D2D1 from peg A to T to place them on top of D3. There is a general rule for moving a tower of size n (n > 1) from the peg S to the peg T:

• So let's start by moving the smallest disk from SOURCE to TARGET. Now there are two choices: We can move this disk again, either back to the SOURCE peg, which obviously doesn't make sense, or we could move it to AUX, which doesn't make sense either, because we could have moved there as our first step. So the only move which makes sense is moving the other disk, i.e. the largest disk, to peg AUX. Now, we have to move the smallest disk again, because we don't want to move the largest disk back to SOURCE again. We can move the smallest disk to AUX. Now we can see that we have moved the tower of size 2 to the peg AUX, but the target had been peg TARGET. We have already used the maximal number of moves, i.e. 2 2 - 1 = 3
• move a tower of n - 1 discs D n-1 ... D 1 from S to A. Disk D n is left alone on peg S
• Move disk D n to T
• move the tower of n - 1 discs D n-1 ... D 1 on A to T, i.e. this tower will be put on top of Disk D n

The algorithm, which we have just defined, is a recursive algorithm to move a tower of size n. It actually is the one, which we will use in our Python implementation to solve the Towers of Hanoi. Step 2 is a simple move of a disk. But to accomplish the steps 1 and 3, we apply the same algorithm again on a tower of n-1. The calculation will finish with a finite number of steps, because very time the recursion will be started with a tower which is 1 smaller than the one in the calling function. So finally we will end up with a tower of size n = 1, i.e. a simple move.

Recursive Python Program

The following Python script contains a recursive function "hanoi", which implements a recursive solution for Towers of Hanoi:

This function is an implementation of what we have explained in the previous subchapter. First we move a tower of size n-1 from the peg source to the helper peg. We do this by calling

hanoi(n - 1, source, target, helper)

After this, there will be the largest disk left on the peg source. We move it to the empty peg target by the statement

After this, we have to move the tower from "helper" to "target", i.e. on top of the largest disk:

If you want to check, what's going on, while the recursion is running, we suggest the following Python programm. We have slightly changed the data structure. Instead of passing just the stacks of disks to the function, we pass tuples to the function. Each tuple consists of the stack and the function of the stack:

On this page

Python and Turtle

Python, Turtle, Projects, Learn

Tower of Hanoi with Python Turtle (Source Code Included)

• Difficulty Level 10

Tower of Hanoi is a puzzle where you need to move all the rings from peg 1 to peg 3.

Rules are: 1. You can only move one ring at each step. 2. You can not put a larger ring on top of a smaller ring.

Solve and animate the Tower of Hanoi problem with Python and Turtle.

Related Post

Asteroids tutorial- bullets asteroids tutorial- bullets.

The Bullets Class First, we need to create bullet class. There should be some variables that apply to all the bullets, such as its speed and how range. The starting

Tutorial: Drawing Crescent Moon with Python Turtle Tutorial: Drawing Crescent Moon with Python Turtle

In this tutorial we are going to show how to draw a crescent moon. It can be done easily with two steps: 1. Draw a full moon 2. Draw a

Tutorial: Rounding Any Corner with Python Turtle Tutorial: Rounding Any Corner with Python Turtle

In a previous tutorial we explained how to round a rectangle with Python Turtle. In this tutorial, we are going to show you how to make any corner round. Knowledge

The #1 tech hiring platform

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

Releases: JoPadOfficiel/Jeux_tour_de_Hanoi_Python

There aren’t any releases here.

You can create a release to package software, along with release notes and links to binary files, for other people to use. Learn more about releases in our docs .