Hi, I have a grad standard due in high school on the Tower of Hanoi with 7 disks. What is the algorithm for 7 of them? I just don't really get how to do it and since its a grad standard my teacher cannot help me. My paper late already :-[. If possible explain the steps as simple as possible or esle I'll never get it. Can anyone help??? Thanx a million!!!!!

> What is the algorithm for 7 of them?

What is the largest number of disks that you know the algorithm for?
Can you solve the puzzle with 3 disks? 4?

As I remember the problem, there are two simple rules for moving the discs. If the pile starts on peg A, and you want to move it to peg B (the target peg), using peg C as the "storage" peg, and you want to move an even number of discs, you move the first one to the storage peg. When you want to move an odd number of discs, you move the first disc to the target peg.

If you continue this procedure for all moves, without a mistake, you will achieve the minimum of 2^n-1 moves.

I do not understand the phrase "grad standard", so I do not know is this is what you want.

For your problem of 7 discs, and you want to move them from peg A to peg B, you start by moving the first disc to peg C, the second disc to peg B, then the one on peg C on top of the one on peg B. You have now moved two pegs in three moves. Then you move the third disc to peg C. Then using the same procedure as before, move the first two discs onto peg C. You have now moved three discs using 7 moves. Then you move the fourth disc onto peg B followed by moving the first 3 discs onto peg B. This will take another 8 moves for a total of 15. You continue this on and on for the total of 127 moves.

I hope this is at least some help.

Jack

Tower of Hanoi

Recursive solution for 4 discs:

Simple to solve for us humans brains (wetfatware), but boggling in computation software...

Let's call the three pegs Src (Source), Aux (Auxiliary) and Dst (Destination). To better understand and appreciate the following solution you should try solving the puzzle for small number of disks, say, 2,3, and, perhaps, 4. However one solves the problem, sooner or later the bottom disks will have to be moved from Src to Dst. At this point in time all the remaining disks will have to be stacked in decreasing size order on Aux. After moving the bottom disk from Src to Dst these disks will have to be moved from Aux to Dst. Therefore, for a given number N of disks, the problem appears to be solved if we know how to accomplish the following tasks:

1.Move the top N-1 disks from Src to Aux (using Dst as an intermediary peg)
2.Move the bottom disks from Src to Dst
3.Move N-1 disks from Aux to Dst (using Src as an intermediary peg)

Assume there is a function Solve with for arguments - number of disks and three pegs (source, intermediary and destination - in this order). Then the body of the function might look like

Solve(N, Src, Aux, Dst)
if N is 0 exit
Solve(N-1, Src, Dst, Aux)
Move from Src to Dst
Solve(N-1, Aux, Src, Dst)

This actually serves as the definition of the function Solve. The function is recursive in that it calls itself repeatedly with decreasing values of N until a terminating condition (in our case N=0) has been met. To me the sheer simplicity of the solution is breathtaking. For N=3 it translates into

1.Move from Src to Dst
2.Move from Src to Aux
3.Move from Dst to Aux
4.Move from Src to Dst
5.Move from Aux to Src
6.Move from Aux to Dst
7.Move from Src to Dst

Of course "Move" means moving the topmost disk. For N=4 we get the following sequence

1.Move from Src to Aux
2.Move from Src to Dst
3.Move from Aux to Dst
4.Move from Src to Aux
5.Move from Dst to Src
6.Move from Dst to Aux
7.Move from Src to Aux
8.Move from Src to Dst
9.Move from Aux to Dst
10.Move from Aux to Src
11.Move from Dst to Src
12.Move from Aux to Dst
13.Move from Src to Aux
14.Move from Src to Dst
15.Move from Aux to Dst

You should find something here to extend to even numbered discs.

Here, we call it "performance standards."