Towers of Hanoi using Recursion in Java

Towers of Hanoi is a mathematical puzzle, consists of three towers (rods or pegs) and number of disks of different size which can slide on to any tower. The puzzle will start with whole disks on the one tower in the ascending order of their diameter, top one is the smallest diameter thus forming a conical shape when we look at disks on the single tower.

Rules of the Game

Only one disk can be moved to the other tower at a time.
You can’t keep larger diameter disk on top of smaller diameter disk.

Goal

Goal of the game is to move all the disks from tower A to tower C, find smallest number of disk movements required.

Algorithm

Move top n-1 disks form start pole (A) to auxiliary tower (B).
Move “n” th disk from start pole (A) to end pole (C).
Move n-1 disks from auxiliary tower (B) to end pole (C)

Above step 1 & 3, transferring the top n-1 disks, can be thought as a fresh problem and can be solved in a similar fashion.

Time and Space complexity

We devise time complexity by looking at different number of disks, which would take the minimum number of disk movements. For no.of disks =1 , moving from source to destination requires only 1 movement. Similarly, for no. of disks=2, moving top 1 disk form source to auxiliary and move left over disk on start pole to end pole and then move auxiliary tower disk to end pole, on the whole constituting minimum of 3 disk movements. For any other number of disks, no. of disk movements can be written as follows.

Number of Disks     Minimum number of disk movements

1               --->             1
2               --->             3
3               --->             7
4               --->             15

In general, Time complexity can be written as 1+2+2^2+2^3+. . . .+2^(n-1)

T(n)= 1*(2^n -1)/1 =2^n -1 : T(n) =O(2^n)

Space complexity C*n –> ?(n) , where constant C is the height of the tree for stack overhead.

Here is the implementation for towers of hanoi using recursion in java

Towers of Hanoi Implementation using Recursion in Java

package com.jminded.recursion;

public class TowersOfHanoi {

/**
 * @author Umashankar
 * {@link https://jminded.com}
 * @param args
 */
public static void moveTowersOfHanoi(int noOfDisks, int startPole, int endPole) {
if (noOfDisks == 0) {
	return;
}
int intermediatePole = 6 - startPole - endPole; 
// Because startPole + intermediatePole + endPole = 6
moveTowersOfHanoi(noOfDisks - 1, startPole, intermediatePole);
System.out.println("Move " + noOfDisks + " from " + startPole + " to "
				+ endPole);
moveTowersOfHanoi(noOfDisks - 1, intermediatePole, endPole);
}
    /**
     * 
     * @param args
     */
	public static void main(String[] args) {
		moveTowersOfHanoi(5, 1, 3);
	}
}

Output

Move 1 from 1 to 3
Move 2 from 1 to 2
Move 1 from 3 to 2
Move 3 from 1 to 3
Move 1 from 2 to 1
Move 2 from 2 to 3
Move 1 from 1 to 3
Move 4 from 1 to 2
Move 1 from 3 to 2
Move 2 from 3 to 1
Move 1 from 2 to 1
Move 3 from 3 to 2
Move 1 from 1 to 3
Move 2 from 1 to 2
Move 1 from 3 to 2
Move 5 from 1 to 3
Move 1 from 2 to 1
Move 2 from 2 to 3
Move 1 from 1 to 3
Move 3 from 2 to 1
Move 1 from 3 to 2
Move 2 from 3 to 1
Move 1 from 2 to 1
Move 4 from 2 to 3
Move 1 from 1 to 3
Move 2 from 1 to 2
Move 1 from 3 to 2
Move 3 from 1 to 3
Move 1 from 2 to 1
Move 2 from 2 to 3
Move 1 from 1 to 3