Experimental Analysis of
Captive Queens Solitaire

Jan Wolter
April 10, 2013

[General Introduction]

The Game

Captive Queens is a very simple solitaire game with twelve foundation piles, a stock pile, a waste pile, and no tableau. Cards are dealt one at a time from the stock to the waste, and the top card of the waste may be played to a tableau pile if it fits. The first two times the stock runs out you may turn over the waste pile to form a new stock pile. If you don't move all cards to the foundations by the end of the third pass through the stock, you lose the game.


The twelve Captive Queens foundation piles with the first card in each. (Wikipedia Image)
The twelve foundation piles are traditionally arranged in two concentric circles, as shown at right. The four center piles each may hold one queen. Four of the piles in the outer ring are begun with a six and built upward, with cards of the same suit, in the following sequence:
6 7 8 9 10 J
The other four piles in the outer ring are begun with a five and are built downward, with cards of the same suit, in the following sequence:
5 4 3 2 A K

Sometimes the game is begun with the queens, fives, and sizes already dealt to their foundation piles, but I will be focusing on the slightly more difficult variation where each foundation pile starts empty. You can read the rules or play the game on politaire.com, (although that program does not lay out the foundation piles in the traditional pretty pattern which gives the game it's name). There are a number of other very similar games, including Sixes and Sevens, Contradance, and Dorothy.

Playing this game will be of little interest to people looking to exercise their intellect. There is no better strategy than to move every possible card to the foundation and hope for the best. No planning or decision making is required, just a modicum of alertness.

Like many other more complex solitaire games, Captive Queens is basically a card sorting game. We are given a shuffled deck and need to put it into order using only the tools that the rules of the game allow us. Many games have a tableau that can be used as a buffer space to make this sequence building easier, but Captive Queens does not. It has just two features to make it playable: the many short foundation piles, and the waste pile.

The fact that the tableau piles contain no more than six cards each, instead of thirteen cards as in other solitaire games, makes them considerably easier to build. The queens, of course, will always all come down on the first pass through the stock, as will all the fives and sixes. Because no foundation is more than six cards long, it is clear that no more than six passes would ever be needed to get all the cards onto the foundations.

The waste pile is also a deceptively powerful tool. Obviously one of the best possible starting decks would be one where all the cards are already in the correct order (we'll call this "Captive Queen order"), where each suit is arranged like:

5 4 3 2 A K 6 7 8 9 10 J Q
We could play each card to the foundation as it comes off the stock and win in one pass.

One would think that the worst possible ordering of the deck would be the reverse of Captive Queen order, but, in fact, that too can be won in one pass. We play all the cards onto the waste, and then we can play them to the foundation from the waste one by one. The waste allows us to reverse the entire deck, or any subsequence of the deck, and so becomes a powerful sorting tool.

It also means that it never actually takes six passes to get all the cards off. At the end of the fifth pass all cards except jacks and kings are guaranteed to be on the foundation. But any remaining jacks and kings will be in the waste, and can all be played out of the waste without the need for starting a sixth pass.

Fully Randomized Deals

To further investigate this game, I wrote a program to play the game. This is not particularly difficult since the game is so simple. I ran the solver on the first million Politaire games, seeds zero through 999999 and found that 587,714 of them (59%) could be solved in three passes or less. If we allow the solver to keep making passes until all cards are out, we get the following distribution:
Number of
Passes
Number of
Games Solved
10     
23,521     
3584,193     
4411,221     
51,065     
We have already shown that no more than five passes are ever needed, this shows that five passes are sometimes needed, though only for one game in a thousand. And though it is obviously possible to solve the game in one pass, the odds of that happening appear to be less than one in a million.

In the variant where the fives and sixes are pre-dealt to the foundation, 97% were winnable in three deals and 12% were winnable in two deals. Even with this easier version, only about two in a million were winnable in a single deal.

Natural Shuffling of Gathered Cards

But traditionally this game would not have been played with fully randomized decks. What if, instead of fully randomizing the decks, we end each game by picking up the cards in the order they lay on the table, give the deck a few riffle shuffles, cut it once, and deal a new hand? Clearly some ordering would survive into the next hand, and since this game is very sensitive to the ordering of the initial deck, the results might be very different.

So, using a shuffling algorithm based on the GSR (Gilbert, Shannon and Reeds) model of riffle shuffling, we played a sequence of a million games in this manner for each number of shuffles from one to ten. In this experiment we' never allowed more than three passes, because if we ran until the game was solved, then we'd always be starting with a fully sorted deck before shuffling for the next game.

The results are shown on the graph below, where the colored areas represents games solved in one, two or three passes:

Captive Queens Win Rate with n Shuffles of a Gathered Deck
Red = Won in One Pass; Blue = Won in Two Passes; Green = Won in Three Passes;

Note that with 10 shuffles we have a 59% win rate, pretty much identical to that for a fully randomized deck. With only one or two shuffles, we won every single game (except for the first one, which was in all cases an unsolvable game not resulting from gathering cards from a previous game). Clearly this game becomes much easier if the cards are shuffled naturally.

Note that I also tried these runs using a alternate shuffling method where, instead of starting with the cards gathered up from the previous deck, I always start with a deck pre-sorted into Captive Queen order. The results were virtually identical to the ones above. Even failed games tend to get so many cards off that the difference between that and a fully ordered deck is negligible.

Interestingly, with seven shuffles we are winning 66% of all games, significantly more than the 59% win rate expected for fully randomized decks. This seems to contradicts the widely held belief that seven riffle shuffles is enough to randomize a deck of 52 cards.

Well, in fact, seven shuffles are not always enough. That belief is based on a famous 1992 paper by Dave Bayer and Paul Diaconis that analyzed the very GSR model of riffle shuffling we use here. It includes a long discussion of the weakness of riffle shuffles in disrupting "rising sequences" of cards and even describes a magic trick based on this weakness. Captive Queens is a game that depends on rising sequences, so the seven shuffles that suffice for many games does not suffice for Captive Queens. There has been a paper by Anke van Zuylen and Frans Schalekamp published showing this to be the case for a solitaire game called "New Age" that in some ways resembles Captive Queens.

I studied this a bit further by modifying the rules of Captive Queens to make it into more of a pure rising sequence counting game in another note.