Page 1 of 2

Tower of Hanoi Puzzle

Posted: Tue Oct 03, 2006 4:06 am
by Wabbit
http://chemeng.p.lodz.pl/zylla/games/hanoi4e.html

Hmm, my wrong moves get really high the more pieces I move.

Posted: Tue Oct 03, 2006 8:50 am
by MKJ
wabbit

Posted: Tue Oct 03, 2006 9:07 am
by Eraser
for real?

Re: Tower of Hanoi Puzzle

Posted: Wed Oct 04, 2006 3:41 am
by tequila!
Wabbit wrote: Hmm, my wrong moves get really high the more pieces I move.
I remember having to solve this puzzle for computer science back in high school. I don't recall whether or not we had to solve it in the least possible moves like this version, or if we simply had to provide any solution that worked.

There is actually a very simple set of rules to follow to solve it in the least possible number of steps, although there is one complication - the rules are slightly different depending on whether you have an even or odd number of disks.

Spoiler:
http://www.tequilasplace.com/temp/hanoi.txt

Posted: Wed Oct 04, 2006 5:32 am
by Deji
Finished it quicker than I expected, the default one with 4 took me like 35 seconds :shrug:

Posted: Wed Oct 04, 2006 1:48 pm
by MKJ
3 wrong moves. wonder how it determines what is "wrong"

Posted: Wed Oct 04, 2006 1:58 pm
by Pext
there's an optimum ~ everything above...

Posted: Wed Oct 04, 2006 1:59 pm
by MKJ
rite

Posted: Wed Oct 04, 2006 4:14 pm
by mjrpes
this is a classic discrete math problem.
Fascinating Facts

The Tower of Hanoi (sometimes referred to as the Tower of Brahma or the End of the World Puzzle) was invented by the French mathematician, Edouard Lucas, in 1883. He was inspired by a legend that 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 provisoøa large disk could never be placed on top of a smaller one.

Where's the Math in this Game?

The number of separate transfers of single disks the priests must make to transfer a tower is 2 to the 64th minus 1, or 18,446,744,073,709,551,615 moves! If the priests worked day and night, making one move every second it would take slightly more than 580 billion years to accomplish the job!
http://www.lawrencehallofscience.org/Ja ... story.html

Posted: Wed Oct 04, 2006 4:51 pm
by R00k
I got the first one quickly, but with 4 wrong moves.

Posted: Wed Oct 04, 2006 4:57 pm
by R00k
Damn. With 4 discs I had 4 wrong moves, with 5 discs I had 39 wrong moves. :(

Posted: Wed Oct 04, 2006 5:21 pm
by mjrpes
the 15 disk puzzle has a minimum of 32767 moves. that will keep you busy :D

Posted: Wed Oct 04, 2006 5:27 pm
by R00k
That's the worst part about the 5 disc one -- it only has a minimum of 31 moves, so I took more than double that to solve it!

Posted: Wed Oct 04, 2006 5:29 pm
by Tsakali_
I was up for a luck fest so I tried the 7 peg one, lol that was a disaster

Posted: Wed Oct 04, 2006 5:31 pm
by PhoeniX
Did the first one in 15 moves :shrug:

Posted: Wed Oct 04, 2006 5:36 pm
by Wabbit
I wasn't going to admit it, but on the 7 disk puzzle, I had 384 wrong moves :icon32:

Posted: Wed Oct 04, 2006 5:37 pm
by Ryoki
First one took me 25 moves :(

Posted: Wed Oct 04, 2006 5:38 pm
by dzjepp
For the tall columns, are you supposed to anticipate moves in advance or is it all elementary math at the core? (albeit very, very, very repetitive).

Posted: Wed Oct 04, 2006 5:40 pm
by Tsakali_
did the 6 one with 45 wrong moves lol

woot 6 bar one with 19 wrong moves!

K I'm done with this :icon30:

Posted: Wed Oct 04, 2006 5:42 pm
by Wabbit
On wikipedia they have a gif of the 4 move tower--it's about half way down the page.

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

Posted: Wed Oct 04, 2006 6:16 pm
by Deji
Tsakali_ wrote:did the 6 one with 45 wrong moves lol

woot 6 bar one with 19 wrong moves!

K I'm done with this :icon30:
6 bar one with 11 wrong moves. Muar.

Posted: Wed Oct 04, 2006 6:30 pm
by Tsakali_
fuck I can't put it down! 124 wrong moves on the 7 bar :icon23:

.

Posted: Wed Oct 04, 2006 6:46 pm
by Tsakali_
dzjepp wrote:For the tall columns, are you supposed to anticipate moves in advance or is it all elementary math at the core? (albeit very, very, very repetitive).
somewhat but with more bars introduced the steps take more switching which makes it more complicated, i can't explain it, just when I think I have the idea on what needs to happen moves have an exponential increase in complexity( added moves)

Posted: Wed Oct 04, 2006 8:22 pm
by Deji
84 wrong moves on the 7 bar. I should think things through before I move shit. At one point I just randomly shifted stuff around seeing if it would work :icon32:

Re: .

Posted: Thu Oct 05, 2006 1:14 am
by tequila!
Tsakali_ wrote:
dzjepp wrote:For the tall columns, are you supposed to anticipate moves in advance or is it all elementary math at the core? (albeit very, very, very repetitive).
somewhat but with more bars introduced the steps take more switching which makes it more complicated, i can't explain it, just when I think I have the idea on what needs to happen moves have an exponential increase in complexity( added moves)
There's a simple algorithm that works for any number of disks with the slight hitch that there is a small difference between solving it for an odd or even number of disks.

Setting the # of disks to 3 and 4, while it may seem too easy, will make it much easier to discover the algorithm.

Start with 3 disks, instead of thinking about it strictly in terms of "winning", think about it in terms of making mental rules for yourself that "always work". Then move on to 4 disks, try the same thing and you'll find you need slightly different rules to make it "always" work, because of the odd/even discrepency.

Once you have that, solving it for higher number of disks is just as straightfoward, albeit the more disks you have the easier it is to lose track of what you're doing and make a mistake.

---

a couple hints:

1) With only 3 disks, see what happens when your very first move is to the middle pole vs. to the third pole, and analyze why only one of those moves will solve it in the least possible number of steps.

2) The bottom most disk must only be moved once if you want to solve it in the least possible number of steps - from its initial position to the third pole. This is why the discrpency arises between how you solve it for odd vs. even numbers of disks.