### Solving the Tower of Hanoi using recursion

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

 Each disk has a different diameter

• Initially situation:

• Problem Hanoi(N):

• Move the N disks from peg 1 to peg 3
• You must obey a set of rules.

• Tower of Hanoi Rules:

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

• 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

• Formulating the Tower of Hanoi algorithm - step 1:     input and output

• Problem description:

• Write a method to obtain the steps to solve Tower of Hanoi problem of moving n disks from peg 1 to peg 3

Example:

• Problem:

 Move 3 disks from peg 1 to peg 3

• Solution:

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

• We will first figure out the following:

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

In other words:

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

• Input and output information:

1. We may as well select an (appropriate) method name to go with the input and output...

(Together, they will form the header of the Java method)

Let's pick this name:

 ``` hanoi ```

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

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

Example: how to express some Tower of Hanoi problems

 ``` hanoi( 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 ```

3. Finally, what is the type of the 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 ???

• The return type is String

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

The meaning of the input parameters are:

 nDisks = number of disks to move fromPeg = the starting peg number where the nDisks disks are moved toPeg = the destination peg number where the nDisks disks are moved

• 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 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 recursive algorithm - summarized for your convenience:

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

• Step 1: Identifying a smaller Tower of Hanoi problem within the Tower of Hanoi problem:

• The original Tower of Hanoi problem: move N disks

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

• Step 2: figure out how to use the solution of the smaller Tower of Hanoi (N−1 disks) problem to solve the original Tower of Hanoi (N disks) problem.

• The original Tower of Hanoi (N disks) problem:

• The effect of the solution of the smaller Tower of Hanoi (N−1 disks) problem is:

Case 1:

Before After

Case 2:

Before After

Think a little bit....

 How can use use the solution of case 1 or case 2 to solve the original Tower of Hanoi problem ???

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

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

Before After

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

Before After

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

Before After

• Step 3: find base cases (we need one base case - because the smaller problem has the size N−1)

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

• The recursive solution for the Tower of Hanoi problem

• Terminology:

• from peg = the source peg in a Tower of Hanoi problem.

• to peg = the destination peg in a Tower of Hanoi problem.

• help peg = the peg in a Tower of Hanoi problem that is not a 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 from peg = 1 The to peg = 3 The help peg = 2

• 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 ); } ```

• Java Program:

 ``` public class Recurse3 { public static String hanoi(int nDisks, int fromPeg, int toPeg) { int helpPeg; String Sol1, Sol2, MyStep, mySol; // Contains moves if ( nDisks == 1 ) { return fromPeg + " -> " + toPeg + "\n"; } else { helpPeg = 6 - fromPeg - toPeg; // Because fromPeg + helpPeg + toPeg = 6 Sol1 = hanoi(nDisks-1, fromPeg, helpPeg); MyStep = fromPeg + " -> " + toPeg + "\n"; Sol2 = hanoi(nDisks-1, helpPeg, toPeg); mySol = Sol1 + MyStep + Sol2; // + = String concatenation ! return mySol;; } } public static void main (String[] args) { int n = 3; String StepsToSolution; StepsToSolution = hanoi(n, 1, 3); System.out.println(StepsToSolution); } } ```

• Example Program: (Demo above code)

How to run the program:

 Right click on link and save in a scratch directory To compile:   javac Recurse3.java To run:          java Recurse3

• Understanding the recursive Hanoi algorithm using a concrete example

• If the above is a bit abstract, hopefully, the following concrete example will help you understand the Hanoi() method better,

• Let's consider the statements executed by the invocation:

 ``` hanoi( 4, 1, 3 ) --- move 4 disks from peg 1 ⇒ peg 3 ```

According to the hanoi() method:

 ``` public static String hanoi(int nDisks, int fromPeg, int toPeg) { int helpPeg; String Sol1, Sol2, MyStep, mySol; // Contains moves if ( nDisks == 1 ) { return fromPeg + " -> " + toPeg + "\n"; } else { helpPeg = 6 - fromPeg - toPeg; // Because fromPeg + helpPeg + toPeg = 6 Sol1 = hanoi(nDisks-1, fromPeg, helpPeg); MyStep = fromPeg + " -> " + toPeg + "\n"; Sol2 = hanoi(nDisks-1, helpPeg, toPeg); mySol = Sol1 + MyStep + Sol2; // + = String concatenation ! return mySol;; } } ```

the invocation will execute these statements:

 ``` helpPeg = 6 - 1 - 3 = 2; Sol1 = hanoi( 3, 1, 2 ); // Move 3 disks from peg 1 ⇒ peg 2 MyStep = "1 -> 3"; Sol2 = hanoi( 3, 2, 3 ); // Move 3 disks from peg 2 ⇒ peg 3 mySol = Sol1 + MyStep + Sol2; return mySol; ```

• Now, let us run the program for hanoi(4, 1, 3) and see what is the output:

 ``` Output of hanoi(4,1,3): 1 -> 2 1 -> 3 2 -> 3 1 -> 2 (These are steps in Sol1 !!!) 3 -> 1 3 -> 2 1 -> 2 1 -> 3 (this is MyStep !!!) 2 -> 3 2 -> 1 3 -> 1 2 -> 3 (These are steps in Sol2 !!!) 1 -> 2 1 -> 3 2 -> 3 ```

• Now perform the steps using this web page:

• Notice the progress of the solution:

• Start of hanoi(4, 1, 3)

Moves 4 disks from peg 1 ⇒ peg 3

• After the steps:

 ``` 1 -> 2 1 -> 3 2 -> 3 1 -> 2 (These are steps in Sol1 !!!) 3 -> 1 3 -> 2 ```

We get:

Notice that this is the solution of hanoi( 3, 1, 2) !!!

The solution was used to move 3 disks from peg 1 ⇒ peg 2 !

• After the steps:

 ``` 1 -> 3 (this is MyStep !!!) ```

We get:

Notice that this is the MyStep = "1 -> 3"; statement !!!

• After the steps:

 ``` 2 -> 3 2 -> 1 3 -> 1 2 -> 3 (These are steps in Sol2 !!!) 1 -> 2 1 -> 3 2 -> 3 ```

We get:

Notice that this is the solution of hanoi( 3, 2, 3) !!!

The solution was used to move 3 disks from peg 2 ⇒ peg 3 !