#include <iostream>
#include <string>
using namespace std;

// file: hanoi.cpp
// author      Dietolf Ramm;  date: 11/9/97
// illustrate recursion solving Towers of Hanoi problem


void hanoi (const string& from, const string& to, const string& via, int n)
// pre:  n > 0 disks in pile "from" to be moved to pile "to"
//       with pile "via" available for intermediate storage.
//       All piles so that disk n always above disk n+k where k > 0.
// post: messages generated to show how to move disks to pile "to"
//       with intermediate use of all piles but only one disk moved at a time
//       and at all times for all n, disk n above disk n+k where k > 0. (I.e.,
//       at no time is a larger disk above a smaller disk where smaller disks
//       have smaller numbers than larger disks.)
{
    if (n == 1) // base case: only on disk in pile
	cout << "Move disk " << 1 << " from " << from << " to " << to << endl;
    else
    {
        hanoi(from, via, to, n-1);  // move disks above to alternate (via)
	cout << "Move disk " << n << " from " << from << " to " << to << endl;
        hanoi(via, to, from, n-1);  // move disks above to target (to)
    }
}


int main ()
{
   int n;

   cout << "Enter number of disks: ";
   cin  >> n;
  
   hanoi("A", "C", "B", n);

   return 0;
}


//  Initial state for n=4
//
//	A		B		C
//	|		|		|
//     (_) 1		|		|
//    (___) 2		|		|
//   (_____) 3		|		|
//  (_______) 4		|		|
//-----------------------------------------------

/*

Sample output

prompt> hanoi
Enter number of disks: 3
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

prompt> hanoi
Enter number of disks: 4
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B
Move disk 4 from A to C
Move disk 1 from B to C
Move disk 2 from B to A
Move disk 1 from C to A
Move disk 3 from B to C
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

*/