# The Math behind rotation puzzles?

In the game Machinarium, there is the following puzzle where the goal is to get all of the green points on the green area by rotating them along any of the 3 circles engraved on the background plate. ( Here is a video showing it in motion )

Is there some theory behind this kind of puzzle?

Edit: And if there is, is there some way to leverage that theory to get a more efficient solution than randomly clicking until a solution is reached?

-

This puzzle is an example of a group action. In this case, our set $X$ is the collection of all possible arrangements of the green and red dots, and the group $G$ that is acting on $X$ is the subgroup of $S_X$ (the group of all permutations of $X$) generated by the three elements corresponding to a turn of the first circle, second circle, and third circle, respectively. The question is then, if $x\in X$ is the current arrangement of the dots, and $y\in X$ is the desired arrangement of the dots, how to find a $g\in G$ such that $gx=y$ (presumably, the puzzle would not be set up in a way where there is no such $g$, i.e., the desired arrangement can actually be reached from the initial arrangement.)

-
I was initially thinking in the same direction, but I think the fact that we cant distinguish the individual dots might pose a problem: If we label them from 1..16, we have 6!*6! positions that would solve the puzzle, and it might very well be possible that only a tiny fraction of them are reachable, i.e. we don't know the y. – Benno Oct 15 '11 at 3:20

Yes, there is a lot of group theory in these puzzles. The best developed literature I have seen (but I haven't read a lot) is on Rubik's cube. One approach is to find a series of moves that interchange two points, leaving all the rest alone. In this puzzle it is harder to see as the points are not distinguishable-it would help to put numbers 1-6 on the green ones and 11-16 on the red. Then you use the logic of commutators-find a pair you want to swap, do whatever moves it takes to put those in the position you know how to swap (remembering how you put them there), swap them, then undo the moves that got them there. In grouptheoryspeak this is a cojugate. The reason it is group theory is you have three basic moves with inverses and associativity.

Added, based on Benno's comment to Zev's answer: if you can find a series of moves that interchanges an inside point with an outside point leaving all others in place you have an algorithm (maybe not the fastest). It is possible that there is no such series of moves, but the puzzle is solvable anyway. For example, there might be a parity restriction that there are always an even number of greens in the center. I would be very surprised. But the Rubik's cube has some constraints that reduce the possible positions by a factor $12$ compared to diasassembly.

-
+1 for explaining how the theory explicitly helps to solve the problem :) – Zev Chonoles Oct 15 '11 at 3:19
It's not a commutator, it's a conjugate: $aba^{-1}$, where $a$ is the sequence of moves that brings the pair to the desired locations, and $b$ is the sequence of moves that swaps the pieces in those locations. – Ted Oct 15 '11 at 6:10
Some more group theory related puzzles: scientificamerican.com/… – Hans Lundmark Oct 15 '11 at 14:19
@Ted: Thanks. I fixed it. – Ross Millikan Oct 15 '11 at 16:16