# Algorithm to solve Tower of Hanoi Problem

**The Tower of Hanoi problem****Problem description:**

- There are
**3 pegs** - There are
**N disks**stacked**on the first peg**. (The disks has a hole in the center).

**Note:**has a*Each disk***different diameter**

*Initially*situation:

**Problem***Hanoi(N)*:**Move**thefrom*N*disks**peg 1**to**peg 3**- You must
**obey**a**set of rules**.

**Tower of Hanoi Rules:**

- You can only
**move**(from any peg to any other peg), and*one disk*at a time - You may
stack a*not**smaller*disk**on top**of a*larger*disk

- You can only

- There are

*Hands on*experiment with the Tower of Hanoi- See how a
**Tower of Hanoi**of**4 disks**is solved:

- Here is a web site with a nice
**Tower of Hanoi applet**for you to try:**click here** - I have a local Hanoi applet if the above one fails to work:
**click here**

- See how a
**Formulating the***Tower of Hanoi*algorithm – step 1: input and output**Problem description:**

- Write a
**method**to obtain theto solve*steps***Tower of Hanoi problem**of movingfrom*n*disks**peg 1**to**peg 3**

**Example:****Problem:**

- Move
from*3*disks**peg 1**to**peg 3**

- Move
**Solution:**

Move 1 disk: 1 -> 3 1 -> 2 3 -> 2 1 -> 3 2 -> 1 2 -> 3 1 -> 3

Try out the moves with this

**applet**:**click here**

- Write a
- We will
**first****figure out**the following:

- What
does the*input*information**algorithm**need to**solve the problem**. - What
does the*output*information**algorithm**need to**return to the user**.

In other words:

- What are the
?*input*parameters - What is the
**return**?*type*

- What
**Input**and**output****information**:

- We may as well
**select**an (appropriate)to go with the*method*name**input**and**output**…(Together, they will form theof the*header***Java method**)Let’s pick this name:

hanoi

- What
**information**does the**method**need to**perform the task**– i.e: what are its?*input*parameters

= the`nDisks`**number**of disks that need to be**moved**= the`fromPeg`**identifier (index)**of the peg where the disks**originate**= the`toPeg`**identifier (index)**of the peg where the disks are**moved to**

**Example:**how to express some**Tower of Hanoi**problemshanoi( 10, 1, 3 ) move 10 disks from peg 1 to peg 3 hanoi( 15, 1, 3 ) move 15 disks from peg 1 to peg 3 hanoi( 15, 1, 2 ) move 15 disks from peg 1 to peg 2

**Finally**, what is theof the*type***information**do you want to**obtain**from the method — i.e. what is the**return**?*type*

- We want to know
**how to****move the disks** - Example: how to move
**3 disks**from**peg 1**to**peg 3**:

1 -> 3 1 -> 2 3 -> 2 1 -> 3 2 -> 1 2 -> 3 1 -> 3

What is the

**type**of this**information**???*Answer:*!!!`String`

- The
**return type**is`String`

- We want to know

- We may as well
of the*Header***method**:

public static String hanoi( int nDisks, int fromPeg, int toPeg ) { .... }

The

**meaning**of the**input parameters**are:=`nDisks`**number of disks**to move= the`fromPeg`where the*starting*peg numberdisks are moved*nDisks*= the`toPeg`where the*destination*peg numberdisks are moved*nDisks*

**Formulating the***Tower of Hanoi*algorithm – step 2: develop the*solution***Solution method:**

- Because this lecture is on
**recursive algorithm**, you can kinda guess that the**solution**will be a.*recursive*algorithm

- Because this lecture is on
- Because the
**Tower of Hanoi**problem is**more complicated**than**factorial**or**fibonacci**, I will follow the**steps**given in the**general procedure**more carefully to help you see how the solution is put together.Here are the**general step**to write a– summarized for your convenience:*recursive*algorithm

