# Fifteen Puzzle: Finding Invariants [closed]

Moved from Math StackExchange: The Fifteen Puzzle consists of sliding square tiles numbered $1...15$ held in a $4\times4$ frame with one empty square. Any tile adjacent to the empty square can slide into it. The standard initial position is $$\begin{array}{|c|c|c|} \hline 1 & 2&3 & 4 \\ \hline 5 & 6 & 7 & 8\\ \hline 9 & 10 & 11 & 12\\ \hline 13 & 14 & 15 \\ \hline \end{array}$$ The target position we would like to reach is: \begin{array}{|c|c|c|} \hline 15 & 14 & 13 & 12 \\ \hline 11 & 10 & 9 & 8\\ \hline 7 & 6 & 5 & 4\\ \hline 3 & 2 & 1 \\ \hline \end{array}

A state machine model of the puzzle has states consisting of a $4 \times 4$ matrix with $16$ entries consisting of the integers $1...15$ as well as one “empty” entry—like each of the two arrays above. The state transitions correspond to exchanging the empty square and an adjacent numbered tile. For example, an empty at position $(2,2)$ can exchange position with tile above it, namely, at position $(1,2)$

Using the method of finding invariants, how can you prove that there is no way to reach the target state starting from the initial state?

• This problem is taken word-for-word from these course notes. You should credit it. – xnor Oct 11 '15 at 8:15
• Also, even though you were directed here from Math SE, I think this is standard enough combinatorics that's it's more a math problem than a puzzle. – xnor Oct 11 '15 at 8:17