FIFA-2022 Career Guide Free Tutorials Go to Your University Placement Preparation 
0 like 0 dislike
in Artificial Intelligence(AI) & Machine Learning by Goeduhub's Expert (3.1k points)
Tower of Hanoi Problem in Artificial Intelligence solved with recursion algorithms in python.

1 Answer

0 like 0 dislike
by Goeduhub's Expert (3.1k points)
edited by
Best answer

Problem: (Tower of Hanoi)

Tower of hanoi is mathematical game puzzle where we have three pile (pillars) and n numbers of disk.

This game has some rules  (Rules of game)

  1. Only one disk will move at a time.

  2. The larger disk should always be on the bottom and the smaller disk on top of it.(Even during intermediate move)

  3. Move only the uppermost disk.

  4. All disk move to destination pile from source pile.

So, here we are trying to solve that how many moves are required to solve a problem (It depends on number of disk).

Tower of hanoi

When we have two disk and 3 pillars (pile, A, B, C)

In the above diagram, following the rule of the game our target is move the disks from source pile (pillar) to the destination pillar. (let's take a look how many steps/ moves are required to make this happen).

Step1:  Move small disk to the auxiliary pillar (A).

Step2: Move large disk to the Destination pillar (B).

Step3: Move small disk to  the Destination pillar(B).4

So, basically when we have 2 disks we required 3 move to reach the destination .

What if we have 3 , 4, 5...n disks ? 

Eventually, you figure out that there is some pattern to the puzzle and with each increment in disks, the pattern could be followed recursively. 

Total move required to reach destination pillar is formula of moves means if we have 3 disks we required (4 moves to reach destination pillar) , if 4 disks 8 moves required and so on ...

Note: Tower of hanoi problem is an example of recursion and backtracking. 

Recursion and backtracking: When a function calls itself, its called Recursion. (Breaking problem into smaller problems).

Let's suppose we have a problem A we subdivided it into B, C, and D.  In Backtracking we attempt solving a sub-problem, and if we don't reach the desired solution, then undo whatever we did for solving that sub-problem, and try solving another sub-problem (Until we get to the goal).

Note: There must be a termination condition in the recursion problems.

Practical Implementation using Python

class Tower:

  def __init__(self):

    self.terminate = 1

  def printMove(self, source, destination):

    print("{} -> {}".format(source, destination))


  def move(self, disc, source, destination, auxiliary):

    if disc == self.terminate:

      self.printMove(source, destination)


      self.move(disc - 1, source, auxiliary, destination)

      self.move(1, source, destination, auxiliary)

      self.move(disc - 1, auxiliary, destination, source)

t = Tower();

t.move(3, 'A', 'B', 'C')


Output of tower of hanoi

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs


About Us | Contact Us || Terms & Conditions | Privacy Policy ||  Youtube Channel || Telegram Channel © Social::   |  | 


Free Online Directory