User:Tandona1

From www.norsemathology.org

Jump to: navigation, search

Description

Tower of Hanoi is a mathematical problem where it contains three towers and more than one disks. It is a classic problem which involves moving disk which are initially arranged in stacks in ascending order where the bigger disk are at the bottom. This concept was taught to me in my CSC 360 class. The objective of the puzzle is to move the stack of disks to another tower following these simple rules.

a) Only one disk can be moved at a time
b) No disk can be placed on top of the smaller disk

You can see an animation of the solution here:

Media:Hanoi.gif

This problem has a recursive nature and hence it can be solved using recursion.

Recursion

Recursion occurs when a thing is defined in terms of itself or of its type. Tower of Hanoi can be solved using recursion. I have created a Java program based on recursion which will help me demonstrate its solution. Initially, all the disks are stacked in a single tower. If there is just one disk then there is no need of doing any calculation as you can straight forward move that one disk from one tower to another. For our case let’s take three towers A, B and C. All the disks are stacked in tower A initially. Our goal is to move the stack to tower B.

Let there be n number of disks. The problem can then be solved with the following steps :
Step 1 − Move n-1 disks from A to C recursively with assistance of tower B.
Step 2 − Move nth disk from A to B.
Step 3 − Move n-1 disks from C to B recursively with assistance of tower B.

Here is my code:


Image:wiki.jpg



Here is the solution it generates:
Enter the number of disks: 5
The moves are:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Move disk 4 from A to B
Move disk 1 from C to B
Move disk 2 from C to A
Move disk 1 from B to A
Move disk 3 from C to B
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 5 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Move disk 3 from B to A
Move disk 1 from C to B
Move disk 2 from C to A
Move disk 1 from B to A
Move disk 4 from B to C
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Recursion Relation

If there is one disk it takes us one move to move from one tower to other, if there are two disk it takes us 3 moves and Similarly for three disk we can do it in 7 steps. It gets harder to know the least number of moves required to solve the problem when we have 4 or more disk.
Since, we know that:
For a given N number of disks, the way to accomplish the task in a minimum number of steps is:
a)Move the top N−1 disks to a spare peg from source peg.
b)Move the bottom disk to the destination peg.
c)Finally, move the N−1 disks from the spare peg to the destination peg.

Therefore, the recurrence relation for this puzzle would become:

a1=1, a2=3, aN = 2aN−1+1, N ≥ 2



Personal tools