Achievable set of permutations for a game? I came across this problem when trying to solve a combination puzzle called triple cross. You can find more about it here. This is just for context, as the problem below doesn't really need a knowledge of the game or its rules. The game has 3 permutation moves on a set of 18 tiles. Assuming some numbering of tiles, the permutation moves can be described using the cycle notation:
move 1: (1 8 14 15 10 3 2)(4 16 17 6 13 12 11)
move 2: (0 7 14 9 2)(1 8 15 3)(4 17 6 13 11)(5 12 10 16)
move 3: (0 1 2 9 15 14 7)(3 10 11 12 5 17 16)
The inverse permutations of these moves are also possible -- but maybe not relevant for this discussion as they can be obtained trivially by repeating the original move by the LCM-1 of the cycle lengths in the move (for moves 1 & 3, 6 times; for move 2, 19 times).
The page referenced above says that all even permutations are reachable. Maybe it was just an off hand remark, based on a brute force search. But my experimentation suggests that it maybe true. If so, how do we prove this?
I apologize in advance if my notation is non-standard. I am just an engineer whose last math class was ~ 20 years ago.
 A: "The page referenced above says that all even permutations are reachable. Maybe it was just an off hand remark, based on a brute force search."
I think that when I wrote that page I had not proved it by hand, but simply used GAP to show that the order of the group generated by move 1 and move 3 was a group of order $18!/2$, so that it had to be $A_{18}$, the group of all even permutations.
There are ways of proving it manually, but this case is particularly horrible. I'll show the first few steps of how you could approach it.
The main idea is to combine the available permutations to produce other permutations that have a simpler structure.
Let $A$ and $B$ be what you called move 1 and move 3, i.e. 
$$A=(1\ 8\ 14\ 15\ 10\ 3\ 2)(4\ 16\ 17\ 6\ 13\ 12\ 11)\\
B=(0\ 1\ 2\ 9\ 15\ 14\ 7)(3\ 10\ 11\ 12\ 5\ 17\ 16)$$
(I'll ignore move 2 - I'm not sure where you got it from, and moves 1 and 3 are the two basic types of cycles that you can perform on the puzzle)
Unfortunately all the cycles of $A$ and $B$ are of the same length, and that length is 7, a prime number. All powers $A^i$ and $B^i$ will then have the same structure, so this fails to simplify things.
Instead, let's look at the commutator of $A$ and $B$:
$$ABA^{-1}B^{-1} = (0\ 1) (2\ 16\ 4\ 3) (5\ 17) (8\ 14) (9\ 15\ 11\ 10) (12\ 13) $$
(Note: I write the permutations left to right, so A is applied first here. Conventions differ.)
The commutator of $A$ and $B$ tend to have a simpler structure than $A$ and $B$ themselves. This is because the commutator only affects the pieces that lie in the overlap of $A$ and $B$ and those pieces that are moved into the overlap by $A$ and $B$. The overlap is quite large here unfortunately, so the commutator is still quite long. It does however have cycles of different lengths.
The cycles of $ABA^{-1}B^{-1}$ have lengths 2 and 4. By squaring it, we get a permutation containing only 2-cycles, swaps:
$$C = (ABA^{-1}B^{-1} )^2 = (2\ 4)(16\ 3) (9\ 11)(15\ 10)$$
So now we have a permutation $C$ that only affects 8 of the pieces of the puzzle. The next step is then to look at commutators of $C$, i.e. commuting it with $A$, $B$, $A^2$, $B^2$, etc. to see if we can get other permutations that can be simplified further.
By repeating this process of taking powers (to knock out some of the cycles) and of commuting pairs of permutations (preferably those with very little overlap), you will probably eventually get down to a permutation that consists of a single 3-cycle. In some other puzzle groups you may even get a single swap. Let's call that simplest cycle $Z$.
To finish the proof you then have to take conjugates of $Z$, i.e. look at $A^i ZA^{-i}$ and $B^i ZB^{-i}$. Conjugates have the same structure, so will also be 3-cycles (or swaps). Once you have enough of these 3-cycles that you can move any puzzle piece into any location (while ignoring the other pieces), then all even permutations are possible. This is easy to prove by induction on the number of 3-cycles.
The Triple Cross puzzle is really not the best puzzle for this kind of analysis. You can find some easier examples on my web page page about rotational puzzles on graphs.
