Recursive

Towers of Hanoi

Pinterest LinkedIn Tumblr

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

  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
  3. 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 CaseAverage CaseWorst Case
O(logk)

Reference

  1. https://en.wikipedia.org/wiki/Tower_of_Hanoi
  2. https://www.mathsisfun.com/games/towerofhanoi.html
  3. https://www.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/a/towers-of-hanoi

Write A Comment