Algorithm explanation

[Lindsey Brooks]

Hello everyone. Does anyone mind explaining what is going on in the "solvepuzzle"method? I'm really confused.
Thanks a lot.

import java.util.Scanner;

public class RecursiveTowerofHanoi
{
 
	public static void main(String args[]) 
    {
		System.out.println();
		
        System.out.print("Enter number of discs: ");
        int numdisc = new Scanner(System.in).nextInt();	

		solvepuzzle(numdisc,"Base1","Base2","Base3");
		
    } 		
 	

	public static void solvepuzzle(int numdisc, String Base1, String Base2, String Base3)
	{
       if (numdisc == 1) 
	   {
           System.out.println(Base1 + " to " + Base3);
       }
	   else 
	   {
           solvepuzzle(numdisc - 1, Base1, Base3, Base2);

           System.out.println(Base1 + " to " + Base3);
		   
           solvepuzzle(numdisc - 1, Base2, Base1, Base3);	   
		   
       }	   
		
	 
	}
}

[Knute Snortum]

In a broad overview, the program has a recursive method.  The method is working with the idea that the solution can be broken down based on how many discs are in the puzzle.  If there is only one disc, the solution is easy.  Now what if there are two discs?  The idea is to solve one disc less and the discs rearranged, solve for one disc, then again solve for one disc less and the discs arranged another way.

Why this works can best be seen by solving the puzzle with two pennies and three squares written on a piece of paper.   Once you understand two pennies, three and up are solved exactly the same way.

[Lindsey Brooks]

 

[Norm Radder]

The code needs some comments describing why it is doing things in the order it does them.  For example what determines the order of the bases in the calls to solvepuzzle?  What is the difference between the 3 bases?

[Lindsey Brooks]

Norm Radder wrote: ...what determines the order of the bases in the calls to solvepuzzle?

That's the question.

[Junilu Lacar]

Norm Radder wrote:The code needs some comments describing why it is doing things in the order it does them.

Comments are good but you could use better names that clearly reflect the purpose of the variables/paramters.  The method name could also be improved.

/* 
 * Recursive solution to the Tower of Hanoi.
 *
 * Move a tower with the given height from the 
 * start pole to the end pole using the middle pole
 * as an intermediate destination.
 */
public static void moveTower(int height, String start, String using, String end) {
    ...
}

As described in this article: http://arlobelshee.com/good-naming-is-a-process-not-a-single-step/ selection of good names is a process. Further experimentation might lead to these choices:

public static void moveTower(int height, String from, String using, String to) { ... }

public static void moveTower(int height, String source, String using, String target) { ... }

public static void moveTower(int height, String origin, String via, String target) { ... }

You may have other preferences but that last one is probably what I'd settle on using.

This page http://www.javawithus.com/programs/towers-of-hanoi shows you other naming options and gives a detail explanation of the algorithm.

[Henry Wong]

As a side question, do you know what a Tower of Hanoi puzzle is?  I actually once found one years ago in some small quaint town while on vacation. Part of me regrets not buying it, but the other part know how tedious the solution is, and that I will never do it the correct way...

Henry

[Junilu Lacar]

Henry Wong wrote:
As a side question, do you know what a Tower of Hanoi puzzle is?  I actually once found one years ago in some small quaint town while on vacation. Part of me regrets now buying it, but the other parts know how tedious the solution is, and will never do it the correct way.

I assume you meant to write "Part of me regrets not buying it, ... "

You don't strike me as one who would while away time just to know when the world is going to end anyway.    

[Lindsey Brooks]

That's the Tower of Hanoi  

Still don't understand the algorithm in the code.  

[Stephan van Hulst]

For me the tower of Hanoi is the most elegant example of recursion I can think of.

Lindsey, the second image you posted is EXACTLY what's wrong with most explanations, and why people don't get recursion. You need to forget about the individual movements, and think of the bigger picture. This is a much better explanation, I think:

Initial case:

|_      |        |
|__     |        |
|___    |        |
|____   |        |

Recursive step:

|       |        |
|       |_       |
|       |__      |
|____   |___     |         (Move a smaller tower with the exact same algorithm)

