# Fun Logic Puzzle



## Anonymous (Jul 20, 2010)

I just stumbled upon this puzzle: http://www.mazeworks.com/hanoi/index.htm

It says that the Tower of Hanoi is a well-known programming puzzle, so maybe some people on the forums already know about it. I love it, and so far have optimally solved up to eight rings.

Play it, tell what you think.


----------



## Cyrus C. (Jul 20, 2010)

Seen this before. It's pretty fun.


----------



## Anonymous (Jul 20, 2010)

How many rings did you manage to solve?


----------



## Forte (Jul 20, 2010)

Anonymous said:


> How many rings did you manage to solve?



Honestly, it's the same every time, just more tedious


----------



## Anonymous (Jul 20, 2010)

Forte said:


> Anonymous said:
> 
> 
> > How many rings did you manage to solve?
> ...



Conceptually, yes, but I find that at some point there's an added level of difficulty keeping track of what I'm doing.


----------



## The Puzzler (Jul 20, 2010)

Its a really easy puzzle


----------



## TheMachanga (Jul 20, 2010)

7,


----------



## cincyaviation (Jul 20, 2010)

gave up after 4


----------



## ariasamie (Jul 20, 2010)

TheMachanga said:


> 7,





http://www.mazeworks.com/hanoi/index.htm said:


> The minimum number of moves required is 127.


aha! you did 7 moves! I thought you did it with 7 discs!
I did it with 4 discs. it's fun! but i'm too lazy too go for 5 discs!


----------



## rjohnson_8ball (Jul 20, 2010)

I figured a simple algorithm for this over 40 years ago.


Spoiler



For the game shown at that site, if the total number of rings is even, then be sure to always move the smallest ring on every other turn in the clockwise direction. (If the total number of rings is odd, then it should go anti-clockwise.) On the intermediate turns, the move is forced. So, just keep moving the smallest ring the correct direction on alternate moves, and you will get the minimal solution.


----------



## ariasamie (Jul 20, 2010)

rjohnson_8ball said:


> I figured a simple algorithm for this over 40 years ago.
> 
> 
> Spoiler
> ...



wow!
I kinda noticed this one:


rjohnson_8ball said:


> the move is forced


but I'm too sleepy to figure out the rest! it's 2:23 am here!


----------



## Anonymous (Jul 20, 2010)

It's a really simple matter of reducing each one to a smaller tower- after you finish seven or eight, the five and four ones semm trivial lol.

Edit: My point is that seven, eight, nine etc. aren't as impossibly hard as they seem.


----------



## KrazyFK (Jul 20, 2010)

It might be interesting to note that for \( n \) rings, the (conjectured) minimum number of moves required is \( 2^n -1 \), and this is achieved by the algorithm already mentioned above.


----------



## Sakarie (Jul 21, 2010)

My "trick" is that whenever I have to choose something, it's practically always the smallest ring that goes first. You look for the pile you're currently moving, and figure where you want it to go; it doesn't matter if it's all the rings or just some. If it's an odd number of rings in the pile to move, you move the small ring to where the whole pile should go, and if it's an even number of rings, you move it to where you don't want the pile to end up.

It isn't hard really, and doing like 20 rings wouldn't be hard, just take time. It's like cubes! When you've solved 7x7, you can solve any numbered cube, it just takes time.


----------



## Anonymous (Jul 21, 2010)

I agree with you in theory, but it's not really feasible to do that many rings. For instance, the 12 ring puzzle requires over 4000 moves. 
I think I'm just going to stick with nine.


----------



## Chance (Jul 21, 2010)

Anonymous said:


> I agree with you in theory, but it's not really feasible to do that many rings. For instance, the 12 ring puzzle requires over 4000 moves.
> I think I'm just going to stick with nine.



It isn't impossible to do them, it just takes a lot longer.

The Tower of Hanoi is pretty easy, but it gets boring after a few times.


----------



## Metroidam11 (Jul 21, 2010)

It's easy but it takes up too much time with more rings. After you figure out the method its too simple.


----------



## qqwref (Jul 21, 2010)

KrazyFK said:


> It might be interesting to note that for \( n \) rings, the (conjectured) minimum number of moves required is \( 2^n -1 \), and this is achieved by the algorithm already mentioned above.



Yes.

