How to call recursion with Tower of Hanoi

Question

I'm trying to resolve Tower of Hanoi problem; I wrote this code:

public class TowersOfHanoi {
   public static void main(String[] args) {
      move(5, 1, 3);
      }

   public static void move(int disks, int from, int to) {
      if (disks > 0) {
         int other = 6 - from - to; // sum of index 1+2+3=6
         System.out.println("Move disk from peg " + from + " to " + to);
         move(disks - 1, from, other);
         move(disks - 1, other, to);
         }
   }
}

but the result is wrong. The solution in my book is

public class TowersOfHanoi {
   public static void main(String[] args) {
      move(5, 1, 3);
      }

   public static void move(int disks, int from, int to) {
      if (disks > 0) {
         int other = 6 - from - to; // sum of index 1+2+3=6
         move(disks - 1, from, other);
         System.out.println("Move disk from peg " + from + " to " + to);
         move(disks - 1, other, to);
         }
   }
}

why is this? I can't understand the ORDER of these expression:

• first it run System.out.println()
• then it run move(disks - 1, from, other)
• now it run System.out.println() again or run move(disks - 1, other, to)?

and WHEN RESTART the block code? Thanx.

Answer 1

The tower of hanoi works in a way that -:

1. First you have to move n - 1 disks to the 2nd peg from 1st using 3.
2. Move the last nth disk to 3rd peg.
3. Move the n-1 disks from 2nd peg to peg 3rd peg using 1st.

The book solution is correct in. Your solution is wrong because you have moved the last disk in the beginning, this is against rule of tower of hanoi. I hope you get it.

A bit more elegant and understandable code after some modification where it works for any arbitary n. (Atleast for small values of n due to it exponential complexity)

public class TowersOfHanoi {
   public static void main(String[] args) {
      int first = 1, second = 2, third = 3;
      int disk = 5; // or take user input
      move(disk, first, third);
   }

   public static void move(int disks, int first, int second, int third) {
      if (disks > 0) {
              move(disks - 1, first, third, second); // source = first, dest = second
              System.out.println("Move disk from peg " + first+ " to " + third);
              move(disks - 1, second, first, third);  // source = second, dest = third
         }
   }
}

Answer 2

So we have n disks and 3 pegs, we want to move the disks placed in the 1st peg (the source peg) to the 3rd peg (the target peg); the concept of recursion in this case is:

1. Move all the disks recursively from 1 to n-1 above the biggest (called n) from the 1st peg to the 2nd (the spare peg), because we want to make space for the biggest disk and be able to put it in the 3rd peg. This is the first sentence move(disks - 1, from, other);

2. After have moved all the disk above the biggest we move it to the 3rd peg: as Wikipedia says this is the simple step and its the second sentence
   System.out.println("Move disk from peg " + from + " to " + to);

3. In the end move all the n-1 disks from the 2nd peg to the 3rd recursively in order to recreate the tower in the 3rd peg, and its the last sentence move(disks - 1, other, to);

This algorithm works both with even and odd n disks because its a general solving procedure, obviously the steps will change depending of the initial number of the disk.

Answer 3

The idea of the correct solution is that:

1. First you have to move the top n-1 discs from peg "from" to peg "other" recursively.
2. Then you can move the bottom disc from peg "from" to peg "to" - that's the println statement.
3. Then you have to move the n-1 discs (which were moved in step 1) from peg "other" to peg "to" recursively.

On the other hand, what you are trying to do in your incorrect solution is move the bottom disc before you moved all the discs stacked above it, which is not a valid move.