Work reducing step:

|       |        |
|       |_       |
|       |__      |
|       |___     |____     (Reduce the amount of work to be done by moving a disk to its final location)

Recursive step:

|       |        |_
|       |        |__
|       |        |___
|       |        |____     (For this particular problem, we need to perform the recursive step a second time)


Understanding recursion lies in believing that the recursive step "just works".

[Norm Radder]

Another point that comments could explain is how the algorithm enforces not moving a larger disc onto a peg over a smaller disc.

[Piet Souris]

It doesn't. The rule at hand is determined by the ordering of the original pillar.

[Junilu Lacar]

I have to side with Piet on this. The fact that the rule about never putting a larger disk on top of a smaller one is never violated seems like something that naturally comes free with the approach rather than the algorithm "enforcing" the rule. To say the latter seems to suggest there's a conscious effort to ensure the rule isn't broken or that there exists a condition which, if not explicitly accounted for by the algorithm, would cause it to fail, which there isn't.

[Stephan van Hulst]

Disagree again.

The original code has no constraints. It says nothing about allowing larger discs being placed on smaller ones. We all recognize it as the tower of Hanoi puzzle because we've been there.

The original code works, but I could write a piece of code that achieves the same thing much more easily by stacking the discs upside down on the second peg, and then restacking them upside down again a second time on the third peg.

In fact, the original code doesn't even have a goal. It solved a puzzle for which we don't know the outline.

[Junilu Lacar]

Not sure who or what you're disagreeing with, Stephan.  

[Stephan van Hulst]

I disagree with the position that you and Piet are taking in regards to Norm.

The algorithm says nothing about having to avoid placing a larger disc on a smaller one. Norm is pointing out that comments should make this clear.

Piet mentions that it's clear from the ordering of the initial pillar. You're siding with him. I disagree.

Never mind, I misread what everyone said. I agree with Norm that things could have been made clearer with comments. I agree with you and Piet that nothing is violated. The confusion stems because there wasn't a problem outline in the first place, and we assumed a problem because we're all familiar with the towers of Hanoi.

[Norm Radder]

Boy, you guys must really be bored.  I'm still working on understanding how the algorithm works.  I reworked the code a bit to validate it and show more details about its moves.

import java.util.*; //Scanner;
 
public class RecursiveTowerofHanoi
{
 static class Tower {
   public String name;
   Stack<Integer> stack = new Stack<>();    // holds the discs on this tower
   int count = 0;    // keep track of items in the stack

   Tower(String name) {
     this.name = name;
   }
   //  This constructor for loading some disks at startup
   Tower(String name, int numDisks) {
     this.name = name;
     // Load stack /  Stack is LIFO so add 1 last
     // The size of the disc is its value
     for(int i = numDisks; i > 0; i--) {
       stack.push(new Integer(i));
     }
   }

   //  Pass through Stack methods
   void push(Integer i) {
    //  Check that i is smaller than top
     if(!stack.empty()) {
       if(stack.peek().compareTo(i) < 0)  {
          System.out.println(">>> " + i + " over "+ stack.peek());
       }
     }
     stack.push(i);
     count++;
   }
   Integer pop() {
     return stack.pop();
   }
   Integer peek() {
     if(!stack.empty()) count--;
     return stack.peek();
   }

   int size() { return count;}

   public String toString() {
      return stack.toString();
   }
 }  // end Tower class
  
   //=============================================
    public static void main(String args[]) 
    {
        System.out.println();
         
        System.out.print("Enter number of discs: ");
        int numdisc = 6; //new Scanner(System.in).nextInt();   // 3->7, 4->15, 5->31, 6->63    2^n-1

        Tower origin = new Tower("origin", numdisc);
 
        System.out.println("origin="+origin);    // Show origin before the moves
        Tower target = new Tower("target");

        moveDisks(numdisc,origin, new Tower("via"), target);
        System.out.println("target="+target +" nbrMoves="+nbrMoves);    // show target after the moves
         
    }  // end main()      
     
 
    static int nbrMoves = 0;

