Searching the web, I found estimates of what percentage of solitaire hands are winnable for different games, but those estimates were often wildly inconsistent and there was rarely much explanation of where they came from. Most are probably player's estimates of how many games can be won, which obviously varies widely with the skill of the player. Serious analysis appears only to have been done for a few popular games, notably FreeCell and Klondike, and some of their variations.
I'm not a particularly talented solitaire player. My interest in the subject is mainly that of a programmer. So data on how many games I personally can win would be both uninteresting and embarrassing. But I thought it might be interesting to write programs to solve a variety of solitaire games, and use them to explore what fraction of games it is possible to win.
This doesn't really provide an entirely satisfactory measure of the difficulty of a solitaire game. Some games where nearly all deals can be won are nevertheless very difficult to win. But it is an upper bound on the percentage of games that can be theoretically be won, and we'll be able to more firmly discount the claims of people who say they won 100% of 18,000 games of Canfield.
But off the computer, complete randomization is probably the exception rather than the rule. A friend of mine, Mark Conger, is one of several mathematician who have studied card shuffling. It turns out that the classic riffle shuffle really is a good way to randomize a deck of cards, but only if you do a lot of shuffles. The mathematical result that many people have heard is that seven shuffles will do a pretty good job of randomizing a deck of 52 cards. This isn't always really true, many games require less, and some require more, but it's a good rule of thumb.
In any case, it's a good bet that most solitaire players don't shuffle seven times between games. I'd guess that most people only shuffle two to four times. Given that most solitaire games sort the deck a lot while being played, and many are very sensitive to the order of the cards, it seems likely that they may play very differently if the cards are not completely randomized between games.
It seemed to me that many older solitaire games may have been designed to be played this way. It's quite possible that putting them on a computer where the cards are relentlessly randomized before each game makes them play worse, not better. I thought there might be some circumstantial evidence for this in the fact that some of the most popular computer solitaire games, like FreeCell, are games that were little known before the computer age, while classic games like Canfield have become relatively less popular.
Bridge tournaments are often played with computer-shuffled hands now, and there is a lot of controversy over this. Many players think computer shuffling substantially alters the hands, increasing the odds of unusual distributions of cards. Others seem to think it is all in their imaginations. Bridge is a difficult game to analyze. Solitaire is much simpler.
So one of my objectives in these experiments was to try to investigate some of the impact of shuffling techniques on solitaire games. In the end, my overall impression is that people who shuffle three or four times between games aren't going to see spectacular differences between physical and computer solitaire, though the difference is going to be noticeable for some games. Only with really bad shuffling will you see really big differences.
Mark provided me with a nice algorithm for simulating manual shuffles on the computer which is used in all tests, and which can be used when playing games on Politaire.com. It's based on the Gilbert, Shannon and Reeds model of shuffling, often called the GSR model. There is a small amount of experimental evidence suggesting that it isn't a bad model of what people really do when they do manual riffle shuffles. (Though I personally suspect that inexperienced shufflers, or people with unevenly worn decks, may deviate substantially from the model.) I also did a few tests using a simulated overhand shuffle, which mostly just confirmed what everyone already knew - it's not a very good way to shuffle.
A single deck is ordered or in increasing order if, when held face up, the sequence from the bottom card to the top card is:
| A♠ | 2♠ | 3♠ | 4♠ | 5♠ | 6♠ | 7♠ | 8♠ | 9♠ | 10♠ | J♠ | Q♠ | K♠ |
| A♥ | 2♥ | 3♥ | 4♥ | 5♥ | 6♥ | 7♥ | 8♥ | 9♥ | 10♥ | J♥ | Q♥ | K♥ |
| A♣ | 2♣ | 3♣ | 4♣ | 5♣ | 6♣ | 7♣ | 8♣ | 9♣ | 10♣ | J♣ | Q♣ | K♣ |
| A♦ | 2♦ | 3♦ | 4♦ | 5♦ | 6♦ | 7♦ | 8♦ | 9♦ | 10♦ | J♦ | Q♦ | K♦ |
If we have multiple decks, they are ordered if each deck was separately ordered, and they are just stacked on top of each other.
A reversed deck is in the opposite sequence, in decreasing order so the first card dealt from it would be the K♦.
When we deal out a solitaire games, our normal procedure is to deal the tableau column by column, starting from the left. Note that dealing this way reverses the order of the cards in the columns, so that if we dealt a column of three cards from an ordered deck then the top card would be 3♠, with 2♠ under it, and A♠ on the bottom. Any reserve columns are dealt the same way.
The stock, however, is not flipped over, so the cards are not reversed. If we were dealing an ordered deck out to play Ali Baba, for which we'd need 40 cards on the tableau, leaving 12 cards for the stock, then the first card turned up off the stock would be 2♦ followed by 3♦, and 4♦, and so on.
Sometimes we start games not with a fresh deck, but from the cards gathered up after a previous game. For these tests I used a standard procedure for gathering up the cards:
Obviously this procedure is somewhat arbitrary, and doesn't represent how all players play. But I had to pick some standard for our tests, and these are the ones I used.
The source code is open source and available from the Google Code. You'll need to check it out from the "trunk" subdirectory of the source responsitory.
Most games use a simple depth-first search engine. After cards are dealt, the solver starts a loop where it finds all possible moves, and uses a game-dependent heuristic function to rate the moves. The heuristic function may mark some moves as "safe," moves that can never be wrong. Those are made immediately and will not be choice points if we backtrack in the future. Otherwise, we pick the best rated move and make it, recording it in our move history as a choice point, and saving the rest of the moves on our list with it.
If we reach a point where there are no moves possible, then we start backtracking. We undo moves until we reach a choice point with other saved move alternatives. We then pick the best of those and continue.
After each move, we encode the current game state as a string (the encoding is game dependent), and save that in a large hash table. If we ever return to a state we've been in before, we immediately backtrack. This is common, because often we can reach the same state by removing the same cards in different orders, and in some games it is possible to go in circles. This state hashing is very important to pruning off such redundent searches and getting decent performance.
So the whole thing is actually pretty dim-witted, and for any particular solitaire game it may well be possible to do much, much better. For many games this is good enough, but many of the more complex games would require substantally smarter solvers.