I think if I were going to guarantee solvability, I'd probably try to write it backwards: perform a series of random reversed operations (I think moving any stack of sequential cards to any destination is a "legal" inverse move) to a solved game until it ends up in a shuffled state.