Question

Tower of Hanoi Problem in Artificial Intelligence solved with recursion algorithms in python.

Answer 1

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).

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  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