There exist starting positions that can not be solved.
To prove it let's write down the numbers in the squares row after row.
We will get a permutation of the set {1, 2, ... 15}. We can count the number
of inversions and see if this permutation is even or odd. It is very easy
to prove that when a square is moved in horizontal direction, the number
of inversions does not change, while when it is moved in vertical direction
the number of inversions changes by one or three (odd numbers). In the
puzzle below the number of inversions is one. From what was said it follows
that during the game the number of inversions remains odd whenever the
empty square is in the second or the forth rows. In the position when all
the numbers are ordered and the empty square is in the low right corner
the number of inversions is zero and thus it can not be reached from the
the position below.