Tower of Hanoi Using Recursion

Company tags: GOLDMAN SACHS, OYO ROOMS, SAMSUNG..etc

The tower of Hanoi is a famous puzzle where we have three rods and N disks. The objective of the puzzle is to move the entire stack to another rod. You are given the number of discs N. Initially, these discs are in the rod 1. You need to print all the steps of discs movement so that all the discs reach the 3^rd rod. Also, you need to find the total moves.
Note: The discs are arranged such that the top disc is numbered 1 and the bottom-most disc is numbered N. Also, all the discs have different sizes and a bigger disc cannot be put on the top of a smaller disc. Refer the provided link to get a better clarity about the puzzle.

Input:
The first line of input is T denoting the number of testcases. T testcases follow. Each testcase contains a single line of input containing N.

Output:
For each testcase, print the steps and the total steps taken. Please see the example output to see the steps format.
Please take care of the case of the letters.

Your Task:
This is a function problem. You only need to complete the function toh that takes following parameters: N (number of discs), Src (The rod number from which we move the disc), dst (The rod number to which we move the disc),helper (The rod that is used as an helper rod), moves (reference to the moves variable to store total moves) and prints the required moves. The total number of moves are printed by the driver code.

Expected Time Complexity: O(2^N).
Expected Helper Space: O(N).

Constraints:
1 <= T <= 16
1 <= N <= 16

Example:
Input:
2
2
3
Output:
move disk 1 from rod 1 to rod 2
move disk 2 from rod 1 to rod 3
move disk 1 from rod 2 to rod 3
3
move disk 1 from rod 1 to rod 3
move disk 2 from rod 1 to rod 2
move disk 1 from rod 3 to rod 2
move disk 3 from rod 1 to rod 3
move disk 1 from rod 2 to rod 1
move disk 2 from rod 2 to rod 3
move disk 1 from rod 1 to rod 3
7

Explanation:
Testcase 1: For N=2 , steps will be as follows in the example and total 3 steps will be taken.
Testcase 2: For N=3 , steps will be as follows in the example and total 7 steps will be taken.

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) 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.
3) No disk may be placed on top of a smaller disk.

We will solve it using recursion by doing 3 simple steps given below:

1.First we will move N-1 stacks form source rod to helper rod simply by calling recursive function.

towerOfHoni( n-1,  src, helper, dst)

2. In second Step we will move the n’th stack from source rod to destination rod using helper rod.

towerOfHoni(1,  src,  dst, helper)

3. In last step we will move all n-1 stacks from helper rod to the destination rod using source rod.

towerOfHoni( n-1,  helper,  dst, src)

So let’s see the code implementations:

package recursion;

import java.util.Scanner;

public class TowerOfHoni {
	static long moves = 0;
	
	static void towerOfHoni(int n, int src, int dst, int helper) {
		
		if( n >= 1) {
			towerOfHoni( n-1, src, helper, dst);
			System.out.println("moves disk " +n+ " form rod"+ src + " to rod" + dst  );
			moves++;
			
			towerOfHoni(n-1, helper, dst, src);
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t-- != 0) {
			int n = sc.nextInt();
			
			towerOfHoni(n, 1, 3, 2);
			System.out.println(moves);
			
		}
		
		
				
				

	}

}

Hope you guys understand the solution of tower of honi in java using recursion.

For practicing the question link is given:https://practice.geeksforgeeks.org/problems/tower-of-hanoi/0

Thanks for reading…!

Happy Coding..!

Thank You…!