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

Tuatara

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.

Protonema

It is possible to answer the question "can the permutation that solves the puzzle be produced by combining the permutations corresponding to elementary moves of the puzzle?" in polynomial time. Unfortunately, the more group theory you know the faster you can solve it, so most of the references are incomprehensible (at least to me). Knuth has a paper at arxiv.org/pdf/math.GR/9201304.pdf that is merely so densely written that it takes some time to notice that it solves this problem at all - the clue is the phrase "There is an easy way to test if a given perm..." – Xerxes

@Tuatara Cool! Check that Knuth paper.. if you dare for a possibly better solution. – Protonema