Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -


  • Please log in to reply
14 replies to this topic

#1 roolstar

roolstar

    Advanced Member

  • Members
  • PipPipPip
  • 250 posts
  • Gender:Male

Posted 29 February 2008 - 10:38 AM

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.

Towers_of_Hanoi.png

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...
  • 0

#2 zoris

zoris

    Junior Member

  • Members
  • PipPip
  • 43 posts

Posted 29 February 2008 - 11:39 AM

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

Spoiler for Spoiler

  • 0

#3 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 06 March 2008 - 07:21 AM

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.

Spoiler for Why stop at 4?

  • 0

#4 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 06 March 2008 - 07:44 AM

...
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....

Spoiler for prove it!

  • 0

#5 roolstar

roolstar

    Advanced Member

  • Members
  • PipPipPip
  • 250 posts
  • Gender:Male

Posted 06 March 2008 - 11:54 AM

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?
  • 0

#6 roolstar

roolstar

    Advanced Member

  • Members
  • PipPipPip
  • 250 posts
  • Gender:Male

Posted 06 March 2008 - 12:32 PM

Spoiler for Why stop at 4?


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?
  • 0

#7 roolstar

roolstar

    Advanced Member

  • Members
  • PipPipPip
  • 250 posts
  • Gender:Male

Posted 06 March 2008 - 12:37 PM

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

Spoiler for prove it!


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 by roolstar, 06 March 2008 - 12:43 PM.

  • 0

#8 roolstar

roolstar

    Advanced Member

  • Members
  • PipPipPip
  • 250 posts
  • Gender:Male

Posted 06 March 2008 - 12:48 PM

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?
  • 0

#9 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 06 March 2008 - 07:34 PM

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 for Why stop at 4? --correct...hopefully



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

Edited by EventHorizon, 06 March 2008 - 07:36 PM.

  • 0

#10 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 06 March 2008 - 08:07 PM

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....
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users