    public static void moveDisks(int numdisc, Tower origin, Tower via, Tower target)
    {
       if (numdisc == 1) 
       {
           Integer movee = origin.pop();
           System.out.println("moving "+ movee +" from "+origin.name + " to " + target.name);
           target.push(movee);
           nbrMoves++;
       }
       else
       {
           moveDisks(numdisc - 1, origin, target, via);
 
           Integer movee = origin.pop();
           System.out.println("moving "+ movee +" from "+origin.name + " to " + target.name);
           target.push(movee);
           nbrMoves++;
            
           moveDisks(numdisc - 1, via, origin, target);
       }     
         
      
    }
}

Some considerations about the order of moves:
if one disc - first (and only) move is origin to target tower
if two discs - first move is to the via tower

Does this make a rule on where to make the first move?

[Junilu Lacar]

Norm, I suspect you'll just confuse yourself more with that code you wrote and the way you seem to be trying to understand it from the top down. Stephan illustrated the best way to understand the algorithm: a big problem that you break down into similar but increasingly smaller problems until you get to the trivial case.

To move a tower of 4 disks, first move a smaller tower of 3 disks to the intermediate pole, then move the bottom disk to the target pole (a trivial step) then move the 3-disk tower to the target pole.

To move a tower of 3 disks, first move a smaller tower of 2 disks ...

To move a tower of 2 disks, first move a smaller tower of 1 disk ...

At each recursive step, you basically start with a new problem and forget there's actually any other disks involved besides the ones in the current smaller tower.

[Ganesh Patekar]

Junilu Lacar wrote:To move a tower of 4 disks,....

Is this how you meant? It completes in 15 moves.

[Stephan van Hulst]

That's what happens per iteration, but to understand how recursion works it's important not to look at each step in order. First look at steps 0 and 7. That's where we move a tower of size 3 one peg to the right. In step 8, we move the bottom disc to the rightmost peg, and finally in step 15 we move the tower of size 3 on top of the rightmost peg as well.

So how do we move a tower of size 3 one peg to the right? Easy, we first move a tower of size 2 to the last peg (step 3), move the next disc to the second peg (step 4), and then move the tower of size 2 on top of the second peg as well.

So how do we move a tower of size 2? First we move a tower of size 1... etc. etc.

This is recursion. Divide the problem into smaller problems that you can solve with the same algorithm.

[Junilu Lacar]

If you output messages in a prefix way (as opposed to infix or postfix), you can pretty much get the full logical breakdown as Stephan describes. Below is what you would have and I have annotated the items with the step #s from Ganesh's excellent diagram. Disks are numbered 1 to 4 from smallest to biggest. The items that are bolded are where you actually move a disk; ones that are not bolded is where recursion occurs. If you hold your finger over the screen (starting from the top) as you trace through the step number annotations in numerical sequence, you'll get an idea of what's happening with the stack pointer as you go up and down the recursion levels.


How do you move a tower of 4 disks from pole 1 to pole 3? (step 0)
1a. Move tower of 3 disks from 1 to 2 (step 7)
1b. then move disk 4 from 1 to 3 (step 8)
1c. then move tower of 3 disks from 2 to 3 (step 15)

How do you move a tower of 3 disks from pole 1 to pole 2? (subtask 1a, from step 0)
2a. Move tower of 2 disks from 1 to 3 (step 3)
2b. then move disk 3 from 1 to 2 (step 4)
2c. then move tower of 2 disks from 3 to 2 (step 7)

How do you move a tower of 2 disks from pole 1 to pole 3? (subtask 2a, from step 0)
3a. Move tower of 1 disks from 1 to 2 (step 1)
3b. then move disk 2 from 1 to 3 (step 2)
3c. then move tower of 1 disks from 2 to 3(step 3)

How do you move a tower of 2 disks from pole 3 to pole 2? (subtask 2c, from step 4)
4a. Move tower of 1 disks from 3 to 1 (step 5)
4b. then move disk 2 from 3 to 2 (step 6)
4c. then move tower of 1 disks from 1 to 2 (step 7)

