Tower Of Hanoi

 



Towers of Hanoi 

The objective is to move the entire stack to any other rod, obeying these rules: 

• Only one disk can be moved at a time
• Each move consists of taking the upper disk from one rod, adding it onto another rod, on top of any disks that you may have already placed on that rod.
• But no disk can be placed on top of a smaller disk 

The recursive algorithm

• move n-1 disk from the starting pole to the pole which is neither start nor target (intermediate)
• move disk n to the target pole and then move n-1 disk from the intermediate pole to the target pole
• The n-1 disks are moved recursively 

Pseudo code:

• if ( nDisks == 1 )    return( "Do this move: fromPeg --> toPeg" ); 
• else 
• helpPeg = peg index that is not equal to fromPeg and toPeg; 
• sol1 = hanoi( nDisks-1, fromPeg, helpPeg );
• myStep = "Do this move: fromPeg --> toPeg"; 
• sol2 = hanoi( nDisks-1, helpPeg, toPeg );

How to use the solutions sol1 and sol2 to solve hanoi(nDisks, fromPeg, toPeg): 
 1. first making the moves in sol1
 2. then do myStep
 3. finally, do the moves in sol2

OUTPUT

Move 2 from 2 to 1
Move1from 3 to 1
Move 1 from 3 to 1
Move 3 from 2 to 3
Move1from 1 to 2
Move 1 from 1 to 2
Move 2 from 1 to 3
Move1from 2 to 3
Move 1 from 2 to 3

Java Code

/**
 * three poles and n disks which fit on the poles
 * All disks have different size
 * they are stacked on pole 1 in the orders of their size
 * The largest disk is on the bottom, the smallest is on the top.
 * The task is to move all disk from pole 1 to pole 3 under the following restrictions
 * Only one disk can be moved
 * A larger disk can not be placed on a smaller disk
 *
 * recursive algorithm works like the following: move n-1 disk from the starting pole
 * move disk n to the target pole and then move n-1 disk from the intermediate pole to the target pole
 *
 * n-1 disks are moved recursively
 *
 * @author ravi
 *
 */
public class TowerOfHanoi {
    /**
     * Pole are labeled 1, 2,3
     * Each disk is also labeled
     *
     * @param args
     */
    public static void main(String[] args) {
        move(4, 1, 3);
    }
    /**
     * For first (n-1) elemnet, end pole will be intermediate pole
     * And n element will be moved to last pole
     *
     * @param n
     * @param stratPole
     * @param endPole
     */
    static void move(int n, int stratPole, int endPole){
        if(n==0){
            return;
        }
        if(n==1){
            System.out.println("Move" + n + "from "+ stratPole +" to " + endPole);
        }       
        int intermediatePole = 6-endPole - stratPole;//3+2+1=6
        move(n-1, stratPole, intermediatePole);
        System.out.println("Move " + n + " from "+ stratPole +" to " + endPole);
        move(n-1, intermediatePole, endPole);
    }

}