Tower of Hanoi

difficulty_mediumrecursion This belongs to track:: recursion and has [difficulty:: medium]. I guess it can also be considered in Stack

[Time taken:: 30mins]

Best [time complexity:: O(2^N)] for 3 disks: 2^3 = 8 steps [space complexity:: O(N)]

Constraints

• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
• No disk may be placed on top of a smaller disk.

Approach:

1. Assume there are n disks.
2. For the three rods: A, B, C, A → from rod, B is auxiliary rod, C is to rod.
3. Move n - 1 disks to rod B.
4. Move last disk from rod A to rod C.
5. Update count of n = n - 1
6. Move n - 1 rods from rod B to rod A.
7. Move last disk from rod B to rod C.

Code

 
function towerOfHanoi(n, from_rod, to_rod, aux_rod)
{
		if (n == 0)
		{
			return;
		}
		towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
		console.log("Move disk " + n + " from rod " + from_rod +
		" to rod " + to_rod+"<br/>");
		towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
	}
 
	// Driver code
	var N = 3;
	
	// A, B and C are names of rods
	towerOfHanoi(N, 'A', 'C', 'B');