OddThinking

A blog for odd things and odd thoughts.

Introducing Captive Queens

Captive Queens is a solitaire card game.

In this post, I will describe the rules, analyse the tactics, simplify the game to an equivalent one and determine the chance of winning.

Stop Press: This analysis is flawed, and the conclusion is incorrect.

Rules of Captive Queens

You start with a single deck of shuffled cards face down (the “stock”), and room in front of you for:

• four “reserve” piles for the queens.
• eight “foundation” piles – four are “up” piles, and four are “down” piles.
• a waste pile.

(There is a traditional layout of the positions of the piles, which I am ignoring as purely decorative.)

One by one, you turn over the cards from the stock to the waste pile. From the top card of the waste pile, you may move a card to a foundation pile or the reserve piles, with following rules.

• Each Queen card may be put on its own reserve pile.
• Each 5 may be used to start its own down foundation pile.
• Each 6 may be used to start its own up foundation pile.
• On an up foundation pile, you may put a card of the same suit, ascending by one rank, through to the Jack. i.e. if there is a 6 of spades, you may put the 7 of spades. On that, you may put then 8, then 9, 10 and finally the Jack.
• On a down foundation pile, you may put a card of the same suit, descending by one rank, rolling over at the King, and stopping at the King – i.e. 5, 4, 3, 2, A, K.
• When the stock pile is complete, you may turn over the waste pile and start again. You may do this twice, meaning you run through the stock three times.

The goal is to have every foundation and reserve pile full before you finish going through the stock three times.

This should be enough information to play. Feel free to try it before I break it down.

Tactics

Each card on the top of the waste pile has a single intended destination – a single foundation/reserve pile where it belongs. Each time it is visible, it can either be played in that position, or it can’t.

If it can’t be played, then there is no choice but to turn over another foundation card.

If it can be played, there are two choices – play it now, or turn over another foundation card. In this situation there is no reason not to play it immediately. It advances the goal to play it. It achieves nothing to leave it where it is.

That deals with the only choice offered to the player in the game. The single tactic in this game is to play a card to its only legal position whenever it is legal.

So, this turns out to be a mindless game, like Clockwork Solitaire. There is no skill. You play like an automata. The only thing left to do to analyse it is to work out your probability of winning.

Captive Nulls

To tackle the question of the probability of winning, I will start by simplifying the rules into a game with an equivalent chance of winning, that is easier to talk about.

Firstly, notice the Queens and the reserve piles. Every Queen is always discovered in the first run through the stock and placed in its own reserve pile, and then has nothing more to do with the game. The Queens are irrelevant. By simply starting with a 48 card deck, we can eliminate them from the game.

Now, notice that the goal to have half the foundation piles ascend in sequence, and half the piles descend in sequence is irrelevant. Instead, of starting the foundations with 5 and 6, we could start them with K and 6, and have them both ascend. (i.e. K, A, 2, 3, 4, 5 and 6, 7, 8, 9, 10, J.)

Now, the two piles in each suit don’t really have anything to do with each other, as suits. We could split them into separate suits to simplify. Take out a thick felt-tipped pen and relabel all the lower cards (K, A, 2, 3, 4, 5) as A, B, C, D, E, F. Then label the higher cards as A, B, C, D, E, F too, but also give them a new suit. Make up four new ones. Anything you like. This is fun!

So, now we have a new, but probabilistically equivalent, game. Instead of Captive Queens, I call it Captive Nulls (as there are no Queens in the game). It has a deck of 48 cards, consisting of 8 suits of cards ranked A through to F, and requires you to create 8 foundation piles ascending A to F in the corresponding suits.

Eight Independent Games

THIS SECTION IS FLAWED. See the comments by Jan Wolter which demonstrate I have made a fundamental error in my analysis below.

The next step is the realise that to solve the game, each of the suits must be solved. If you consider the problem from the perspective of each one of those suits, the other suit cards are irrelevant – the suits don’t interact in any way. All that matters is the order in the stock of the cards of that particular suit. The other cards may as well be blank – or not present.

So, each of the 8 suits can be isolated and calculated independently of the others. The chance of winning the game is simply the product of the chances of winning each suit.

The chance of solving each suit is identical, so the overall probability of winning, is the probability of solving one suit, multiplied to the power of 8.

