CODEWITHSUNDEEP
javaalgorithmrecursiontowers-of-hanoi
Silverfin
Silverfin

Reputation: 495

Recursive approach to solving the Towers of Hanoi puzzle

I'm trying to work out the "towers of hanoi" problem, which moves stacks of disks organized from smallest to largest from a start stack to a destination stack, by means of an auxiliary stack without ever placing a larger disk on top of a smaller disk.

I was given the algorithim:

If numberDisks ==  1:
   Display “Move the top disk from  S to D”.
Else
  Move(numberDisks -1, ‘S’, ‘A’, ‘D’);
  Move(1, ‘S’, ‘D’, ‘A’);
  Move(numberDisks -1, ‘A’, ‘D’, ‘S’);

However this seems to differ from most other examples which seem to work without using Move(1, ‘S’, ‘D’, ‘A’); in the recursive function.

As my code stands, I seem repeat the base case for every move, and im not sure how to structure my print statements to give the proper output which should look like:

Move disk 1 from S to D
Move disk 2 from S to A
Move disk 1 from D to A
Move disk 3 from S to D
Move disk 1 from A to S
Move disk 2 from A to D
Move disk 1 from S to D

When trying to move 3 disks.

// Recursively solve Towers of Hanoi puzzle

public static void main(String[] args) {
    if (handleArguments(args)) {
        System.out.println("numDisks is ok");
        int numDisks = Integer.parseInt(args[0]);

        Move(numDisks,'s', 'a', 'd' );
    }
}

// recursive case
public static void Move(int disks, char start, char aux, char destination) {

    // base case
    if (disks == 1) {
        System.out.println("Move disk 1 from S to D");

        // if number of disks is 2 or greater
    } else if(disks > 1) {
        Move(disks - 1, start, aux, destination);
        System.out.println("move disk " + disks + " from " + start + " to " + destination);
        Move(1, start, destination, aux);
        Move(disks - 1, aux, destination, start);
    }
}

Upvotes: 1

Views: 1685

Answers (1)

moreON
moreON

Reputation: 2008

First thing: Understand the algorithm for moving n discs (from S to D, with A)

  1. If there is only one disc to move, just move it then stop*.
  2. Move n - 1 discs from S to A, with D.
  3. Move nth disc from S to D
  4. Move n - 1 discs from A to D, with S.

*Equally: If there are 0 discs, just stop. (Some would argue that this is the superior termination condition because, in your code, it will prevent the print statement when there is one from being a special case, it will be handled naturally by the print statement you cover step 3 with. When, for example, you decide to change this method to return a list of the steps instead of printing it, this change will only have to be applied in one place)

You mention that "I seem repeat the base case for every move." If you look at your code, and compare to my statements above. You will see that you call Move(1, start, destination, aux); between my steps 3 and 4. This is why you are repeating your base case, because you are explicitly calling, repeating your base case, but it doesn't make any sense to.

The other main problem I can see: System.out.println("Move disk 1 from S to D"); will always print 'S' and 'D', in that order, when often you will need to specify a different move, ensure to use the arguments for this statement.

I don't think that there is anything else, but try it and see.

In response to the example you were given, in the start of your post. It produces subtly different output than your version.

Yours specifies (or attempts to) which size disc should be moved at each step, the example only specifies which stack to move a disc from and to, regardless of its size.

The recursive call with 1 as its argument in the middle there is to print the move instruction for moving the final disc in the stack (my step 3).

Upvotes: 1

Related Questions