/* hanoitowers13.cpp solves the Towers of Hanoi puzzle recursively.
 *
 * Input:  numDisks, the number of disks to be moved
 * Output: a sequence of moves that solve the puzzle
 ******************************************************************/

#include <iostream>

void Move(int n, char source, char destination, char spare);

int main()
{
   const char PEG1 = 'A',              // the three pegs
              PEG2 = 'B',
              PEG3 = 'C';

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

   cout << "Enter the number of disks: ";
   int numDisks;                        // the number of disks to be moved
   cin >> numDisks;
   cout << endl;

   Move(numDisks, PEG1, PEG2, PEG3);   // the solution

   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)                                 // anchor
      cout << "Move the top disk from " << source << " to " 
           << destination << endl;
   else
   {                                          // inductive case
      Move(n-1, source, spare, destination);
      Move(1, source, destination, spare);
      Move(n-1, spare, destination, source);
   }
}