Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

**1)** Only one disk can be moved at a time.

**2)** A disk can only be moved if it is the uppermost disk on a stack.

**3)** No disk can be placed on top of a smaller disk.

##### Example 1: Moves to solve tower of hanoi with 3 disks.

**Input:** n=3, towers: A,B,C

**Output:**

Move disk: 1 from: A to: C. Move disk: 2 from: A to: B. Move disk: 1 from: C to: B. Move disk: 3 from: A to: C. Move disk: 1 from: B to: A. Move disk: 2 from: B to: C. Move disk: 1 from: A to: C.

##### Example 2: Moves to solve tower of hanoi with 4 disks.

**Input:** n=4, towers: A,B,C

**Output:**

Move disk: 1 from: A to: B. Move disk: 2 from: A to: C. Move disk: 1 from: B to: C. Move disk: 3 from: A to: B. Move disk: 1 from: C to: A. Move disk: 2 from: C to: B. Move disk: 1 from: A to: B. Move disk: 4 from: A to: C. Move disk: 1 from: B to: C. Move disk: 2 from: B to: A. Move disk: 1 from: C to: A. Move disk: 3 from: B to: C. Move disk: 1 from: A to: B. Move disk: 2 from: A to: C. Move disk: 1 from: B to: C.

## Solutions

### Method 1: Recursion

Lets assume we have three towers: A (Source Tower), B (Auxiliary Tower), C (Destination Tower).

If there was only one disk we would have move that from A to C and thats it, this will make the base condition.

Now if there are more than 1 disk, we should remove all but 1 from A to B recursively; so that we can move remaining one biggest disk from A to C.

Now all we have to do is to move all disks (moved from A in previous step) from B to C recursively.

package com.cb.recursion; /* * Assume towers: * A (sourceTower), * B (auxTower), C (desTower) * */ public class R14_TowerOfHanoi { public static void move(int noOfDisk, char sourceTower, char auxTower, char desTower) { // if single disk in A, move it to C if (noOfDisk == 1) { moveSingleDisk(1, sourceTower, desTower); return; } // Move n-1 disks from A to B, so that the remaining last disk in A can be moved to C move(noOfDisk - 1, sourceTower, desTower, auxTower); // Move remaining disk in A to C moveSingleDisk(noOfDisk, sourceTower, desTower); // Move n-1 disks (came from A in first step) from B to C move(noOfDisk - 1, auxTower, sourceTower, desTower); } // just printing private static void moveSingleDisk(int diskNumber, char source, char dest) { System.out.println("Move disk: " + diskNumber + " from: " + source + " to: " + dest + "."); } public static void main(String[] args) { move(3, 'A', 'B', 'C'); } }

Move disk: 1 from: A to: C. Move disk: 2 from: A to: B. Move disk: 1 from: C to: B. Move disk: 3 from: A to: C. Move disk: 1 from: B to: A. Move disk: 2 from: B to: C. Move disk: 1 from: A to: C.

##### Complexity

For every disk two recursive case originates, so Time Complexity is **O(2^n)** and the Space Complexity is **O(1)**.