Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I found this question which got some good answers on how to check if an 8-puzzle is solvable. But what if there are less than 8 tiles on the grid? How to check if a puzzle with n tiles is solvable?
For n=7 tiles, this would be the goal state:
1|2|3
-+-+-
4|5|6
-+-+-
7| |
You know that with one open slot half the puzzles are unsolvable, basically because two neighboring tiles have been switched ('inverted'). (or: as some put it: there have been an odd number of such inversions, and as you make moves, there will always remain an odd number of inversions).
But with two open slots, you can always get any two tiles $A$ and $B$ next to each other, and next to the open 2 spots, making a square:
\begin{array}{|c|c|} \hline A & B \\ \hline & \\ \hline \end{array}
And with those two open slots we can of course easily switch the position of those two tiles:
\begin{array}{|c|c|} \hline B & A \\ \hline & \\ \hline \end{array}
So, you can do any number of inversions with two open slots. Hence, with 2 open spots, it is always solvable (for any size board $m \times n$ with $m,n \ge 2$).
