For the Windows rules, Wikipedia claims that 82-91.5% of Klondike Solitaire games are solvable. This probably checks all possible moves from an initial position (i.e. that you backtrack if you get stuck). I was wondering what the odds are for a naive strategy (i.e. me), because I can rarely be bothered to backtrack.

On the other hand, Windows Solitaire probably doesn't use the CryptoAPI RNG, so you might be right there...