//Hanoi.java
//Describes the movement of discs to solve the Towers of Hanoi problem.

import java.util.Scanner;

public class Hanoi
{
    public static void main(String[] args)
    {
        System.out.println
        (
            "\nThis program solves the Tower of Hanoi "
            + "problem by describing the sequence\nof disc moves that "
            + "will achieve the transfer of n discs from the initial"
            + "\npost to the final post, according to the following rules:"
            + "\n\n"
            + "1. Only one disc can be moved at a time.\n"
            + "2. No disc can be placed on top of a smaller disc."
            + "\n\n"
            + "The amount of time to compute the moves increases "
            + "dramatically as the\nnumber of discs increases. For "
            + "illustrative purposes keep the number\nof discs to "
            + "four or five at most.\n"
        );

        Scanner keyboard = new Scanner(System.in);
        int n;
        System.out.print("Enter the number of discs to move: ");
        n = keyboard.nextInt();
        describeDiscMoves(n, 1, 3);
        System.out.println();
    }

    public static void describeDiscMoves
    (
        int n,
        int startPost,
        int endPost
    )
    /**
        Display the order in which disks must be moved and to which
        posts in order to move n disks from startPost to endPost.
        @param n The number of disks to be moved.
        @param startPost The post holding all disks at the start.
        @param endPost The post to which all disks must be moved.
        <p>Pre:<p>n, startPost and endPost have been initialized.
        <p>Post:<p>All moves necessary for moving n disks from
        startPost to endPost have been displayed.
    */
    {
        int tempPost;
        if (n == 1)
            System.out.println
            (
                "Move the top disc from post "
                + startPost + " to post " + endPost + "."
            );
        else
        {
            tempPost = 6 - startPost - endPost;
            describeDiscMoves(n - 1, startPost, tempPost);
            System.out.println
            (
                "Move the top disc from post "
                + startPost + " to post " + endPost + "."
            );
            describeDiscMoves(n - 1, tempPost, endPost);
        }
    }
}