Can somebody describe the recursive solution of the Tower of Hanoi?

Answer 1

Tower of honoi

To some its a never ending game, to others its a good way to test the speed of their CPU, but, to us it is a great example of recursion.

In the original Tower of Honoi, you have 64 disks in position A stacked on top of each other. The largest disk at the bottom and smallest at the top and disks sorted from large to small. The task at hand is to move all 64 disks from position A to position B using position C, without ever putting a larger disk on top of a smaller one and only moving 1 disk at a time. How long do you think that would take you to complete? Chinese priest thought that the completion of this task will bring the end of the world, it was considered an unendable task. But, that was before the age high speed computers. How many moves do you think it takes to moves all 64 disks?

The recursive algorithm is extremely simple to state, note that the larger the number associated with a disk is, the larger the disk:

if (N == 1)
Move disk N from position A to position B
else
Move (N-1) disks from position A to position C using B
Move disk N from position A to position B
Move (N-1) disks from position C to position B using A
endif

Here is a method that prints all moves needed for N disks. To realize that time complexity of this method grows exponentially as n gets larger, you can copy the program that tests this method and try it for bigger Ns. The file is test_honoi.java You can use the Save As option in the File pull-down menu of netscape to save it in your account once the file is loaded in netscape.

public static void towerOfHonoi (int N, char from, char to, char using){
if (N == 1)
System.out.println("Move disk "+ N + " from position " + from + " to position " + to);
else {
Tower_Of_Honoi (N-1,from,using,to);
System.out.println("Move disk "+ N + " from position " + from + " to position " + to);
Tower_Of_Honoi (N-1,using,to,from);
}
}

Here is the output from this function when moving 3 disks from A to B using C:

Enter the number to try: 3
Move disk 1 from position A to position B
Move disk 2 from position A to position C
Move disk 1 from position B to position C
Move disk 3 from position A to position B
Move disk 1 from position C to position A
Move disk 2 from position C to position B
Move disk 1 from position A to position B
**** MOVES COMPLETED ****

Answer 2

With this problem it is best to break it into smaller parts, I won't give you a complete solution as that defeats the point of the exercise. You probably know that you need to use a recursive method on a stack database in order to solve this problem. Don't try to imagine the whole solution in your mind but write out bits of psuedocode to express the functions you want to perform. The problem then just becomes like any other, a series of steps that can be dealt with. Hope this helps and good luck.

Answer 3

quantity your disks a million,2,3, ... from the smallest to the biggest. think of your posts are 3 factors on a clock face(e.g, 12 o'clock, 4 and eight). elect an arbitrary clockwise/counter-clockwise direction for the weird and wonderful/even numbers of the disks to be moved via. assume it particularly is weird and wonderful-counter-clockwise or maybe-clockwise. purely pass this form. by no ability pass a bigger disk on actual of a smaller one. by no ability pass an identical disk two times in-a-row. do no longer injury those 3 rules. initiate with all disks on one positioned up ordered from backside to actual via length(quantity) from extreme to low. assume you have 3 disks. Your strikes will then be a million,2,a million,3,a million,2,a million in case you employ the stack technique, you're (in result) doing it recursively.

Answer 4

The website below is good. Most important is the part where it says "Recursive solution" and specifically the pseudocode starting with "Solve(N, Src, Aux, Dst)." If you don't understand the pseudocode, choose values for the four arguments and follow it through step-by-step. That's what I do.

So, for example, say N=3, Src=a, Aux=b, and Dst=c for the first call to the function. a, b, and c are 3 pegs from left to right. You can draw them like this. I represent it sideways because it is easier to draw.

a { O o .
b {
c {

a, b, and c are different pegs. "{" indicates peg platform. "O" is the biggest disk, "o" is the medium-sized disk, and "." is the smallest disk.

I will represent the diagram every time it changes.

Here it is step-by-step. Each ">" means one level into a function call.

Solve(N=3, Src=a, Aux=b, Dst=c)
>N=3, don't exit
>Solve(N=2, Src=a, Aux=c, Dst=b)
>>N=2, don't exit
>>Solve(N=1, Src=a, Aux=b, Dst=c)
>>>N=1, don't exit
>>>Solve(N=0, Src=a, Aux=c, Dst=b)
>>>>N=0, exit
>>>Move disk from a to c

a { O o
b {
c { .

>>>Solve(N=0, Src=b, Aux=a, Dst=c)
>>>>N=0, exit
>>Move disk from a to b

a { O
b { o
c { .

>>Solve(N=1, Src=c, Aux=a, Dst=b)
>>>N=1, don't exit
>>>Solve(N=0, Src=c, Aux=b, Dst=a)
>>>>N=0, exit
>>>Move disk from c to b

a { O
b { o .
c {

>>>Solve(N=0, Src=a, Aux=c, Dst=b)
>>>>N=0, exit
>Move disk from a to c

a {
b { o .
c { O

>Solve(N=2, Src=b, Aux=a, Dst=c)
>>N=2, don't exit
>>Solve(N=1, Src=b, Aux=c, Dst=a)
>>>N=1, don't exit
>>>Solve(N=0, Src=b, Aux=a, Dst=c)
>>>>N=0, exit
>>>Move disk from b to a

a { .
b { o
c { O

>>>Solve(N=0, Src=c, Aux=b, Dst=a)
>>>>N=0, exit
>>Move disk from b to c

a { .
b {
c { O o

>>Solve(N=1, Src=a, Aux=b, Dst=c)
>>>N=1, don't exit
>>>Solve(N=0, Src=a, Aux=c, Dst=b)
>>>>N=0, exit
>>>Move disk from a to c

a {
b {
c { O o .

>>>Solve(N=0, Src=b, Aux=a, Dst=c)
>>>>N=0, exit

And we're done with the expected configuration. It's get much harder to do on paper with higher numbers of N.

Hope this helps!

Answer 5

http://en.wikipedia.org/wiki/Towers_of_hanoi