There is an interesting variation in which you can only move rings to *adjacent* pegs - no moving from left to right or back for instance - and you must move the entire stack from the left peg to the right peg. This variation takes \( 3^n-1 \) moves for n rings and is slightly trickier to keep track of.


----------



## Whyusosrs? (Jul 21, 2010)

I did 8 rings. It just took a bit


----------



## cmhardw (Jul 21, 2010)

qqwref said:


> There is an interesting variation in which you can only move rings to *adjacent* pegs - no moving from left to right or back for instance - and you must move the entire stack from the left peg to the right peg. This variation takes \( 3^n-1 \) moves for n rings and is slightly trickier to keep track of.



Wow, I never thought to try that variation! That does sound neat, will have to give this a go. Trying to work out the process for 4 discs, and it already seems very interesting!

Chris


----------



## Grzegorz (Jul 21, 2010)

i wanted to do 12. when i was busy for a full minute, i then saw i needed a min of 4095 moves. i stopped then.


----------



## Rinfiyks (Aug 31, 2010)

cmhardw said:


> qqwref said:
> 
> 
> > There is an interesting variation in which you can only move rings to *adjacent* pegs - no moving from left to right or back for instance - and you must move the entire stack from the left peg to the right peg. This variation takes \( 3^n-1 \) moves for n rings and is slightly trickier to keep track of.
> ...



It's actually quite simple


Spoiler



Call the 3 pegs A, B and C.
You start on peg A, and have to get to peg C.

Move the smallest disc between pegs A and B.
Move the smallest disc between pegs B and C.

Repeat these two steps until you're finished.



There's a similar three step method for the original version too.


Spoiler



Move the smallest disc between pegs A and B.
Move the smallest disc between pegs A and C.
Move the smallest disc between pegs B and C.

And repeat until complete. But this one gets it to a different peg depending on whether you start with an odd or even number of discs, but that can easily be fixed, by swapping B and C in the method for an odd number of discs.



Can anyone help with this sequence?
Move the discs from A to C, and write 0 or 1 each move if:
If you move A to B, A to C or B to C, write 1. If you move B to A, C to A or C to B, write 0.

For 1, 2, 3, 4 and 5 discs, I get
1
111
1101011
111100111001111
1101011100001101011000011101011
Is there a way to find what this sequence will be with any number of discs?


----------



## FatBoyXPC (Aug 31, 2010)

Maybe I don't see the revelation of why this game is so interesting? Jaap has a javascript Towers of Hanoi with 7 or 8 rings on it, I forget which, and I found it to be the most boring puzzle. You keep doing the same thing over and over again.


----------



## qqwref (Sep 1, 2010)

Rinfiyks said:


> For 1, 2, 3, 4 and 5 discs, I get
> 1
> 111
> 1101011
> ...



4 = 111 1 0 0 111 0 0 1 111
5 = 1101011 1 000 0 1101011 0 000 1 1101011
6 = 111100111001111 1 0010100 0 111100111001111 0 0010100 1 111100111001111




Spoiler



The first, third, and fifth underlined sequences are identical to the sequence for 2 fewer discs. The second and fourth sequences are the inverse of the sequence for 3 fewer discs. Those 1s and 0s control the second-to-largest disc. The idea is that to think in terms of these sequences we can either move single discs between any two pegs or move stacks of discs from the leftmost peg to the rightmost peg or vice versa (but never to the middle peg because that would create a new type of sequence).

So the procedure is:
- Move top N-2 discs from the leftmost peg to the rightmost peg.
- Move N-1st disc right to the middle peg.
- Move top N-3 discs from the rightmost peg to the leftmost peg.
- Move N-2nd disc left to the middle peg.
- Move the N-2 discs on the leftmost peg (top N-3 plus Nth) to the rightmost peg.
- Move N-2nd disc left to the left peg.
- Move top N-3 discs from the rightmost peg to the leftmost peg.
- Move N-1st disc right to the right peg.
- Move top N-2 discs from the leftmost peg to the rightmost peg.


----------



## hic0057 (Sep 1, 2010)

Fun Fact: badmephisto got another account on YouTube called fractal maths which talks about the tower of hanoi. Check in his profile then click on his personal website. Click on YouTube on the right side. Fractal Math should show up in the middle.


----------



## MEn (Sep 1, 2010)

2^N-1


----------

