Experimental Analysis of
Cruel Solitaire

Jan Wolter
January 15, 2014

[General Introduction]

The Game

Cruel Solitaire is played with a single deck of cards. The goal is to move the them all to the four foundation piles, where we build upward from ace to king, in suit. The four aces start on the foundation, and the other 48 cards start face up on the tableau, in 12 piles of 4 cards each. Only single cards can be moved. You can build down in suit on the tableau. Empty tableau spaces may not be filled. If you get stuck, you may redeal the tableau any number of times, picking the cards up column by column from top to bottom, and then dealing them out again, without shuffling, in the same order, but with only four cards per column.

Nearly every description of the game that I've read says redeals can be done "when no other moves can be made," but every computer implementation I've seen allows you to redeal at any time. Allowing redeals at any time certainly increases your options and improves your chances of winning the game. Sometimes the only way to win is by redealing when there are still movable cards.

You can read the rules for Cruel or play the game on Politaire.com or on many other websites.

This game resembles Indefatigable and Royal Marriage but is more difficult for human players. Those games allow building both up and down on the tableau. Redeals are done in a manner that more thoroughly disrupts the card order, collecting cards column by column, and dealing them dealt row by row. Only a limited number of redeals are permitted.

Redeal Algorithms

At the time of writing, the Wikipedia article about Cruel was quite adamant about what the correct redealing method was:
Note: Many people who play this game or create certain computerized versions thereof erroneously believe that the cards are "shuffled" by taking the last pile and putting it on top of the next-to-last pile and so on, then putting the bottom four cards in the first pile, the next four cards in the second, and so on. The technically correct order is to "shuffle" by taking the cards on the first pile, putting them on top of the cards from the second pile, then on top of the third, and so on, then taking the top four cards and putting them back in the first pile, then the next four cards in the second, and so on. Only about one in six to one in five people can win the game using the incorrect "shuffling" method; however, the chances of winning using the correct method are significantly higher, about one in three or two in five.
The redeal method really does make a significant difference to the play of the game. Digging cards out from the bottom of the first column is always a challenge in Cruel. The example below shows the different result of a correct and incorrect redeal after one card has been removed from the first column:
With the correct redeal algorithm, our progress in digging down toward the three of spades in the first column is not lost. With the incorrect redeal algorithm, we are back where we started.

The next image shows the results of the two redealing methods after one card has been added on top of the first column:

Note that with the correct redeal algorithm, adding a single card to the top of the first column is sufficient to extract both twos from the bottoms of their respective columns. These examples make it clear why the author of the Wikipedia article says that the correct redeal algorithm doubles your chances of winning.

I find it easier to describe the correct algorithm as:

and the incorrect algorithm as: Here the "top" card is the card that is playable (which is normally nearer the bottom of your screen which is confusing), and the first card dealt is the first card that was picked up. In either case, if we started with a tableau with four cards in each column, we'd end up with the exact same tableau, but as seen above, when cards have been moved, the two algorithms give very different results.

The anonymous author of the Wikipedia page includes estimated win rates for a human player of 33% to 40% with the correct dealing algorithm or about half that with the incorrect dealing algorithm. We'll analyze both options here.

Solver

I adapted my depth-first-search solver for Indefatigable to play these games. The first version of the solver allowed redeals to be done at any point in the game, but these lead to too much combinatorial explosion, so I modified the game to only do redeals when no other moves are possible. This restriction undoubted reduces the number of winnable games.

Results

My solver was able to find solutions for 744,684 of the first million Politaire Cruel games, seeds 0 through 999999. This is a 74.5% win rate. An average of 46.4 cards were removed.

If we use the alternate, bottom to top, deal order, then only 466,977 out of a million games were solvable, for a 46.7% win rate. Clearly the Wikipedia page was correct in saying that the game is much harder when it is played this way, and its estimate that it is about twice as hard was not far off.

My solver doesn't work well if we allow redeals to be done at any time, instead of only when there are no other moves to be made, but partial results are sufficient to indicate that allowing redeals at any time significantly improves the percentage of games that are winnable. I ran that version of the solver on 10,000 random Cruel deals (Politaire seeds 0 through 9999) and was able to solve about 87% of them. For most of the remaining games, the solver got lost in a combinatorial explosion and had to be terminated without a result. Less than 2% of the puzzles were conclusively proven to be unsolvable. This means the percentage of winnable games is actually somewhere between 87% and 98%.

To win games of Cruel, it is clearly important to chose the right moments to redeal, so that the redeal will bring cards you want to the surface. This is not too hard for a human player to do if you are only looking one redeal ahead, but looking ahead over multiple redeals quickly becomes nearly impossible. Thus the human player's win rate is going to fall far short of the theoretical maximum win rate.