Tower of Hanoi

Hello Reader,

Today we will go through the solution to the famous problem called the Tower of Hanoi. But before that, let us again go through the requirements and the constraints provided to us in the problem statement.

Requirement: The requirement in this problem is to print the instructions to move the disks from tower 1 to tower 2 using tower 3 subject to the constraints given below.

Constraints:

1. You can move 1 disk at a particular point in time.
2. You cannot place a smaller disk under a larger disk.
3. You can only move the disk at the top.

Intuition for the recursive solution:

Reader, your intuition to the solution may be correct! The intuition for the recursive solution comes from what you have been studying in this section. You may have worked on the ideas of “High-Level Thinking” and then subsequently used “Low-Level Thinking” to define your solutions to recursion problems. In case you have not gone through this logic flow, We would request you to either read through the first few articles in the Introduction to Recursion section on https://www.pepcoding.com/resources/online-java-foundation

or go through this video: https://www.youtube.com/watch?v=5Q5ed7PWJ8I&list=PL-Jc9J83PIiFxaBahjslhBD1LiJAV7nKs

We hope that you have gone through either the articles or the video so that the explanation ahead is clear for you.

Reader, firstly you may be wondering what should be the Expectation and Faith in this problem?

The expectation from the function toh(3, A, B, C) (Tower of Hanoi function with 3 disks and 3 towers labeled A, B, and C respectively) is that it is capable of printing instructions such that the requirement of the problem is satisfied while not violating any constraint(Printing of instructions such that all disks are transferred from tower A to tower b through tower c while adhering to all the constraints).

Now, as you may have noticed by now, for recursive problems once we have set our Expectation with the function, we have to keep Faith that the function is capable of solving a sub-problem of the given wider problem. The Faith in this question will be kept on toh(2, a, b, c) i.e. the function knows how to write the instructions which can move 2 disks from the tower a to tower b using tower c while adhering to the constraints given above.

Now, once we have set our Expectation and Faith, we have to think about the logic so that we can meet the Expectation logically using the Faith we have set. Readers, do note that it is important to have utmost belief in the faith we have set that it will do the work we think it should do, and then the onus on you is to think the logic to meet the Expectation from the function using this Faith (i.e. assuming we can move two disks successfully from one tower to another, how do we achieve the moving of 3 towers from one tower to another).

Here, our Expectation is toh(3, A, B, C) i.e. printing of instructions such that 3 disks are moved from tower A to tower B using tower C.

Now for the function, you could think of this template toh(number of disks, from, to, using).

Readers, now think of the meeting the Expectation being fulfilled in the form of this question:

If Tower of Hanoi(function) knows how to print the instructions to move 2 disks while satisfying the rules, then how can we make Tower of Hanoi(function) print the instructions to move 3 disks while not violating any constraint?

Readers, we will use the following steps to help meet the Expectation of toh(3, A, B, C) using the Faith we have set:

1. We will use the Faith we set as precedence and write the following recursive call:

toh(2, A, C, B). Readers, try to associate this with the template mentioned above. What we achieve through this call is that the instructions to move 2 disks from tower A to tower C while using tower B are now printed(in accordance with the faith we had with the toh(2, A, B, C) function).

1. Now we will print the step to move disk 3 from A to B( 3:[A->B]).
2. Now what we have achieved till now includes, 2 disks present in tower C and disk 3 present in tower B and tower A is now empty, now we have to move these 2 disks to tower B to meet the Expectation. How can we do that?

Yes, you are right! We can use the faith we have set in the function in the case of 2 disks to move the disks from tower C to tower B using tower A while not violating any constraint.

Thus we will make a recursive call: toh(2, C, B, A)

We keep faith that this recursive call will print the instructions of moving 2 disks from tower C to B using tower A.

Now a concern you might have is that toh(2, A, C, B) might move 2 disks simultaneously from A to C using B. But understand that the faith we have set is in accordance with the fact that this call will print instructions to move these 2 disks in accordance with the constraints of the problem, so two disks being moved simultaneously is not possible.

If you are following this solution and want a visual representation of the logic above you might want to watch the video given below from 0:00 up to 8:40:

https://www.youtube.com/watch?v=QDBrZFROuA0

Now, let us write the code for the part that we have discussed till now:

