Composition of transpositions to solve a simple tile puzzle

Question

I'm teaching myself group theory by means of studying tile puzzles. One very simple puzzle has a 3x3 grid containing the numbers 1-9, and the only available move is to swap the tiles in any 2 positions, with the goal of having the tiles in order from 1-9 as shown below:

+---+---+---+
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
+---+---+---+

First of all, I need to know that my basic understanding of cycle notation for permutations is correct.

Is it correct to say that this arrangement:

+---+---+---+
| 2 | 6 | 8 |
| 5 | 4 | 7 |
| 9 | 3 | 1 |
+---+---+---+

is represented by the permutation

(1 9 7 6 2) (3 8) (4 5)

?

If so, is there any need to distinguish this as representing a state vs an action that has been performed?

Next, I understand that certain combinations of permutation produce predictable results.

E.g. (a b) (c d) = (a b c) (a d c)

My question is, how can I use results such as this to solve the problem - i.e. to perform a minimal sequence of transpositions which will create the winning state?

Is this the kind of thing that is amenable to some equivalent of solving an equation in "normal" algebra? Is there a systematic approach which can be applied, or is it more a case of applying known transformations using educated guesswork?

Answer 1

If we number the nine positions $1$ to $9$ like the tiles in the solved state, we can indeed say that $\pi=(19762)(38)(45)$ represents the given scrambled position. We can understand this as tile $i$ at position $\pi(i)$, or that we have moved tile $i$ to position $\pi(i)$, so there is no need to distinguish the two interpretations.

Now to solve the problem in minimal moves, look at $\pi$'s cycles in turn. For each cycle $(x_1x_2\dots x_n)$ where $n>1$ (i.e. ignoring tiles already in place), swap tiles $x_n$ and $x_{n-1}$, then tiles $x_{n-1}$ and $x_{n-2}$ and so on down to tiles $x_2$ and $x_1$. Every permutation has such a cycle decomposition, and it is easy to see that restoring an $n$-cycle requires at least $n-1$ transpositions, so the method produces optimal results.