Home » Python » Python programs

Python program Tower of Hanoi (modified)

Here, we are going to implement a python program for Tower of Hanoi.
Submitted by Anuj Singh, on June 30, 2019

You are challenged for a challenge to find the number of moves required to move a stack of disks from one peg to another peg. Wait for a second, it sounds easy? Let’s find are what is going on and in this article, we are introducing a chapter of "TOWER OF HANOI".

You are given with a stack of n disks on a peg arranges as largest is at the bottom and smallest is at the top. We are required to shift this whole stack to another peg (total three pegs, two are empty initially) with considering the following rule:

  1. No larger disk can be placed over a smaller one.
  2. One disk at a time.
  3. Disk cannot be transferred to peg B directly. It must be transferred to middle peg while moving from A to B or B to A.

The problem is looking easy but it's not. The way we are going to tackle it is recursion. The problem is simple when you see it from recursion perspective.

Key: The number of steps required to shift the stack is exactly equal to the twice of steps for shifting the stack of one less disk(The largest one) plus one step.

    Consider the case of shifting one disk : T(1) = 2
    Consider the case of shifting two disk : T(2) = 3*T(1) + 2 = 8
    Consider the case of shifting three disk : T(3) = 3*T(2) + 2 = 26
    .
    .
    .
    . 
    T(n) = 3*T(n-1) + 2

Implementing this formula now in our python program is our next goal of solving this.

So here is the code:

def hanoi(x):
    global repN
    repN += 1
    if x == 1:
        return 2
    
    else:
        return 3*hanoi(x-1) + 2
    
x = int(input("ENTER THE NUMBER OF DISKS: "))

global repN
repN =0

print('NUMBER OF STEPS: ', hanoi(x), ' :', repN)

Output:

ENTER THE NUMBER OF DISKS: 14                                                                                                  
NUMBER OF STEPS:  4782968  : 14





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL




Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.