CODEWITHSUNDEEP
javaalgorithmrecursion
Lin Ma
Lin Ma

Reputation: 10139

Towers of Hanoi solution issue

I am debugging some solutions for Towers of Hanoi problem and have always found one confusing rule. I think that there is a restriction stating that "a disk is slid off the top of one rod onto the next rod".

My question is, if line 45 works, which means the "buffer" rod is next to the current rod, the "destination" rod should not be next to the current rod. This means line 46 is not correct since we move to a rod to a position not next to that of the current rod.

But it seems the only solution? If anyone could clarify the confusion, it would be great.

Here is the code that I am debugging: 

 public static void main(String[] args) {
    int n = 5;
    Tower[] towers = new Tower[n];
    for (int i = 0; i < 3; i++) towers[i] = new Tower(i);
    for (int i = n - 1; i >= 0; i--) towers[0].add(i);
    towers[0].moveDisks(n, towers[2], towers[1]);
}

public class Tower {
    private Stack < Integer > disks;
    private int index;
    public Tower(int i) {
        disks = new Stack < Integer > ();
        index = i;
    }

    public int index() {
        return index;
    }

    public void add(int d) {
        if (!disks.isEmpty() && disks.peek() <= d) {
            System.out.println(“Error placing disk” + d);
        } else {
            disks.push(d);
        }
    }

    public void moveTopTo(Tower t) {
        int top = disks.pop();
        t.add(top);
        System.out.println(“Move disk” + top + “from” + index() + “to” + t.index());
    }

    public void print() {
        System.out.println(“Contents of Tower“ + index());
        for (int i = disks.size() - 1; i >= 0; i--) {
            System.out.println(““ + disks.get(i));
        }
    }

    public void moveDisks(int n, Tower destination, Tower buffer) {
        if (n > 0) {
            moveDisks(n - 1, buffer, destination);
            moveTopTo(destination);
            buffer.moveDisks(n - 1, destination, this);
        }
    }
}

Thanks in advance, Lin

Upvotes: 0

Views: 381

Answers (2)

Sumeet
Sumeet

Reputation: 8282

The tower of hanoi problem is a simple 3 step problem using recursion.There are three rods:

start , buffer and the destination

Step 1: Move n-1 disks from start to buffer rod.

Step 2: Move the nth disk from start to destination.

Step 3: Move the n-1 disks from buffer to destination.

That said, this can be very easily written in java.

class Toh
{
 public static void main(String []args)
 {
  int n=5;
  toh(n,1,2,3);//move n disks from rod 1 to 3 using 2
 }
 public static void toh(int n,int start,int buffer,int destination)
 {
  if(n<1)
   return;
  toh(n-1,start,destination,buffer);//step 1
  System.out.println("disk moved from rod "+start+" to "+destination);//step 2
  toh(n-1,buffer,start,destination);//step 3
 }
}

Upvotes: 1

invisal
invisal

Reputation: 11171

There is no such rule as A disk is slid off the top of one rod onto the PHYSICALLY next rod. You can move a disk from one rod to another rod as long as

  • You move one disk at the time
  • No disk may be placed on the top of the smaller disk
  • And you can move the upper disk of the current rod to the top of the destination rod.

So it does not require the tower to be PHYSICALLY NEXT to each other.

Upvotes: 2

Related Questions