0
$\begingroup$

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| | 
$\endgroup$

1 Answer 1

2
$\begingroup$

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$).

$\endgroup$
4
  • $\begingroup$ By one missing tile, you mean 8 tiles in total, not 7? What do you mean by saying two neighboring tiles have been switched? For sure the board can be more mixed than what that sounds. $\endgroup$
    – Antti_M
    Feb 2, 2017 at 16:20
  • $\begingroup$ @Antti_M Yes, an unsolvable board can be mixed up more than that, but you can always get an unsolvable board to a state where only the 7 and the 8 are switched (or any two neighboring squares). $\endgroup$
    – Bram28
    Feb 2, 2017 at 16:28
  • $\begingroup$ @Antti_M And you can always take the line of reasoning that for an unsolvable 8-puzzle, there will always be an odd number of inversions ... with the 7-puzzle, you can get any number of inversions. $\endgroup$
    – Bram28
    Feb 2, 2017 at 16:30
  • $\begingroup$ @Antti_M Oh, and yes, by '1 missing tile' I meant the 8-puzzle. I guess I should have said '1 open slot' $\endgroup$
    – Bram28
    Feb 2, 2017 at 16:31

You must log in to answer this question.

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