Gadgets 4 Students Online Courses
Free Tutorials  Go to Your University  Placement Preparation 
0 like 0 dislike
10.4k views
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.

Where can I do online courses From Word's Top Instructors?

UDEMY::  Attend All Udemy Courses in Just INR 450[Coupon]
Coursera:: Join For FREE

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)

    else:

      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

Output of tower of hanoi

Code your future with Programming skills. Courses starting at ₹ 455 only!

3.3k questions

7.1k answers

395 comments

4.5k users

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs

 Goeduhub:

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

 

Free Online Directory
...