Regarding approach to solving sliding tiles puzzle

Question

I have started reading "Think Like A Programmer" by V Anton Spraul. Here is the question.

The train technique mentioned in the book works fine for the example sighted in it. I was attempting to write the train approach method to solve the sliding tiles problem.

Assuming that I am working on subset of the complete problem, for the below set of tiles (as given as example in the book), the approach mentioned works fine.

6 8 .

5 4 7

We move anti-clock wise until we get 4,5,6 in order in top row and then slide 8 over empty space to get all in order.

But for the below, I could not find any suitable method

. 8 6

7 4 5

Is it possible that there can be permutations where the puzzle is unsolvable?

Thanks,

/MS

Answer 1

Yes, in fact some puzzles are unsolvable. The way to find out is to try to solve two puzzles at a time: one being the original puzzle, and one being the original puzzle with two tiles switched. When you solve one puzzle, you know that the other one cannot be solved.