Hanoi tower trouble

Hi Jason Allow me to try to answer your question. Since I am not sure how broad of explanation do you want I will focusing in answering on your question: *why does this program move the first disk from stack 0 to stack number 2 when 2 disks are present. However, when there are 3 disks the first disk is moved from stack 0 to stack 1? *

You can read more about the history of Towers of Hanoi here

You can read more about Java recursion to solve the Towers of Hanoi here

Okay back to your question, I will answer it using real life logic. The rules of the Tower of Hanoi challenge are:

1) The monks can only move one disk at a time

2) The larger disk must be under the smaller disk

so please remember that not just the disk can only moved one at a time but also the disks size is not uniform.

next You need to remember the stack numbering convention:

0: is the start stack which all disks are originally located at the beginning of the challenge

1 : the final destination stack where all disks finally stacked accordingly

2: auxiliary stack to give spare room to maneuver the disks movements.

So the case where there are two disk which stacked in stack 0 with smaller disk is above the larger disk:

1) In order to meet the requirement that in the final destination stack (stack 1) the larger disk will be in the bottom and the smaller disk is above it we need to move the smaller disk first to auxiliary stack (stack 2)

2) Then we move the larger disk into the stack 1 which means we positioned the larger disk at the bottom of stack 1 right?

3) lastly we move the smaller disk from stack 2 to stack 1 and we finished the process.

In the case of 3 disks (small disk, medium disk, large disk):

1) we move small disk from stack 0 to stack 1 but this is not the final step

2) we move the medium disk from stack 0 to stack 2

3) we move small disk from stack 1 to stack 2 (this is not violation of the rule since the small disk is still above the medium disk).

4) we move large disk from stack 0 to stack 1 (the final destination) make it the bottom of the stack 1 (just what we want it to be).

5) we move small disk from the top of stack 2 to the stack 0

6) we move the medium disk from stack 2 to stack 1 (final destination)

7) and in the end we move the small disk from stack 0 to the top of stack 1 ( the end of the process)

As for how the program did this kind of work, well since this is recursion it will take a while to explain step by step. So I will try only to explain the 2 disk steps, is that okay?

Let's see the code:

    static void TowersOfHanoi(int disks, int from, int to, int spare) {
        if (disks == 1) {
            System.out.println("Move a disk from stack number " + from + " to stack number " + to);
        }
        else {
            TowersOfHanoi(disks-1, from, spare, to);
            System.out.println("Move a disk from stack number " + from + " to stack number " + to);
            TowersOfHanoi(disks-1, spare, to, from);
        }
    }

the key here is to pay attention to the order of the parameters each time the recursion process happens. there are three kind of order of parameters for the TowerOfHanoi method calls within the method it self (which is known as recursion):

1) TowersOfHanoi(int disks, int from, int to, int spare) : which means move from stack 0 (from) to stack 1 (to)

2) TowersOfHanoi(disks-1, from, spare, to); which means move from stack 0 (from) to stack 2 (spare)

3) TowersOfHanoi(disks-1, spare, to, from); which means move from stack 2 (spare) to stack 1 (to)

If you pay attention there are only these 3 steps used in solving Tower of Hanoi challenge.

so for the case where int disk =2, int from = 0, int to = 1, int spare = 2 here is what's going on.

1) The parameters arrived in the TowersOfHanoi method and were asked if disk == 1 the answer is FALSE then we go to ELSE

2) in the ELSE section we arrived in the first recursion which calls the method the TowerOfHanoi but this time the parameters change right? TowersOfHanoi(disks-1, from, spare, to);

-> int disk is now disk -1 = 1

-> int from is still from = Stack 0

-> int to now switches with spare = Stack 2 (meaning the destination for the movement of the disk is stack 2 not stack 1)

3) that recursion calling for a new session and the new parameters arrived and asked if disk == 1? the answer is TRUE

4) then because it is TRUE we print Move disk from Stack 0 to Stack 2. This printing process end this session and we are going back to the previous session.

5) we back at the older session after the recursion the next order is to print System.out.println("Move a disk from stack number " + from + " to stack number " + to); BUT REMEMBER the parameters used here is the older parameters:

-> int disk = 2

-> int from = stack 0

-> int to = stack 1

Therefore it will print Move disk from Stack 0 to Stack 1

6) Lastly for this first session we meet another recursion which changes parameters to be: TowersOfHanoi(disks-1, spare, to, from);

-> int disk is now disk -1 = 1

-> int from is now spare = Stack 2

-> int to still the same = Stack 1

7) Thus we open yet again new session with method TowerOfHanoi and we were asked again if disk==1? Answer is TRUE

8) So we must print Move disk from stack 2 to Stack 1 this ended this session and we are going back to our first session

9) After this the first (and oldest session) is also over... Thus we print three things:

-> Move disk from Stack 0 to Stack 2

-> Move disk from Stack 0 to Stack 1

-> Move disk from stack 2 to Stack 1

That is the same result as how we solve the two disk stack Towers of Hanoi right?

Sorry if this is too long. As I said I am not sure how deep the explanation you wanted. I hope this can help you a little. For the three disk stack Towers of Hanoi I hope you can use this explanation as base for figuring out how the code is doing to solve the problem