Towers of Hanoi (15 points)

Given:

n disks, all of different sizes - the size of the ith disk is i

3 pegs - A, B, C the number of pegs might change in a future version of the game

Initially, all the disks are stacked on peg A

Requirement:

Never place a larger disk on top of a smaller disk (disk 5 is larger than disk 4, etc.)

Objective:

Move the disks from peg A to peg C

Input:

n, the number of disks initially stacked on peg A; you should get n from the command line, as a command line argument; assume n < 10

Output:

Commands describing how the player should move the pegs

Example:

If 3 is input then the output should be:

MovePeg Configuration

ABC

init3 2 1

1 from A to C3 21

2 from A to B321

1 from C to B32 1

3 from A to C2 13

1 from B to A123

2 from B to C13 2

1 from A to C3 2 1

Strategy:

If there are n disks on peg A and we need to move them to peg C then we'll use peg B as a utility peg:

Move the top n-1 disks from A to B

Move the nth disk from A to C

Move the n-1 disks from B to C, using peg A as a utility

OR

If we must move n disks on the source peg to the dest peg using a utility peg:

Move the top n-1 disks from source to utility

Move the nth disk from source to dest

Move the n-1 disks from utility to dest, using peg source as a utility

Be sure to choose appropriate classes - it should require minimal changes if we desire to modify the problem to include any number of pegs (you should provide a flexible, extensible solution) or modify our strategy. Note your class cohesion and degree of coupling between classes (maximize cohesion, minimize coupling)

You are expected to think about and correctly identify the objects in this exercise. The reasons I assigned this exercise are for you:

- To get more practice programming in Java

- To think about and utilize Object Oriented Programming techniques

The second reason requires you to "think outside the box"...you must be very careful to first identify the objects in the problem space (don't discount identifying an object because you might think it's too trivial), form their associated classes, discover their associated properties (instance variables) and roles (methods).

Herein, it's extremely important to assign roles to objects based on their expertise - e.g. if you want me to drive to school then you should not do the job for me, you should ask ME to drive and I'll determine HOW to satisfy the request.

All classes should be included in a single file.

You are not asked to solve the problem for n pegs.....just be sure that if, in the future, you are asked to extend the problem to n pegs it will not require major code modifications..this requires careful thinking about the objects involved in the computation and their classes

SUBMISSION

Submit the zip file, as mentioned in Appendix A of the Reader (zip the jar file and src directory)

Q. What classes should be included?

Consider the following discussion: Are we using a disk class? I created one with a class but seem to have a lot of trouble using it. It seems to me that the answer to this question is: Is Disk an object we are using? If so, then it needs to be created, and thus needs its own class.Well, as stated in class, you would need to design a program that would be modifiable later on. A disk class would be very useful in that sense because you can create instances in the class like disk name (ex. naming a disc, Disc "abc123", instead of just Disc "1") and disc weight. Those things would insure that the program is reusable later on. Remember, in a first pass at determining classes you should consider the statement of the problem requirements. In many cases, the nouns in the statement are good candidates for classes, while the verbs are good candidates for methods in associated classes You are expected to think about and correctly identify the objects/classes in this exercise. The reasons I assigned this exercise are for you: - to get more practice programming in Java - to think about and utilize Object Oriented Programming techniques Another issue is to require you to "think outside the box"...you must be very careful to first identify the objects in the problem space (don't discount identifying an object because you might think it's too trivial), form their associated classes, discover their associated properties (instance variables) and roles (methods). Herein, it's extremely important to assign roles to objects based on their expertise - e.g. if you want me to drive to school then you should not do the job for me, you should ask ME to drive and I'll determine HOW to satisfy the request.

Q. Should we solve the problem for n pegs?

You are not asked to solve the problem for n pegs.....just be sure that if, in the future, you are asked to extend the problem to n pegs it will not require major code modifications..this requires careful thinking about the objects involved in the computation and their classes