CODEWITHSUNDEEP
javaalgorithmrecursion
user564927
user564927

Reputation: 305

Tower of Hanoi Recursion Algorithm

I am having a problem understanding this Tower of Hanoi recursion algorithm:

public class MainClass {
  public static void main(String[] args) {
    int nDisks = 3;
    doTowers(nDisks, 'A', 'B', 'C');
  }

  public static void doTowers(int topN, char from, char inter, char to) {
    if (topN == 1){
      System.out.println("Disk 1 from " + from + " to " + to);
    }else {
      doTowers(topN - 1, from, to, inter);
      System.out.println("Disk " + topN + " from " + from + " to " + to);
      doTowers(topN - 1, inter, from, to);
    }
  }
}

The output is:

Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C

I don't understand how do we get:

Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A

Can someone please explain?

Thank you.

Upvotes: 2

Views: 10863

Answers (2)

Legna
Legna

Reputation: 1661

Moving a N disks tower from peg A to C is achieved by moving a N-1 (all disks but the last one) tower from A to B, then moving the Nth disk from A to C, and finally moving the tower previously moved to B, from B to C. This shall be applied any time a tower with more than one disk is moved, in the case of a 1 disk tower, you just move its only disk.

Upvotes: 9

alanmanderson
alanmanderson

Reputation: 8200

If I'm not mistaken you can move 1 disk one peg each turn correct? So you move the first disk from a to b then b to c. That is 2 moves. Then we can now move disk 2 from a to b. Now we can move disk 1 from c back to b. Right now disk 3 is on A and disk 2 and 1 are on a. Now we move disk 1 from a to b then to c. No we need to get disk 1 and 2 on disk 3 in the right order. So we clear disk 1 by moving it from B to A. This allows us to put disk 2 from B to C. Now we finish by moving disk 1 from a to b then to c and we are done.

Does that answer your question?

Upvotes: 0

Related Questions