Page 1 of 1

Towers of Hanoi Variation

Posted: Thu Oct 08, 2009 5:26 am
by elendiastarman
I got an idea while looking at a child's toy and simplified it to represent the simplest non-trivial case.

You start with 3 poles in a row. The left one has triangles on it and the right has squares, there is nothing in the middle. Rules are exactly like the original for the triangles and the squares, but you can put a big square on top a small triangle, although you must move the big square off first. The objective is for the stacks to switch position.
How many moves will it take to switch stacks when both have 4 pieces?
How many moves will it take to switch stacks when both have 5 pieces?
How many moves will it take to switch stacks when both have 10 pieces?
If having only 3 poles makes it impossible, prove it and use 4 poles instead. I haven't actually tried it yet... :/

Re: Towers of Hanoi Variation

Posted: Sat Oct 17, 2009 1:00 am
by rmillika
If the rule is that any square can go on any triangle, we can just view this as a stage of the original game with the number of disks equal to the sum of the squares and triangles. So for 4 squares and 4 triangles we have eight disks with a linear order among them. If we started with all the disks on one peg and played the original game, we are now 15 moves in. Your target configuration is achieved 15 moves before completion of the original game. So the number of moves is 2^8-1-30=225. For five of each it is not so easy, as we are not on the way to stacking the triangles on the right side, but on the way to stacking the triangles in the middle. One choice is to move the squares back to the triangles, using 31 moves, go 31 moves short of moving the whole stack to the right (which has the squares in the middle), then use 31 moves to get the squares on the left. This is 31+2^10-1=1054. I am not sure that there isn't a faster way. For 10 we have 2^20-1-2*(2^10-1)=1046549.

I think.

Re: Towers of Hanoi Variation

Posted: Sat Oct 17, 2009 1:13 am
by elendiastarman
Well, the rule is that any square can go on any triangle and any triangle can go on any square. There is no relation between the two other than physically preventing the lower one from being removed before the higher one.

Re: Towers of Hanoi Variation

Posted: Tue Oct 20, 2009 9:56 am
by rmillika
In that case, I think the easiest is to move the squares to the center peg, the triangles to the left, and the squares to the right, using the standard solution.
You have to clear the largest square from the left peg, and putting it on the triangles is in the way. So for four of each we need 3*(2^4-1)=45 moves.
I can't think of a more efficient way.

Re: Towers of Hanoi Variation

Posted: Fri Jan 01, 2010 3:29 am
by uws8505
I doubt that it is possible, but think of this:
Move the top(smallest) triangle to the middle. Then move the top square to the middle.
Repeat the process until you have only one square left on the right and nothing on the left.
Move the biggest square to the left. Then move all pieces on the middle to the corresponding position.
That makes only 4n-1 moves!
If you do not consider violation of "bigger under smaller" rule for pieces not touching each other, it makes sense :D

Re: Towers of Hanoi Variation

Posted: Sun Mar 18, 2012 11:22 pm
by Alhazen
What about an abstract 2 game players based on towers of Hanoi?