```

import java.io.*;

import java.util.*;

public class Main {

public static void main(String[] args) throws Exception {

Scanner scn = new Scanner(System.in);

int n = scn.nextInt();

int t1id = scn.nextInt();

int t2id = scn.nextInt();

int t3id = scn.nextInt();

toh(n,t1id,t2id,t3id);

}

public static void toh(int n, int t1id, int t2id, int t3id){

if(n == 0)

{ //Nothing to do if we have no disk left so we will return

return;

}

toh(n-1,t1id,t3id,t2id); // will print the instructions to move n-1 disks from t1 to t3 using t2 (1)

//Now only disk left is the nth one, we will now move that disk from t1 to t2

System.out.println(n+”[“+t1id+” -> “+t2id+”]”); //(2)

//Now we have to print the instructions to move n-1 disks from t3 to t2 using t1.

toh(n-1,t3id,t2id,t1id); //(3)

}

}

```

For more information regarding the code and the views given above, you might want to watch the video given below from 8:41 to 12:51:

https://youtu.be/QDBrZFROuA0?t=521

Dry run and explanation of recursive logic being followed:

The nature of the recursion followed in this problem is of the manner we have seen previously in the question Print zig-zag. In case you have not gone through this concept, We would request you to go through this video before proceeding further: https://www.youtube.com/watch?v=R7qja_gZrvI

Now, if you have gone through the logic explained in Print zig-zag, you will be able to understand that for the function toh (Tower of Hanoi) we are making 2 recursive calls i.e. left call and right call and we can do the processing in 3 different areas i.e. preorder area (before making the left recursive call), inorder area (after the left recursive call but before making the right recursive call) and the postorder area (after the left and right recursive calls).

Here we are printing in the inorder area indicating transfer of 1st disk from tower 1 to tower 2.

public static void toh(int n, int t1id, int t2id, int t3id){

if(n == 0)

{ return;

}

//Preorder area

toh(n-1,t1id,t3id,t2id); //Left recursive call

System.out.println(n+”[“+t1id+” -> “+t2id+”]”); //Inorder area

toh(n-1,t3id,t2id,t1id); //Right recursive call

//Postorder area

}

Can you think of what the left and right recursive calls are achieving here?

3,A,B,C — — — -> Left Recursive Call — — — → 2,A,C,B

and

3,A,B,C — — — -> Right Recursive Call — — — -> 2,C,B,A

This means that the left recursive call swaps B and C while calling for n-1 disks and the right recursive call swaps A and C while calling for n-1 disks.

Now, let’s move on to the dry run and see how the output of the instructions comes:

Fig. Dry Run of the recursive logic (similar logic to Print zig-zag) explained above with the blue dots indicating the execution of the print statement in the inorder section of the code of the recursive function.

You can observe that the base condition is for n = 0 and we are directly returning from there as there are no disks to be moved.

Now let’s see what is happening to the output as we process along the dry run:

Initial logical view at 3ABC:

The first statement of the output comes when we reach the inorder code for 1ABC, we print:

1:[A->B]

Logical View (in terms of movement of the disk):

Now next inorder statement comes for 2ACB, we print:

2:[A->C]

Logical View (in terms of movement of the disk):

Now next inorder statement comes for 1BCA, we print:

1:[B->C]

Logical View (in terms of movement of the disk):

The next inorder statement comes for 3ABC (the call from where all smaller calls originated), we print:

3:[A->B]

Logical View (in terms of movement of the disk):

The next inorder statement comes for 1CAB, we print:

1:[C->A]

Logical View (in terms of movement of the disk):

The next inorder statement comes for 2CBA, we print:

2:[C->B]

Logical View (in terms of movement of the disk):

The next inorder statement comes for 1ABC, we print:

1:[A->B]

Logical View (in terms of movement of the disk):

As you may have observed in the logical view above, we successfully managed to transfer all the 3 blocks from tower A to tower B using tower C and also printed the required instructions (satisfying the requirement of the question) while not violating any constraint.

A breakdown of the processing of how the output comes is also given below:

As indicated in the diagram above, the first three statements of the output come from the left recursive call made from within the function toh(3, A, B, C) and the output for n = 3 (i.e. 4th line of the output comes from the inorder section of the function toh(3, A, B, C). The subsequent 3 lines come from the right recursive call for the function toh(3, A, B, C).

For a video version of the dry run provided above, you might refer to the video given below from 13:00 onwards:

https://youtu.be/QDBrZFROuA0?t=780

You may go to the following link for an animated version of the logic flow provided above pictorially: http://towersofhanoi.info/Animate.aspx

This is all from our side for this solution coders, Happy Coding ahead!