Is it Possible to Solve Any Sliding Tile Puzzle with a Single Empty Space?

[Johnny B.]

Given any two random tile arrangements in a sliding tile puzzle, is it always possible to find a way to go from one to the other? It's trivial to prove that this isn't true for 2x2 puzzles, but I don't know how to approach the problem for bigger sizes, short of brute forcing it with a computer. Can you help me find a more elegant solution?

 

[HallsofIvy]

No, you cannot go from one arrangement to any other.
The basic idea is that, if you write a given position as a permutation of the original position- that is, number the tiles 1, 2, 3, ..., up to the number of tiles starting from the upper left and going by rows- show that any "reachable" position must be an even permutation of the original position.

Historically, the original version of the "15" puzzle, instead of having 15 numbers, set in a 4 by 4 grid with a single empty position, had the letters "rate your mind bud ". You could show the original position to a friend, mix up the letters and challenge him to put them back into the original position. The "trick" was to move the "r" in "your" to the first position. People would almost automatically leave that "r" alone since the original form has an "r" there. But switching the two "r"s is an odd permutation. You can't get all the other letters in the original position with the two "r"s reversed.