Tower of Hanoi Problem

There are 3 pegs source ,auxillary and target. n disks of different sizes are given which can slide onto any peg . In the beginning all of the disks are in the source peg in the order of size with largest disk at the bottom and smallest disk at the top. We have to move all the disks from source peg to target peg such that in the end the target peg will have all the disks in the same order of size.

Rules:

1. Only one disk can be moved from one peg to another peg at a time
2.  A larger disk cannot be placed on top of the smaller disk 

Tower of Hanoi

C++ Program

#include <iostream>
#include <cstdlib>
 
static int moveCounter = 0;
void towerOfHanoi(int ndisk, char source, char auxillary, char target)
{
  if(ndisk == 1)
  {
    std::cout << "Move [" << ndisk << "]   [" << source << "] to [" <<
      target << "]" << std::endl;
    ++moveCounter;
    return;
  }
 
  //place ndisk - 1 disks from source to auxillary peg
  towerOfHanoi(ndisk - 1, source, target, auxillary);
   
  //place ndisk to target peg
  std::cout << "Move [" << ndisk << "]   [" << source << "] to [" <<
      target << "]" << std::endl;
  ++moveCounter;
 
  //place ndisk - 1 disks from auxillary to target peg
  towerOfHanoi(ndisk - 1, auxillary, source, target);
}
 
int main(int args, char *argv[])
{
  if(argv[1] == NULL)
  {
    std::cout << "ERROR: Insufficient Arguments\n";
    std::cout << "Usage: ./a.out number_of_disks\n";
    exit(-1);
  }
  int disks = atoi(argv[1]);
   
  char peg1 = 'A', peg2 = 'B', peg3 = 'C';
  towerOfHanoi(disks, peg1, peg2, peg3);
  std::cout << "Total Moves = " << moveCounter << std::endl;
}

Java Program:

public class TowerOfHanoi
{
  private static final char source = 'A';
  private static final char auxillary = 'B';
  private static final char target = 'C';
  private static int moveCount = 0;
 
  public static void main(String args[])
  {
    if(args.length < 1)
    {
      System.out.println("ERROR: Insufficient Arguments");
      System.out.println("Usage: java TowerOfHanoi number_of_disks");
      System.exit(-1);
    }
 
    int ndisk = Integer.parseInt(args[0]);
    towerOfHanoi(ndisk, source, auxillary, target);
    System.out.println("Total Moves = " + moveCount);
  }
 
  public static void towerOfHanoi(int ndisk, char source, char
      auxillary, char target)
  {
    if(ndisk == 1)
    {
      System.out.println("Move [" + ndisk + "] from [" + source +
          "] to [" + target + "]");
      ++moveCount;
      return;
    }
 
    //move ndisk - 1 disks from source peg to auxillary peg
    towerOfHanoi(ndisk - 1, source, target, auxillary);
 
    System.out.println("Move [" + ndisk + "] from [" + source +
          "] to [" + target + "]");
    ++moveCount;
 
    //move ndisk - 1 disks from auxillary peg to target peg
    towerOfHanoi(ndisk - 1, auxillary, source, target);
  }
}

Time Complexity: Let the time required for n disks is T(n). There are 2 recursive call for n-1 disks and one constant time operation to move a disk from source peg to target peg . Let it be c. Therefore, 

T(n) = T(n-1) + c + T(n-1)
T(n) = 2T(n-1) + c
T(0) = k1
T(1) = 2T(0) + c1 = 2k1 + c1
T(2) = 2T(1) + c2 = 2(2T(0)) + c2 = 2(2k1 + c1) + c2 = 4k1 + 2c1 + c2
T(3) = 2T(2) + c3 = 2(4k1 + 2c1 + c2) + c3 = 8k1 + 4c1 + 2c2 + c3

Coefficient of k1 =2ⁿ Time complexity is O(2ⁿ)  

Output

//Output with 3 pegs
Move [1]   [A] to [C]
Move [2]   [A] to [B]
Move [1]   [C] to [B]
Move [3]   [A] to [C]
Move [1]   [B] to [A]
Move [2]   [B] to [C]
Move [1]   [A] to [C]
Total Moves = 7

//output with 5 pegs
Move [1]   [A] to [C]
Move [2]   [A] to [B]
Move [1]   [C] to [B]
Move [3]   [A] to [C]
Move [1]   [B] to [A]
Move [2]   [B] to [C]
Move [1]   [A] to [C]
Move [4]   [A] to [B]
Move [1]   [C] to [B]
Move [2]   [C] to [A]
Move [1]   [B] to [A]
Move [3]   [C] to [B]
Move [1]   [A] to [C]
Move [2]   [A] to [B]
Move [1]   [C] to [B]
Move [5]   [A] to [C]
Move [1]   [B] to [A]
Move [2]   [B] to [C]
Move [1]   [A] to [C]
Move [3]   [B] to [A]
Move [1]   [C] to [B]
Move [2]   [C] to [A]
Move [1]   [B] to [A]
Move [4]   [B] to [C]
Move [1]   [A] to [C]
Move [2]   [A] to [B]
Move [1]   [C] to [B]
Move [3]   [A] to [C]
Move [1]   [B] to [A]
Move [2]   [B] to [C]
Move [1]   [A] to [C]
Total Moves = 31