- Find out
*which*problems you need to use to*smaller*Tower of Hanoi**solve**theproblem*original*Tower of Hanoi - Find out
**how to use**theof the*solutions*problems to*smaller*Tower of Hanoithe*solve*problem.*original*Tower of Hanoi - Find the
**solutions**for a**sufficient number**of the**base cases**.

- Find out
*Step 1:***Identifying**aproblem within the*smaller*Tower of Hanoi**Tower of Hanoi problem**:

- The
**original****Tower of Hanoi**problem:**move***N*disks

- A
*smaller***Tower of Hanoi**problem:**move***N-1*disks

- The
figure out*Step 2:*to use the*how***solution**of theproblem to*smaller*Tower of Hanoi (*N−1*disks)**solve**theproblem.*original*Tower of Hanoi (*N*disks)

- The
problem:*original*Tower of Hanoi (*N*disks)

- The
of the*effect***solution**of theproblem is:*smaller*Tower of Hanoi (*N−1*disks)**Case 1:**

Before After **Case 2:**Before After **Think a little bit….**can use*How*the*use***solution**of**case 1**or**case 2**tothe*solve*???*original*Tower of Hanoi problem

: How to*Answer*the*use***solution**theproblem to*smaller*Tower of Hanoi (*N−1*disks)**solve**theproblem:*original*Tower of Hanoi (*N*disks)

, solve*First**this*problem:*smaller*Tower of Hanoi (*N−1*disks)

Before After

move*Next:***one disk**from**peg 1**to**peg 3**

Before After

: solve*Finally**this*problem:*smaller*Tower of Hanoi (*N−1*disks)

Before After

- The
find*Step 3:*(we need*base cases***one****base case**– because thehas the size*smaller*problem)*N−1*

- Move
**stack of disks**that has**1 disk**is**very easy**:

- Move

**The recursive solution for the Tower of Hanoi problem****Terminology:**

= the*from*peg**source peg**in a**Tower of Hanoi**problem.= the*to*peg**destination peg**in a**Tower of Hanoi**problem.= the*help*peg**peg**in a**Tower of Hanoi**problem that isa*not*.*source*or*destination*peg

**Example:**

**hanoi(n, 1, 3)**means the**Tower of Hanoi**problem of moving**n disks****from****peg 1****to****peg 3**- The
= 1*from*peg - The
= 3*to*peg - The
= 2*help*peg

**Pseudo code:**

String hanoi( int nDisks, int fromPeg, int toPeg ) { int helpPeg; if ( nDisks == 1 ) { /* ------------------------------------------------------ Solving a trivial (base case) Tower of Hanoi problem: ------------------------------------------------------ */ return( "Do this move: fromPeg --> toPeg" ); } else { /* ------------------------------------------------ Solving a non-trivial Tower of Hanoi problem: ------------------------------------------------ */ /* ------------------------------------------------ Determine the helpPeg ------------------------------------------------ */ helpPeg = peg index that is not equal to fromPeg and toPeg; /* --------------------------------------------------- First: solve this smaller Tower of Hanoi problem: ---------------------------------------------------- */ sol1 = hanoi( nDisks-1, fromPeg, helpPeg ); // Sol1 looks like: 1 -> 3, 1 -> 2, ... /* --------------------------------------------------- Next: do this move ---------------------------------------------------- */ myStep = "Do this move: fromPeg --> toPeg"; /* --------------------------------------------------- Finally: solve this smaller Tower of Hanoi problem: ---------------------------------------------------- */ sol2 = hanoi( nDisks-1, helpPeg, toPeg ); // Sol2 looks like: 1 -> 3, 1 -> 2, ... /* =============================================== How to use the solutions sol1 and sol2 to solve hanoi(nDisks, fromPeg, toPeg): 1. first making the moves in sol1 2. then do myStep 3. finally, do the moves in sol2 =============================================== */ mySol = so1l + myStep + sol2; // mySol looks like: 1 -> 3, 1 -> 2, ... return ( mySol ); }