How do you move a tower of 3 disks from pole 2 to pole 3? (subtask 1c, from step 8)
5a. Move tower of 2 disks from 2 to 1 (step 11)
5b. then move disk 3 from 2 to 3 (step 12)
5c. then move tower of 2 disks from 1 to 3 (step 15)

How do you move a tower of 2 disks from pole 2 to pole 1? (subtask 5a, from step 8)
6a. Move tower of 1 disks from 2 to 3 (step 9)
6b. then move disk 2 from 2 to 1 (step 10)
6c. then move tower of 1 disks from 3 to 1 (step 11)

How do you move a tower of 2 disks from pole 1 to pole 3? (subtask 5c, from step 12)
7a. Move tower of 1 disks from 1 to 2 (step 13)
7b. then move disk 2 from 1 to 3 (step 14)
7c. then move tower of 1 disks from 2 to 3 (step 15)

[Junilu Lacar]

Here's how you would generate those messages (sans annotations in parens):

private static int step;
 
private static void hanoi() {
	step = 1;
	moveTowers(4, 1, 2, 3);
}

private static void moveTowers(int n, int origin, int via, int target) {
	if (n > 1) {
		System.out.printf("How do you move a tower of %d disks from pole %d to pole %d?%n", n, origin, target);
		System.out.printf("%da. Move tower of %d disks from %d to %d%n", step, n-1, origin, via);
		System.out.printf("%db. then move disk %d from %d to %d%n", step, n, origin, target);
		System.out.printf("%dc. then move tower of %d disks from %d to %d%n%n", step, n-1, via, target);
		step++;
		moveTowers(n-1, origin, target, via);
		moveTowers(n-1, via, origin, target);
	} 
}

[Piet Souris]

And it goes to show that the ordering of the pile has no effect whatsoever on the output.
The algo blindly does its work.

Maybe Ganesh can produce an identical drawing, but this time with a randomly ordered pile, performing the exact same moves, just for illustration purpose.

[Junilu Lacar]

Piet, I assume by "randomly ordered pile" you mean that you could start with the tower at pole 3 and try to move it to pole 1 or pole 2, or any other random selection of origin, target, and intermediate pole. That's right, the pole #s don't matter; you can start and end with any two poles and the result will basically be the same.

[Piet Souris]

hi Junilu,

no, I mean that you could start with a pile where the largest disc is in the middle, on top of the smallest one, et cetera.
What you get is an identically ordered pile, on another pole.

We're so used to start with this nicely ordered pile in the TOH, that we tend to forget that the algo was derived from the rule that only a smaller disc could be placed on top of a larger. But having this algo now, that ordering is in fact irrelevant. I think we all mean the same, but this "mother of all recursion examples" keeps being confusing!  And that makes it an evergreen    

[Norm Radder]

algo was derived from the rule that only a smaller disc could be placed on top of a larger.

I'm still having problems seeing how the algo was designed to follow that rule.  Without that rule, a simpler algo would be:  Move all from origin to via and then move all from via to target.
Another value that is not used when a person does the moves manually is the numdiscs variable.  With my rewrite of the code using Stacks, could the algo use the contents of the Stacks vs numdiscs to control its execution?  The use of that variable needs tobe explained for the OP and me to understand the algo.

[Junilu Lacar]

Take the first breakdown of the problem:  Move 3 disks from pole 1 to pole 2, move disk 4 to pole 3, then move the 3 disks from pole 2 to pole 3.

Assuming the subtasks that move 3 disks never breaks the "no larger disk on top of a smaller one" rule, then this breakdown and all its subtasks never break that rule. When drilling down into the subtasks, you basically forget that you have any other disks besides the ones in the current subset and you still don't have to worry about breaking the "no larger on smaller" rule.

I guess Piet's point is that if you ignore the "no larger on smaller rule" and you have the same numbering of the disks but changed their sizes, the order in which the disks will be moved by this particular algorithm will be the same regardless.  Say for example, if disk 1 was the biggest, disk 3, the second biggest, then disk 4, then disk 2 being the smallest. If you still stack these as disk 1, 2, 3, 4 from top to bottom then the textual description I generated a few posts ago would still correctly describe the solution.

