Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.)
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.
This puzzle is easy once you try to put the red dots into their correct places instead of focusing on the green dots. In fact, you can do it without using the top-left circle!
In general, for permutation puzzles that don't have physical restrictions, including puzzles like the Rubik's cube, we can solve them systematically by finding the following:
(I use A' to denote the inverse of A)
Two transformations A,B that intersect in only one place X such that both A and B moves the piece at X away. Then ABA'B' is a commutator that will do a 3-cycle involving X. It is usually not hard to choose A and B such that A pulls the correct piece into X and B' pushes the piece at X into the correct place of the piece that was originally at X. It may sometimes be necessary to set up the pieces using a third sequence C so that a commutator can be done, and then undo C'. It is usually not harder to get the 3-cycle to correctly position and orient 2 of the 3 pieces in the 3-cycle.
Two transformations A,B that intersect in only one place X such that only B moves the piece at X away, while A merely changes the orientation of the piece at X. Then ABA'B' is a commutator that will change the orientation of two pieces, one of which is at X. Usually this can be substituted by using two 3-cycles, the first to dislodge the two pieces and a third, and the second to put them all back in the correct orientations, however this single commutator may take fewer moves.
Commutators can solve a state if and only if the positions of the pieces is an even permutation and the full description including orientations is also an even permutation. (For a Rubik's cube, a corner-twist is a 3-cycle on the three outer faces of the piece.) Some positions are not even permutations, and you must find a way to correct all these parities. (In the case of an 3*3*3 Rubik's cube a quarter-turn of any face corresponds to a 4-cycle of edges and a 4-cycle of corners. This parity means that exactly half of all positions can be solved by commutators alone, while the other half require a parity correction. For a 4*4*4,5*5*5,6*6*6 Rubik's cube there are 2,2,3 parities respectively if I counted correctly.)
For those puzzles with physical restrictions, like the Square One, it may be sufficient to get it into a nice enough form where commutators can be used without being blocked.
Note that this method involve absolutely no memorized algorithms, which means that it works on a large class of permutation puzzles, but which also means that it is usually not as fast as memorization-based methods which are tailored to the specific puzzle. However, its most important advantage is that you fully understand how the permutation puzzles work.
There are some puzzles I have come across where it is difficult to find 3-cycles, such as Twiddle. The only suggestion I have is to find two sequences which intersect at as few places as possible, and the commutator obtained will permute at most 3 times as many pieces as intersections, and then to combine commutators that intersect in fewer places, and so on. If anyone has better ideas I would of course be interested to hear!
