/* This program solves the Towers of Hanoi puzzle recursively.

   Input:  NumDisks, the (int) number of disks to be moved
   Output: A sequence of moves that solves the puzzle
-------------------------------------------------------------------------*/

#include <iostream.h>

void Move(int, char, char, char);      // the function to solve the puzzle

int main(void)
{
   const char                          // the three pegs
      Peg1 = 'A',
      Peg2 = 'B',
      Peg3 = 'C';

   cout << "\nThis program solves the Hanoi Towers puzzle.\n";

   int
      NumDisks;                        // the number of disks to be moved

   cout << "\nPlease enter the number of disks: ";
   cin >> NumDisks;

   Move(NumDisks, Peg1, Peg3, Peg2);   // the solution

   cout << '\n';
   return 0;
}

/* Move is a recursive function to solve the Hanoi Towers puzzle.

   Receive: N, the number of disks to be moved;
            Source, the needle the disks are to be moved from,
            Destination, the needle the disks are to be moved to, and
            Spare, the needle that can be used to store disks
              temporarily
------------------------------------------------------------------*/

void Move(int N, char Source, char Destination, char Spare)
{
   if (N <= 1)											// base case
      cout << "\nMove the top disk from " << Source << " to "
           << Destination;
   else
   {														// inductive case
      Move(N-1, Source, Spare, Destination);
      Move(1, Source, Destination, Spare);
      Move(N-1, Spare, Destination, Source);
   }
}