What is the parity of permutation in the 15 puzzle?

Question

You might know the 15 puzzle:

$\hskip1.4in$

Concerning the solvability, Wiki says:

The invariant is the parity of the permutation of all 16 squares plus the parity of the taxicab distance (number of rows plus number of columns) of the empty square from the lower right corner. This is an invariant because each move changes both the parity of the permutation and the parity of the taxicab distance. In particular if the empty square is in the lower right corner then the puzzle is solvable if and only if the permutation of the remaining pieces is even.

I don't get what exactly is meant with the parity of the permutation in this special case?

Answer 1

There are many equivalent ways of defining the parity of a permutation. For the 15 puzzle, if the blank is in the lower right, you can imagine restoring the original setup by removing two tiles and replacing them in each other's position until you are done. There are many paths to home, but they will either all have an odd number of steps or all have an even number of steps. For example, the original puzzle was shipped with the 14 and 15 swapped. That takes one flip if you flip 14 and 15. You could also flip (14,1), (1,15), (14,1). That is three swaps, but is still odd. The puzzle is solvable with sliding moves iff the permutation is even.

Answer 2

Given any current position of the sliding puzzle, a unique permutation in $S_{16}$ corresponding to this position is obtained by considering where exactly each of the 16 numbers is currently located (the 16th number represents of course the empty square). For example, the single move that brings 12 to the lower-right corner and that pushes the empty square one up yields the position (or permutation) $(12,16)$ since location 12 is mapped to square 16, and location 16 is mapped to square 12. The desired permutation (the final desired position) is the identity permutation.

Assuming we start off with the empty square in the lower-right corner, the objective of the puzzle is to bring the given permutation into the identity permutation using an even number of moves - even because in the final position the empty square will again have to be in the lower-right corner, and this means the empty square must have travelled an even number of moves (the 4x4 grid graph is bipartite, so for the empty square to have returned back to the initial partition in this bipartite graph requires it to have travelled an even number of edges). Every move is a transposition, such as the transposition $(12,16)$ above. A permutation can be expressed as a product of either an even number of transpositions or an odd number of transpositions, but not both. Thus, if the initial given position is such that it corresponds an odd permutation, then the puzzle is impossible to solve. (The converse also happens to be true - every even permutation is solvable.)