[roolstar]

I can't believe there is no mention of the Tower of Hanoi on this forum!!

I am pretty sure many of you guys are familiar of this game..

It consists of three pegs, and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another peg, obeying the following rules:

1- Only one disk may be moved at a time.

2- Each move consists of taking the upper disk from one of the pegs and sliding it onto another peg, on top of the other disks that may already be present on that peg.

3- No disk may be placed on top of a smaller disk.

Now the questions on this forum are:

1- Can this be solved for any number of disks? Even a hundred and only 3 pegs? How can you prove it?

2- How many moves are needed for (n) number of disks?

Advanced question for people already familiar with the 2 first questions:

3 - How many moves are needed if there are 4 pegs not 3??

Note: I don't have an answer for #3 yet...

Please don't post your answers without a spoiler, this may be fun for people who've just heard about this for the first time...

[Guest]

Tower of Hanoi.

This puzzle was invented by the French mathematician Edouard Lucas in 1883. A full description can be found here.

The puzzle can be solved for any number of disks, and the minimum necessary moves are (2^n)-1, where n is the number of disks.

[EventHorizon]

I had thought a while about trying to figure out how adding more towers would affect the number of steps needed.

It turned out to be an interesting answer (I love it when answers involve Pascal's triangle (represented in the answer by nCr))....though I don't know why it is as it is......yet.

I wrote some c++ code that given the number of towers and disks it would do breadth first search to find the least number of moves to move all the disks from one tower to another. It reports the number of steps and gives the sequence of states/moves.

I altered it later to just go halfway (till the biggest disk is moved) since the rest is fairly obvious.

I included some code.....just no comments on how bad/cryptic/not fault tolerant/not robust it is

I included some text files that shows the output I looked at to come up with my solution. I basically ran the code till it would crash because of integer overflow/out of memory and included the results. I may rewrite it by taking a different approach to allow larger numbers for the amount of towers and disks....later.

In the text files the state is listed as position of the disks going from smallest to biggest...

so it starts at 0 0 0 0 0 for 5 disks....which mean all disks are on tower 0.

The second state may be 1 0 0 0 0....which means all the disks but the smallest are on tower 0, and the smallest is on tower 1.

hanoi.zip

first, nCr(x,y) = x!/((x-y)!y!), which is the number of combinations of pool of x objects taken y at a time.

So here is a method to determine how many steps it will take to move d (>0) disks where there are t (>2) towers. Sorry for not being more clear.....but this isn't all that simple.

Step 1 - dcount = 0;

Step 2 - steps = 1;

Step 3 - increment = 2;

Step 4 - group = 1;

Step 5 - tochange = nCr(t-2+group,group);

Step 6 - dcount = dcount + 1;

//If (dcount == d) You are done....steps holds the number of steps needed!

Step 7 - steps = steps + increment;

Step 8 - tochange = tochange - 1;

Step 9 - If (tochange != 0) go to Step 6;

Step 10- increment = increment * 2;

Step 11- group = group + 1;

Step 12- tochange = nCr(t-2+group, group);

Step 13- go to Step 6

So the increment is always a power of 2. You add the increment a number of times based on pascal's triangle to the total, and then double the increment.

Notice that for 3 towers that nCr always results in 1....so the increment is always doubled. Also notice that for 4 towers that nCr increases by 1 each time.

Here's a quick run through for 4 towers

disks,steps,increment to next

1,1,2

2,3,2

3,5,4

4,9,4

5,13,4

6,17,8

7,25,8

8,33,8

9,41,8

10,49,16

11,65,16

12,81,16

13,97,16

14,113,16

...

Hopefully that made some sense.......any comments? Errors?

[EventHorizon]

...

Now the questions on this forum are:

1- Can this be solved for any number of disks? Even a hundred and only 3 pegs? How can you prove it?

2- How many moves are needed for (n) number of disks?

...

Since zoris didn't answer the last part of question 1....

It is easily proven by induction.

Base case:

You want to move a stack of the 1 smallest disk to another tower. Just move the one disk to the tower you want to move it to.

Inductive step:

(inductive hypothesis) Assume you can move a stack of the n smallest disks from one tower to another.

We want to show that you can move a stack of n+1 disks from one tower to another.

By the inductive hypothesis you can move the stack of n smallest disks. Move them to the tower that they are not on and not the tower you want the stack to eventually move to. Move the n+1st disk to the tower you want to have the stack on. Use the inductive hypothesis again to move the n+1 smallest disks to the tower you want them on. Now all the disks are on the tower you wanted to move them to.

By induction, you can move a stack of n disks to another tower.

Granted...this is not all that rigorous.....but you get the idea.

You can also see how many steps it takes to move a stack of disks.

For n+1 disks, you move a stack of n disks twice and move the n+1st disk once.

So steps(1) = 1. steps(n+1) = 2*steps(n)+1. Solving the recurrence relation results in steps(n)=(2^n)-1.

[roolstar]

I had thought a while about trying to figure out how adding more towers would affect the number of steps needed.

It turned out to be an interesting answer (I love it when answers involve Pascal's triangle (represented in the answer by nCr))....though I don't know why it is as it is......yet.

I wrote some c++ code that given the number of towers and disks it would do breadth first search to find the least number of moves to move all the disks from one tower to another. It reports the number of steps and gives the sequence of states/moves.

I altered it later to just go halfway (till the biggest disk is moved) since the rest is fairly obvious.

I included some code.....just no comments on how bad/cryptic/not fault tolerant/not robust it is

I included some text files that shows the output I looked at to come up with my solution. I basically ran the code till it would crash because of integer overflow/out of memory and included the results. I may rewrite it by taking a different approach to allow larger numbers for the amount of towers and disks....later.

Good job!

I downloaded your application and ran it (completely trusting you btw ). I entered the number of pegs, and the number of discs. Once I press "enter" the window closes and I don't get to see the answer... Any ideas why?

[roolstar]

hanoi.zip

first, nCr(x,y) = x!/((x-y)!y!), which is the number of combinations of pool of x objects taken y at a time.

So here is a method to determine how many steps it will take to move d (>0) disks where there are t (>2) towers. Sorry for not being more clear.....but this isn't all that simple.

Step 1 - dcount = 0;

Step 2 - steps = 1;

Step 3 - increment = 2;

Step 4 - group = 1;

Step 5 - tochange = nCr(t-2+group,group);

Step 6 - dcount = dcount + 1;

//If (dcount == d) You are done....steps holds the number of steps needed!

Step 7 - steps = steps + increment;

Step 8 - tochange = tochange - 1;

Step 9 - If (tochange != 0) go to Step 6;

Step 10- increment = increment * 2;

Step 11- group = group + 1;

Step 12- tochange = nCr(t-2+group, group);

Step 13- go to Step 6

So the increment is always a power of 2. You add the increment a number of times based on pascal's triangle to the total, and then double the increment.

Notice that for 3 towers that nCr always results in 1....so the increment is always doubled. Also notice that for 4 towers that nCr increases by 1 each time.

Here's a quick run through for 4 towers

disks,steps,increment to next

1,1,2

2,3,2

3,5,4

4,9,4

5,13,4

6,17,8

7,25,8

8,33,8

9,41,8

10,49,16

11,65,16

12,81,16

13,97,16

14,113,16

...

Hopefully that made some sense.......any comments? Errors?

I was almost able to follow you in the code, but I'm not sure I got it...

Could you explain in a more intuitive way how you reasonned to find the minimum required steps to move the disks?

[roolstar]

Since zoris didn't answer the last part of question 1....

It is easily proven by induction.

Base case:

You want to move a stack of the 1 smallest disk to another tower. Just move the one disk to the tower you want to move it to.

Inductive step:

(inductive hypothesis) Assume you can move a stack of the n smallest disks from one tower to another.

We want to show that you can move a stack of n+1 disks from one tower to another.

By the inductive hypothesis you can move the stack of n smallest disks. Move them to the tower that they are not on and not the tower you want the stack to eventually move to. Move the n+1st disk to the tower you want to have the stack on. Use the inductive hypothesis again to move the n+1 smallest disks to the tower you want them on. Now all the disks are on the tower you wanted to move them to.

By induction, you can move a stack of n disks to another tower.

Granted...this is not all that rigorous.....but you get the idea.

You can also see how many steps it takes to move a stack of disks.

For n+1 disks, you move a stack of n disks twice and move the n+1st disk once.

So steps(1) = 1. steps(n+1) = 2*steps(n)+1. Solving the recurrence relation results in steps(n)=(2^n)-1.

You are right: It is best proven by induction:

If we can move 3 disks, we can move 4; because moving 4 disks means:

1- Moving 3 disks to peg 2: that's exactly the same like moving 3 disks to peg 3.

2- Moving the biggest disk from peg 1 to peg 3

3- Moving the 3 disks from peg 2 to peg 3

So if it works for 1 ==> it works for 2 ==> it works for 3 ==> etc...

This method also helps up get the number of needed moves...

Edited March 6, 2008 by roolstar

[roolstar]

FOLLOW UP QUESTION!

An old legend tells of a Hindu temple where the pyramid puzzle might have been used for the mental discipline of young priests. Legend says that at the beginning of time the priests in the temple were given a stack of 64 gold disks, each one a little smaller than the one beneath it. Their assignment was to transfer the 64 disks from one of the three poles to another, with one important condition: a large disk could never be placed on top of a smaller one. The priests worked very efficiently, day and night. When they finished their work, the myth said, the temple would crumble into dust and the world would vanish.

So when the priest will finish their work the world would seize to exist!

Now the question is: When is that?

[EventHorizon]

I had an off-by-one error in my pseudocode (should have been nCr(t-3+group,group)), and I can extend the method to allow 0 disks (no moves needed).

[spoiler=Why stop at 4? --correct...hopefully ]

hanoi.zip

first, nCr(x,y) = x!/((x-y)!y!), which is the number of combinations of pool of x objects taken y at a time.

So here is a method to determine how many steps it will take to move d (>=0) disks where there are t (>2) towers. Sorry for not being more clear.....but this isn't all that simple.

Step 1 - dcount = 0;

Step 2 - steps = 0;

Step 3 - increment = 1;

Step 4 - group = 0;

Step 5 - tochange = nCr(t-3+group,group);

Step 6 - If (dcount == d) You are done....steps holds the number of steps needed!

Step 7 - steps = steps + increment;

Step 8 - dcount = dcount + 1;

Step 9 - tochange = tochange - 1;

Step 10- If (tochange != 0) go to Step 6;

Step 11- increment = increment * 2;

Step 12- group = group + 1;

Step 13- go to Step 5

ok...now to read what roolstar has posted since last night....

Edited March 6, 2008 by EventHorizon

[EventHorizon]

Good job!

I downloaded your application and ran it (completely trusting you btw ). I entered the number of pegs, and the number of discs. Once I press "enter" the window closes and I don't get to see the answer... Any ideas why?

.....

I was almost able to follow you in the code, but I'm not sure I got it...

Could you explain in a more intuitive way how you reasonned to find the minimum required steps to move the disks?

As for the window closing. I wrote it to be run from the dos prompt (it is easier to do batch processing that way). The program finishes once the answer is printed, but you could always add in a pause of some sort (two getchar()'s ? or System("pause")) if you can recompile the code.

When running from the dos prompt you can also just give it the number of towers and disks on the commandline (eg, "hanoi.exe 4 6").

As for not being able to follow the code.....I assume you mean the C++ code and not the pseudocode...here's a bit of a walkthrough as to what it is doing.

* deep breath *

I wrote a method to store the list of positions into a single integer (index2num), and one to get it back again (num2index). The index array holds this list of disk positions.

The node class is just there to be a linked list. This is used to do the breadth first search. It is used as a queue (first in first out).

I first allocate an array to hold every possible state that can be reached (states[]), this is used to store the "parent state" of each state....basically it is how I reached that state. I use this after the goal state is found to print back the sequence of moves.

I put the first state (0 0 0 0 0, in the case of 5 disks) onto the queue, and mark that the initial state's parent is itself (0). When printing back you will notice I stop when 0 is found then outside of the while loop print off the initial state.

Here's where the main loop begins...

I look at the state in the front of the queue and fill index with it's disk positions

"

if (current)

{

if (index[disks-1]) break;

}

"

I check to see if I'm in the goal state. If I am I exit the loop.

This goal state is only halfway (once the biggest disk is not on tower 0) since once the biggest disk is moved the rest if fairly trivial. This also makes this it run a good deal faster.

Then I loop through all valid moves (loop through disks, if there is a smaller disk on me or on the tower I want to move to, it is invalid) and add them to the queue marking their parent state in the states array (so they won't be added again later and to know how I got there).

I pop off the node I was looking at and delete it.

And then redo the loop.

Breadth first search will find the shortest path to any node/state. Which means the least number of moves.

* gasp *

Hope that helps....

[EventHorizon]

FOLLOW UP QUESTION!

An old legend tells of a Hindu temple where the pyramid puzzle might have been used for the mental discipline of young priests. Legend says that at the beginning of time the priests in the temple were given a stack of 64 gold disks, each one a little smaller than the one beneath it. Their assignment was to transfer the 64 disks from one of the three poles to another, with one important condition: a large disk could never be placed on top of a smaller one. The priests worked very efficiently, day and night. When they finished their work, the myth said, the temple would crumble into dust and the world would vanish.

So when the priest will finish their work the world would seize to exist!

Now the question is: When is that?

This question requires a few assumptions....

When is the beginning of time? I'll assume 4000bc to appease the new-earth creationists.

How quickly can the priests move a single disk? I'll assume it takes one second to move a disk and that it doesn't matter the size of the disk.

So, it takes 2^64-1 moves to move the stack.....this is approximately 1.844*10^19.

So that amount in seconds is 3.0744*10^17 minutes

5.1241*10^15 hours

2.13504*10^14 days

5.84542*10^11 years (this used 365.25 as days in a year...I know it is a little off)

584542046.1 millenia

Well.....that's a lot of time.

So I guess my answer would be just about 584542046100 A.D.

[roolstar]

As for the window closing. I wrote it to be run from the dos prompt (it is easier to do batch processing that way). The program finishes once the answer is printed, but you could always add in a pause of some sort (two getchar()'s ? or System("pause")) if you can recompile the code.

When running from the dos prompt you can also just give it the number of towers and disks on the commandline (eg, "hanoi.exe 4 6").

As for not being able to follow the code.....I assume you mean the C++ code and not the pseudocode...here's a bit of a walkthrough as to what it is doing.

* deep breath *

...

Hope that helps....

It does!!

Thanks EH for your efforts, I can see this took some time...

[roolstar]

This question requires a few assumptions....

When is the beginning of time? I'll assume 4000bc to appease the new-earth creationists.

How quickly can the priests move a single disk? I'll assume it takes one second to move a disk and that it doesn't matter the size of the disk.

So, it takes 2^64-1 moves to move the stack.....this is approximately 1.844*10^19.

So that amount in seconds is 3.0744*10^17 minutes

5.1241*10^15 hours

2.13504*10^14 days

5.84542*10^11 years (this used 365.25 as days in a year...I know it is a little off)

584542046.1 millenia

Well.....that's a lot of time.

So I guess my answer would be just about 584542046100 A.D.

So we're safe for now! Pfuu...

I even heard another twist in the legend saying that every VISITOR to the temple has to move one disk, and when all of them are on the 3rd pole, THE END!

So this would take a bit more time....

[EventHorizon]

It does!!

Thanks EH for your efforts, I can see this took some time...

YW. It didn't take all that much time actually....I'm a Computer Science grad.

It was a problem I had thought a bit about before...and it was kinda fun to decide how to implement it in C++ and then to find the answer. It's also nice to know someone else was interested in it too.

[Guest]

I had a variant of this as a kid. It was nesting pyramids with a prize under the smallest (you could only put a pyramid on a smaller pyramid). I solved it once and never felt it was worth the time to ever solve it again