Yes, and no. If you generate the numbers randomly, I believe that there is a situation that could occur that causes the puzzle to be unsolvable. The way I'd suggest generating a puzzle is starting with the solved puzzle, and executing a number (increasing based on difficulty) of moves in reverse. That way you know that the end puzzle is solvable.
This discussion of The 15 Puzzle will probably give you the answer. I suspect that the analysis of the permutations in that puzzle will apply to your smaller puzzle.
From the french wikipedia on the "Taquin" (The 15 puzzle) :
Anecdote
Position initiale du taquin de Sam Loyd
Loyd affirma qu'il avait « rendu le monde entier fou » avec un taquin modifié. Dans la configuration proposée, les carreaux 14 et 15 étaient inversés, l'espace vide étant placé en bas à droite. Loyd prétendait avoir promis 1 000 USD à celui qui remettrait les carreaux dans l'ordre, mais la récompense n'aurait jamais été réclamée.
La résolution de ce problème est impossible. D'une part, il faut en effet échanger les places des carreaux 14 et 15, et l'on peut montrer que cette opération nécessite un nombre impair de glissements. D'autre part, il faut que la case vide retrouve sa place initiale, opération qui, quant à elle, nécessite un nombre pair de glissements. Il est toutefois possible d'ordonner les chiffres de 1 à 15 si la case vide est initialement en haut à gauche.
Anecdote
Initial position of Sam Loyd's 15 puzzle
Loyd said he had "made the world crazy" with a 15 puzzle modified. In the proposed configuration, the tiles 14 and 15 were reversed, the empty space being placed in the bottom right. Loyd claimed to have promised 1 000 USD for one who would put the tiles in order, but the reward was never claimed. Solving this problem is impossible. On the one hand, it must indeed swap the places of the tiles 14 and 15, and it can be shown that this operation requires an odd number of slides. On the other hand, the empty space must go back to its original position, an operation which, requires an even number of slides. It is possible to order the numbers 1 to 15 if the empty space is initially in the upper left.
Resources :