WRITE JAVA PROGRAMS

PLEASE FOLLOW THE RULES OF THE GAME

DEADLINE IS JUNE 14

NO RECURSION PLEASE!!!!!

PLEASE ADD COMMENTS WHEREVER POSSIBLE

You are required to design an algorithm which solves the Tower of Hanoi puzzle . You have an array of stacks (use the ListStack implementation) named rods with size 3. All three of the stacks are in the same size which is n.

At the beginning: rods[0] (first stack) is full of discs marked with positive integers from 1 to n where 1 is at the top and n is at the bottom ( i.e., you need three stacks of Integers with the first initialized to store the n Integers). The other two stacks are empty.

The goal of the puzzle: is to move all these disks from rods[0] to the third rod, rods[2], with the help of rods[1], without breaking any rules of the Tower of Hanoi puzzle.

The rules of the game are:

Only one disc may be moved at a time. Each move consists of taking the top (smallest) disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod. No disk may be placed on top of a smaller disk.

Hints: To move a stack of k discs from rod A to rod B, we first move k-1 discs from A to C, then move the remaining (kth) disc from rod A to B, and then finally move all k-1 discs on C to B. Also, if you closely examine the puzzle you will see that there is at most one legal move between any two rods.

Deliverables:

TowersofHanoi.java

- A class that has the rods, and the size n of the storage of the rods. It has a constructor that takes the towercapacity( i.e., n) and creates the new array

rods,(i.e., Stack

stacks (each with capacity n) with the first rod containing the n integers.

- Implements Boolean legalMove(int a, int b) returns true if it is legal to move a

disc from rod a to rod b. ( rods are referred to as rod 0, rod 1, rod 2)

- Implements Boolean move(int a, int b) that moves a disc from a to b after ensuring it is a legal move and prints out a sentence disc x moved from rod y to rod z with x,y, z representing the right number for the disc and the rods. It

returns false if the move is not legal.

- Implements Boolean move(int m, int a, int b, int c) moves m discs from tower

a to tower b using tower c as an intermediate storage. It prints out all the movements of the discs as they appear. It returns false if the moves are not legal. This could be because a doesn t have m discs, rod b has exceeded capacity or you are trying to store a large disc on top of a smaller one.

- Implement the method void showTowerStates() prints out the contents of the rods.

- Method void solvegame() solves the game from the initial state where all discs are stored in rods[0].

- Bonus: method void solvecurrent() solves the game at any state for the rods.

PlaytowerofHanoi.java

- Your main program that asks the user how many discs, n, (up to 6 discs) , and then asks

the user if he/she wants to play the game or see the solution.

- The program should create a new TowersofHanoi instance of the game, shows the

towers state before the game starts.

- If the user selects to play then you repeatedly ask him to select a move of one disk from

one Rod to another. You need to check if a move is legal or not and prompt the user to re- enter a legal move if it is not. The program should tell the user that he/she has lost the game after a maximum of 2^n-1 legal moves (if bonus used: and solves the game from the current state showing the user the solution). If the user solves the game the program should congratulate him/her and terminate.

- If the user chooses to see the solution then the program should solve it and display the steps.

- You cannot use recursion in solving this problem (i.e., no method can call itself).

- Hint: There is always one legal movement between any two rods. Here is a possible way

to solve the towers of Hanoi problem:

1. Calculate the total number of moves required i.e. "pow(2, n)-1" here

2. If number of disks (i.e. n) is even then interchange destination rod and auxiliary rod.

3. for i = 1 to total number of moves: if i%3 == 1:

legal movement of top disk between source rod and

destination rod

if i%3 == 2:

legal movement top disk between source pole

and auxiliary rod

if i%3 == 0: legal movement top disk between auxiliary rod

and destination rod