[Piet Souris]

Well, the original problem was:

given a pile of discs, with the largest at the bottom and the smallest at the top, move the whole pile to another pole, maintining the ordering of course. This must be done one disc at a time, and with the proviso that we can only put a smaller disc on top of a larger disc.

Now, we must move the largest disc, sooner or later, and the only way to do so is to clear the way for that disc. So, move all the N - 1 smaller discs to the spare, then we can move the largest one to the target pole..
But then we're not finished: we still must move the N - 1 discs to the target pole as well. And that involves moving N - 1 discs to another pole, in essence are we now facing the same problem, albeit that we are nearer to our base case.

So, that is what the three line algo is doing: moving N - 1 discs to the spare, moving the largest one to the target, and moving the N - 1 discs also to the target.

And then we must read Stephans remark: since this whole recursion is way too complex for a human to follow, we have no alternative than to believe that it works! (well, after much testing, of course!).

And as a bonus (which is easily proven by induction): if we need f(N) moves to move a pile of N discs, then for a pile of N + 1 discs, we need: f(N) + 1 + f(N) moves, so we get the recurvie relation:

f(N + 1) = 2 * f(N) + 1.

And that boils down to a total of 2^N - 1.

[Ganesh Patekar]

Thank you Stephan, Junilu and Piet for clarification.   Yes It is easy to sort these disks in pictorial form but not easy to understand practically by tracing how these values gets swapped as It uses stacks. It's been more than 7-8 hours I'm trying to understand how these value gets assigned to each other.

Piet Souris wrote:Maybe Ganesh can produce an identical drawing, but this time with a randomly ordered pile, performing the exact same moves, just for illustration purpose.

You mean to say It should start with this?

[Junilu Lacar]

Ganesh Patekar wrote:You mean to say It should start with this?

No, Piet means something like this:

.   ===|=== 
.     =|=
.  ====|====
.    ==|==

Still start with all disks on one pole but not ordered by size

[Ganesh Patekar]

Junilu Lacar wrote:Still start with all disks on one pole but not ordered by size

Ohh! you mean all discs will be on one pole suppose all above discs are on pole 1 but in this order 3 at top then 2 then 4 and at last 1. Am I correct ?

[Norm Radder]

These are interesting comments:

this whole recursion is way too complex for a human to follow, we have no alternative than to believe that it works!  

Assuming the subtasks that move 3 disks never breaks the "no larger disk on top of a smaller one" rule

I don't see where my question about why the numdisc variable is used is answered
or why these method calls are in the code for when numdisc not equal to 1:

           moveDisks(numdisc - 1, origin, target, via);    //   <<< swap via and target
 //...
           moveDisks(numdisc - 1, via, origin, target);    //  <<< swap origin and via

[Junilu Lacar]

Ganesh Patekar wrote:not easy to understand practically by tracing how these values gets swapped as It uses stacks. It's been more than 7-8 hours I'm trying to understand how these value gets assigned to each other.

Think of the roles the pole plays in each iteration.  A pole is either the origin, the target, or the spare/via pole. These roles change from one iteration to the next and each pole will play only one role in any given iteration.

Ging back to my textual description:

Study how the recursive calls are made because they reflect how the roles of the poles are changing from one level or recursion to the next.

When you start with the 4-disk tower, pole 1 is the origin, pole 2 is the spare, pole 3 is the target. The top-level call to entire solution is moveTower(4, 1, 2, 3). This starts the recursion.

When you do the first breakdown, the call becomes moveTower(n-1, origin, target, via) --> moveTower(3, 1, 3, 2)

Notice how the roles that two of the poles play changed. When moving the subset with 3 disks, Pole 2, which was initially the spare pole, is now designated as the target pole. Pole 3, which was initially the target, is now designated as the spare.

[Junilu Lacar]

Norm, in recursion, there's what you call the degenerate case, i.e. the trivial case which marks the end of the need to recurse further.  In this problem, the degenerate case is when the tower is only 1 disk high. When you only have one disk, you just move it straightaway from the origin pole to the target pole.  When N != 1, then you have a recursive case which can be broken down further, therefore you recurse and pass in the number of disks in the smaller subset that needs to be moved first, hence you pass N-1 to the next recursive call.

