Tower Of Hanoi is a mathematical game. It consists of three rods and disks with different size (small, medium and large). The objective of the puzzle is to move the entire stack to another rod. It should follow
- 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
- No disk may be placed on top of a smaller disk.
Write a program to implement Tower Of Hanoi is a mathematical game
source Code
package com.dsacode.Algorithm.recursive; public class TowersofHanoi { public void solve(int n, String start, String auxiliary, String end) { if (n == 1) { System.out.println(start + " -> " + end); } else { solve(n - 1, start, end, auxiliary); System.out.println(start + " -> " + end); solve(n - 1, auxiliary, start, end); } } public static void main(String[] args) { TowersofHanoi towersOfHanoi = new TowersofHanoi(); int discs = 3; System.out.println("Number of Discs in Towers of Hanoi: " + discs); System.out.println("Solution of Towers of Hanoi: " + discs); towersOfHanoi.solve(discs, "A", "B", "C"); } }
Output
Number of Discs in Towers of Hanoi: 3 Solution of Towers of Hanoi: 3 A -> C A -> B C -> B A -> C B -> A B -> C A -> C
Algorithm Explanation
![]() | Move n-1 discs from A to B. This leaves disc n alone on peg A |
![]() | Move disc n from A to C |
![]() | Move n-1 discs from B to C so they sit on disc n |
Time Complexity
Best Case | Average Case | Worst Case |
---|---|---|
– | – | O(logk) |