For those that are not familiar with (this type of) sliding puzzles, basically you have a number of tiles on a board equal to (n * m) - 1 (possibly more holes if you want). The goal is to re-arrange the tiles in such a way that solves the puzzle.
The puzzle could be anything, from number games to images.
While writing a small app for this, I found that if I were to initialize the puzzle by randomly shuffle all of the pieces, I could end up in a situation where there is no solution if my puzzle was 2x2.
So the problem I have is: given a sliding puzzle with n-by-m dimensions, is there always a solution if there are a sufficient number of tiles (eg: a 3x3 board)? How would I even begin to prove this, or simply convince myself that it is the case?
If it is possible that a random shuffle could result in no-solution, then I'd have to figure out how to verify that there exists a solution, which is a completely different beast.