/*
 * hanoi.c
 * This program solves the problem of the towers of Hanoi.
 */

#include <stdio.h>
#define MAX_LINE 80

/* Prototypes: */
int move_tower (int n, int from, int to);

int main ()
{
  char    in[MAX_LINE];
  int     n;
  int     n_moves;

  /* Read the height of the tower. */
  do
  {
    printf ("Please enter the height of the tower: ");
    scanf ("%s", in);
    n = atoi(in);
  } while (n <= 0);

  /* Move a tower of height n from the first pole to the second pole. */
  n_moves = move_tower (n, 1, 2);
  printf ("The solution requires %d moves.\n", n_moves);

  return (0);
}

/* ------------------------------------------------------------------------
 * Function: move_tower
 * Purpose : Move a tower from one pole to the other.
 * Input   : n    - The height of the tower (number of rings in it).
 *           from - The source pole.
 *           to   - The target pole. 
 * Returns : The number of moves required.
 */
int move_tower (int n, int from, int to)
{
  int     aux;
  int     n_moves;

  /* In case of a single ring, just move it from the source to the target. */
  if (n == 1)
  {
    printf ("Move ring [1] from pole no. %d to pole no. %d\n", from, to);
    return (1);
  }

  /* Since the three poles are indexed 1, 2 and 3 we can easily find the index
     of the free auxiliary pole using (1 + 2 + 3 = 6): */
  aux = 6 - from - to;

  /* Move the top (n-1) rings from the source pole to the auxiliary pole. */
  n_moves = move_tower (n - 1, from, aux);

  /* Move the buttom ring from the source pole to the target pole. */
  printf ("Move ring [%d] from pole no. %d to pole no. %d\n", n, from, to);
  n_moves++;

  /* Move the top (n-1) rings from the auxiliary pole to the target pole. */
  n_moves += move_tower (n - 1, aux, to);

  return (n_moves);
}