Does a 15-puzzle always have a solution 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.
Martin Gardner had a very good writeup on the 14-15 puzzle in one of his Mathematical Games books.

Sam Loyd invented the puzzle.  He periodically posted rewards for solutions to certain starting configurations.  None of those rewards were claimed.

Much analysis was expended, and it was finally determined, through a parity argument (as mentioned in the comment above), that half of the possible starting configurations were unsolvable.  Interestingly, ALL of Loyd's reward configurations were unsolvable.

SO: No, every possible configuration is not solvable.  If you START with a solved puzzle, and apply only legal transformations (moves) to it, you always wind up at a solvable configuration.

For the GENERAL nxm question, you'd probably have to expand the parity argument.
Here, we consider the following problem:
For a given position on the board to say whether there is a sequence of moves leading to a decision or not.

Let there be given a position on the board:

+------------------+.  
| 11 | 15 | 2 | 13 |.  
|----|----|---|----|.  
| 14 | 1  | 8 | 3  |.  
|----|----|---|----|.  
| 7  | 6  | 0 | 10 |.  
|----|----|---|----|.  
| 4  | 12 | 9 | 5  |.  
+------------------+.


wherein one of the elements is zero and indicates an empty cell.
Consider the numbers in the matrix serially (rowwise):  

11 12 2 13 14 1 8 3 7 6 0 10 4 12 9 5


Denote N - the number of inversions in the permutation (i.e. the number of such elements a[i] and a[j] that i &lt; j but a[i] > a[j]).

Next, let K- line number in which there is an empty element (i.e. in our notation K = 3).

Then, a solution exists if and only if N + K is even.