Comment by oessessnex

It's even simpler than that. You can randomly generate a valid sequence of moves (i.e you are a pawn at a2, move to a3, become knight, move to ..., move to ..., become ..., ...), instead of the initial board state and that guarantees the puzzle is solvable. The only thing you need to watch out for is that you are not allowed to touch squares that appear in previous moves.