I remember making that puzzle in C++.

Half of the random states created are solvable, and the other half are unsolvable.

My solution was not checking if the puzzle is solvable (the mathematics of this seem complicated), but starting with a solved one and then do a fixed number of random movements.