Does the position of the blank in an n-puzzle solution affect the set of valid puzzles?

Question

I'm having trouble with my n-puzzle solver. Thought it was working, but it turns out it is solving insoluble puzzles. I've tried to trace it, but that's a lot of tracing and so far I see no cheating. I think I understand the algorithm for determining solubility, and my implementation agrees with the odd/even parity of some examples from the web... that is to say, when I count up the number of tiles after a given tile that are smaller than it, for every tile, and then add the row index of the blank tile, I get the same odd or even number as others have gotten.

So a thought that has occurred to me. In my model of, say, the 8-puzzle, my solution state is:

_ 1 2
3 4 5
6 7 8

Rather than

1 2 3
8 _ 4
7 6 5

Or

1 2 3
4 5 6
7 8 _

As it is in some other formulations. Could this be affecting which puzzles are soluble and which are not?

Thanks!

z.

Answer 1

In general, yes: If a configuration is solvable to the standard solution, it will not be solvable to an unsolvable configuration.

In particular, it depends on the exact configuration you're using as a solution. You will need to check to see if you can solve from that configuration to the standard one.

EDIT: This of it this way:

Let A be the standard solution. Let B be your preferred solution. Let C be your starting configuration.

If you can get from A to B, and you can get from C to A, then you can get from C to B. But if you can't get from A to B, and you can get from C to A, then you can't get from C to B.