Chance of Solving One Suit

So, here is where it gets interesting. We can discard all the cards except six from one suit, and ask “What is the probability that going through these cards three times, we can find the sequence A, B, C, D, E, F?”

We know how many permutations there are. 6! = 720. How many are solvable?

This problem turns out to be trickier that it first seems. I tried a few approaches, brought it up with a few mathematically-inclined friends, and watched them try the same approaches.

We never did solve it for the general case, but for n=6 there are only 720 combinations so it is quite feasible to exhaustively search, even if it makes me feel a little dirty. (As I said about the Monte Carlo method, this technique “skips the niceties of logical analysis to use sheer brute force to solve a problem”.)

My Python code is below. It works by generating every permutation, repeating it three times (to represent the three run throughs), and then searching it to find the sequence ABCDEF, with possible irrelevant letters in between. It counts the number of permutations that have this sequence.

``` from itertools import permutations from re import compile solved_pattern = ".*A.*B.*C.*D.*E.*F.*" solved_re = compile(solved_pattern) def solvable(permutation_list): repeated_str = ''.join(permutation_list) * 3 return solved_re.match(repeated_str) solvable_count = sum( 1 for permutation in permutations("ABCDEF") if solvable(permutation)) print solvable_count ```

The result is a nice round 360.

That gives a probability of solving a single suit as 360/720 = 1/2.

Which means the probability of solving the whole puzzle is (1/2)8 or one in 256.

Conclusion

There’s no need to have a deck of cards to play Captive Queens. If you ever have the urge, simply flip a coin eight times. If you get 8 heads, you won.

Due to the flaw in the argument, this previous conclusion is false. The new conclusion: Julian is a dunderhead.

1. Hi. I stumbled upon your website because I was looking for nonogram solvers to include in my survey. Curious to see what you’ve been doing lately, I followed a link to your latest post and found that you had analysed this stupid obscure Solitaire game that I just happen to have done a Monte Carlo analysis of just last month. Weird coincidence.

Alas, our answers don’t agree. We aren’t even close. I found 59% of games winnable.

I think you are overlooking the fact that, under the normal rules, after you play a card from the waste, you don’t have to deal a new card. You can play the next card from the waste. So if the cards were all backwards, FEDCBAFEDCBA, you could still win the game easily by playing all cards to the waste, and then playing them off the the waste in reverse order. In effect, you can use the waste to reverse any subsequence of the deck as you make a pass through the deck. This helps hugely.

But this brings up another problem. The suits aren’t separable once you allow playing multiple cards off the waste. FEDCBA of hearts is easily winnable without a redeal, but not if there is some other unplayable card of another suit between the B and the A of hearts. This loss of separability makes the analysis quite a bit more difficult. Too difficult for me anyway, which is why I fell back on doing the dim-witted Monte Carlo thing.

2. Jan,

Whoa! Good point. I need to give this some more thought.

3. Just noticed that I seem to have messed up on my links. They should be
http://webpbn.com/survey/
and
http://politaire.com/article/captivequeens.html

By the way, I too spent several days thinking myself smart for noticing that the suits in Captive Queens were separable before I saw the flaw in that argument.

4. If I have it right, the tactics are still just to play cards to legal positions whenever you can. So instead of 8 heads, you need to roll better than 41 on percentile dice.

I thought about the original problem, and I can’t see a good general solution (is there a group theorist in the house?) But there is some exploitable symmetry.

The better a sequence is for getting out forward (ABCDEF), the worse it is for getting out reverse (FEDCBA) – any two cards that are correctly ordered for forwards are incorrectly ordered for reverse. Since forward and reverse are symmetrical, the number of permutations that will work at each number of runs is also symmetrical (the more that work forward, the fewer work reverse).
In particular, the number of permutations that will work for n/2 runs forward is the same as the number that will work for n/2 runs backwards, and this must therefore be half the total number of runs.

So in the special case of n/2 runs through n cards, your 50% chance is not a coincidence.

5. For those who haven’t worked it out, Jan Wolter’s comments above have completely undermined my analysis.

After more thought, I cannot see any way to easily fix the error. I have updated the article to insert warnings that I have made a huge mistake.

Sorry for the mistake. Props to Jan for figuring this out; thank you! (And sorry for taking so long to update it.)