It's even simpler than that. You can randomly generate a valid sequence of moves (i.e move to a3, become knight, move to ..., move to ..., become ..., ...) instead of the initial board state and that guarantees the puzzle is solvable.