/* hanoi.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
 *
 * Written by:   Larry R. Nyhoff
 * Adapted from program for C++: An Introduction to Computing, 2e
 *   for use in  Lab Manual for C++: An Introduction to Data Structures
 *************************************************************************/

#include <iostream>
using namespace std;

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

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

}

/* Move is a recursive function to solve the
 * Towers of Hanoi puzzle.
 *
 *  Receive: n, the number of disks to be moved;
 *           source, peg containing disk to move
 *           destination, peg where to move disk
 *           spare, peg to store disks temporarily,
 *  Output:  A message describing the move
 **************************************************/

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);
  }
}