Generally, you have this:

How to move N disks from origin to target using spare?
a. Move subset of N-1 disks from origin to spare
b. Move the remaining disk from origin to target
c. Move subset of N-1 disks from spare to target

If you frame the degenerate case in terms of the above, you get

How to move 1 disk from origin to target using spare?
a. Move subset of 0 disks from origin to spare
b. Move the remaining disk from origin to target
c. Move subset of 0 disks from spare to target

Since moving 0 disks is basically a NO-OP (no operation), the degenerate case becomes simply:

a. --- nothing to do ---
b. Move the remaining disk from origin to target
c. --- nothing to do ---

Or simply:

- Move the disk from origin to target.

[Ganesh Patekar]

Junilu Lacar wrote:Ging back to my textual description:

Yes sure, I will read It once again.

Study how the recursive calls are made

I found this one, explained in detail.

[Campbell Ritchie]

Good description but the code style is iffy, and I think there were two mathematical mistakes
I challenge you to find the three things I wasn't happy about.

[Ganesh Patekar]

Campbell Ritchie wrote:Good description but the code style is iffy, and I think there were two mathematical mistakes
I challenge you to find the three things I wasn't happy about.

He didn't consider:

What If n is a negative number, no validation.

What If n is 0 where 0! =1.

Variable name n rather number?

Return type should have been double Or BigInteger.

[Norm Radder]

Thanks everyone for helping with the explanations.

[Campbell Ritchie]

I could have sworn I replied on Friday, but I cannot find a copy of it.

Ganesh Patekar wrote:. . .

What If n is a negative number, no validation.

He did say that factorials were only defined for positive numbers.

What If n is 0 where 0! =1.

That was one of the things I noticed; he missed out 0! = 1. The other thing I noticed was related; I would have used 0 as the base case. In fact I would have said that the factorial is only defined for natural numbers, not integers. Since there is no such thing as a negative natural number, that would have given a simpler definition of the domain of the factorial function.

Variable name n rather number?

No, I think single‑letter arguments are all right when they do not mean anything special, so n meaning any number is OK. I prefer i, j, k, l, m, n for integers and get told off for not using x, y.

Campbell's Colleauges wrote:We're only interested in integers; we can use x and y. We're not writing Fortran.

Of course the C chappies like single‑letter names because they can save on keystrokes.

Return type should have been double Or BigInteger.

He was writing C which doesn't have a big integer type builti‑in. My problem with the code was the use of return twice, when you can save lots of keystrokes with the ?: operator. I tried some C on Friday, so I shou‍ld be able to find it and post it here. It's on a different computer, so please wait  few minutes for that code. The unsigned keyword doesn't exist in Java®, but it prevents you from using negative numbers. I shall let you work out what −64 means.

[Campbell Ritchie]

The three things I noticed were:-

1: Two returns rather than ?:

2: Using 1! as base case rather than 0!

3: Saying factorials were only defined for positive integers rather than natural numbers which include 0.

I couldn't find my factorial program in C, so had to write it again:-/* factorial program factorial.c */ #include <stdio.h> #include <stdlib.h> unsigned long int factorial(unsigned long int); int main(int argc, char **argv) {    int i = atoi(*(argv + 1));    printf("%d! = %lu\n", i, factorial(i));    return 0; } unsigned long int factorial(unsigned long int i) {    return i == 0 ? 1 : factorial(i - 1) * i; }

Campbell's Computer wrote:[critchie@computer CPrograms]$ gcc -o factorial factorial.c
[critchie@computer CPrograms]$ ./factorial 66
66! = 0
[critchie@computer CPrograms]$ ./factorial 64
64! = 9223372036854775808
[critchie@computer CPrograms]$ ./factorial 21
21! = 14197454024290336768
[critchie@computer CPrograms]$ ./factorial -64
[“forgot” to quote output ]

I shall let you explain the output for 64! and 66! and −64!