Again, the key is to first discover a recursive solution. Once you have that, the implementation should require little effort. You might want to read "Recursive Design Techniques", pp. 653-4.
Provide a solution to programming project #7 of chapter 11 of Savitch's textbook:
There is a story about Buddhist monks who are playing this puzzle with 64 stone disks. The story claims that when the monks finish moving the disks from one post to a second via the third post, time will end.
A stack of n disks of decreasing size (from bottom to top) is placed on one of three posts. The task is to move the disks one at a time from the first post to the second. To do this, any disk can be moved from any post to any other post, subject to the rule that you can never place a larger disk over a smaller disk. The ( spare) third post is provided to make the solution possible. Your task is to write a recursive static method that gives instructions for a solution to this problem. We do not want to bother with graphics, so you should output a sequence of instructions that will solve the problem. The number of disks is a parameter to the method.
Hint: If you could move up n– 1 of the disks from the first post to the third post using the second post as a spare, the last disk could be moved from the first post to the second post. Then, by using the same technique ( whatever that may be), you can move the n– 1 disks from the third post to the second post, using the first disk as a spare. There! You have the puzzle solved. You have only to decide what the nonrecursive case is[i.e., the base case], what the recursive case is, and when to output instructions to move the disks.
This is a classic problem for students of recursion. There are lots of solutions on the web, but please don't look them up. You can solve this on your own! Your driver, Hanoi, should prompt the user for the number of disks to be placed on the leftmost post. The other two posts will be empty. It should then print the sequence of moves necessary to move the disks from the leftmost post to the middle post, using the rightmost post as an intermediary.
To do this, write a function, printHanoi(int numDisks, int fromPost, int toPost) which prints the sequence needed to move numDisks disks from post fromPost to post toPost. We're using integers to identify the posts, so let post 1 is the leftmost post, post 2 be the middle, and post 3 be the rightmost.
Our printHanoi function will take two of those numbers as parameters. Suppose we call the function like this: printHanoi(6, 1, 3) . In other words we provide it with fromPost = 1 and toPost = 3. This means that we are trying to calculate how to move 6 disks on post 1 to post 3, by using post 2 as the intermediary (the "spare"). (The spare post is always the post that is not referenced as a parameter).
Consider how printHanoi might work for moving 4 disks from A to B. First, move the top 3 disks from A to C, leaving just the biggest disk on A and B empty. The move the biggest disk to B, the move the 3 disks from C to B. Done! In other words, printHanoi(4, 1, 2) involves printHanoi(3, 1, 3) and printHanoi(3, 3, 2).
As this will be a recursive solution, you'll need to identify the base case(s). Concentrate on the value of the first parameter to printHanoi()....
You'll want a helper function, int sparePost(int fromPost, int toPost) that returns the unoccupied post (either 1, 2 or 3), given any pair of posts.
Your program's main class should be called Hanoi. It should prompt the user for the number of disks to place on the leftmost post (I've called it "A" in my example). There will be 0 disks on the other two posts (I called them "B" and "C" in my example.)
Start by getting your function to work properly for problems of size 1 and 2. Then see if you can get it to work for problems of size 3, then 4.
Here is sample output for 4 disks from A to B:
Move 1 from A to C Move 2 from A to B Move 1 from C to B Move 3 from A to C Move 1 from B to A Move 2 from B to C Move 1 from A to C Move 4 from A to B Move 1 from C to B Move 2 from C to A Move 1 from B to A Move 3 from C to B Move 1 from A to C Move 2 from A to B Move 1 from C to B
Submit your code to the drop box.
Eddie Gurnee has found a nice animation of a solution to a variation of the Towers of Hanoi at https://projecteuler.net/problem=497.