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?


1 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.

  • $\begingroup$ Perhaps I'm missing something obvious: in your optimality proof, what precludes the possibility of jointly restoring a $p$-cycle and a $q$-cycle by using $< p+q-2$ transpositions? (I'm not saying it's possible; I just didnt see it proven to be impossible.) $\endgroup$
    – antkam
    Sep 11, 2020 at 16:39
  • $\begingroup$ @antkam the cycles are disjoint. $\endgroup$ Sep 11, 2020 at 16:40
  • $\begingroup$ Of course they are disjoint... Ah perhaps you mean if you transpose two elements belonging to two different cycles, then that intermediate result would be a bigger cycle and your proof would apply? $\endgroup$
    – antkam
    Sep 11, 2020 at 16:41
  • 1
    $\begingroup$ @antkam You think of the cycles as "homes" and the elements within a cycle as inhabitants of those homes. If you swap elements from different cycles, you take those inhabitants out of their homes, so you need more swaps to return them to their homes. $\endgroup$ Sep 11, 2020 at 16:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .