Tower of Hanoi Puzzle

[Wabbit]

http://chemeng.p.lodz.pl/zylla/games/hanoi4e.html

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

[MKJ]

wabbit

[Eraser]

for real?

[tequila!]

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

[Deji]

Finished it quicker than I expected, the default one with 4 took me like 35 seconds

[MKJ]

3 wrong moves. wonder how it determines what is "wrong"

[Pext]

there's an optimum ~ everything above...

[MKJ]

rite

[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

[R00k]

I got the first one quickly, but with 4 wrong moves.

[R00k]

Damn. With 4 discs I had 4 wrong moves, with 5 discs I had 39 wrong moves.

[mjrpes]

the 15 disk puzzle has a minimum of 32767 moves. that will keep you busy

[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!

[Tsakali_]

I was up for a luck fest so I tried the 7 peg one, lol that was a disaster

[PhoeniX]

Did the first one in 15 moves

[Wabbit]

I wasn't going to admit it, but on the 7 disk puzzle, I had 384 wrong moves :icon32:

[Ryoki]

First one took me 25 moves

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

[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:

[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

[Deji]

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.

[Tsakali_]

fuck I can't put it down! 124 wrong moves on the 7 bar :icon23:

[Tsakali_]

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)

[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:

[tequila!]

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.