{"id":1777,"date":"2013-05-30T12:22:08","date_gmt":"2013-05-30T02:22:08","guid":{"rendered":"http:\/\/www.somethinkodd.com\/oddthinking\/?p=1777"},"modified":"2013-06-24T12:04:43","modified_gmt":"2013-06-24T02:04:43","slug":"analysis-of-captive-queens","status":"publish","type":"post","link":"https:\/\/www.somethinkodd.com\/oddthinking\/2013\/05\/30\/analysis-of-captive-queens\/","title":{"rendered":"Analysis of Captive Queens"},"content":{"rendered":"<h2>Introducing Captive Queens<\/h2>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Captive_Queens\" title=\"Wikipedia definition of Captive_Queens\" class=\"wikipedia\">Captive Queens<\/a> is a solitaire card game.<\/p>\n<p>In this post, I will describe the rules, analyse the tactics, simplify the game to an equivalent one and determine the chance of winning.<\/p>\n<p><strong>Stop Press:<\/strong> This analysis is flawed, and the conclusion is incorrect.<\/p>\n<h2>Rules of Captive Queens<\/h2>\n<p>You start with a single deck of shuffled cards face down (the &#8220;stock&#8221;), and room in front of you for:<\/p>\n<ul>\n<li>four &#8220;reserve&#8221; piles for the queens.<\/li>\n<li>eight &#8220;foundation&#8221; piles &#8211; four are &#8220;up&#8221; piles, and four are &#8220;down&#8221; piles.<\/li>\n<li>a waste pile.<\/li>\n<\/ul>\n<p>(There is a traditional layout of the positions of the piles, which I am ignoring as purely decorative.)<\/p>\n<p>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.<\/p>\n<ul>\n<li>Each Queen card may be put on its own reserve pile.<\/li>\n<li>Each 5 may be used to start its own down foundation pile.<\/li>\n<li>Each 6 may be used to start its own up foundation pile.<\/li>\n<li>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.<\/li>\n<li>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 &#8211; i.e. 5, 4, 3, 2, A, K.<\/li>\n<li>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.<\/li>\n<\/ul>\n<p>The goal is to have every foundation and reserve pile full before you finish going through the stock three times.<\/p>\n<p>This should be enough information to play. Feel free to try it before I break it down.<\/p>\n<hr \/>\n<h2>Tactics<\/h2>\n<p>Each card on the top of the waste pile has a single intended destination &#8211; a single foundation\/reserve pile where it belongs. Each time it is visible, it can either be played in that position, or it can&#8217;t. <\/p>\n<p>If it can&#8217;t be played, then there is no choice but to turn over another foundation card.<\/p>\n<p>If it can be played, there are two choices &#8211; play it now, or turn over another foundation card. In this situation there is <em>no reason<\/em> not to play it immediately. It advances the goal to play it. It achieves nothing to leave it where it is.<\/p>\n<p>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. <\/p>\n<p>So, this turns out to be a mindless game, like <a href=\"http:\/\/www.somethinkodd.com\/oddthinking\/2005\/05\/31\/beating-the-clock-solitaire\/\">Clockwork Solitaire<\/a>. 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.<\/p>\n<h2>Captive Nulls<\/h2>\n<p>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.<\/p>\n<p>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.<\/p>\n<p>Now, notice that the goal to have half the foundation piles <strong>ascend<\/strong> in sequence, and half the piles <strong>descend<\/strong> 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.)<\/p>\n<p>Now, the two piles in each suit don&#8217;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!<\/p>\n<p>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.<\/p>\n<h2>Eight Independent Games<\/h2>\n<p><strong>THIS SECTION IS FLAWED.<\/strong> See the comments by Jan Wolter which demonstrate I have made a fundamental error in my analysis below.<\/p>\n<p>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 &#8211; the suits don&#8217;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 &#8211; or not present.<\/p>\n<p>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.<\/p>\n<p>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.<\/p>\n<h2>Chance of Solving One Suit<\/h2>\n<p>So, here is where it gets interesting. We can discard all the cards except six from one suit, and ask &#8220;What is the probability that going through these cards three times, we can find the sequence A, B, C, D, E, F?&#8221;<\/p>\n<p>We know how many permutations there are. 6! = 720. How many are solvable?<\/p>\n<p>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.<\/p>\n<p>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 <a href=\"http:\/\/www.somethinkodd.com\/oddthinking\/2005\/05\/31\/beating-the-clock-solitaire\/\">Monte Carlo<\/a> method, this technique &#8220;skips the niceties of logical analysis to use sheer brute force to solve a problem&#8221;.)<\/p>\n<p>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.<\/p>\n<p><code><\/p>\n<pre>from itertools import permutations\r\nfrom re import compile\r\n\r\nsolved_pattern = \".*A.*B.*C.*D.*E.*F.*\"\r\nsolved_re = compile(solved_pattern)\r\n\r\ndef solvable(permutation_list):\r\n    repeated_str = ''.join(permutation_list) * 3\r\n    return solved_re.match(repeated_str)\r\n    \r\nsolvable_count = sum(\r\n                    1 \r\n                    for permutation in permutations(\"ABCDEF\")\r\n                    if solvable(permutation))\r\n\r\nprint solvable_count<\/pre>\n<p><\/code><\/p>\n<p>The result is a nice round 360.<\/p>\n<p>That gives a probability of solving a single suit as 360\/720 = 1\/2.<\/p>\n<p>Which means the probability of solving the whole puzzle is (1\/2)<sup>8<\/sup> or one in 256.<\/p>\n<h2>Conclusion<\/h2>\n<p><strike>There&#8217;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.<\/strike><\/p>\n<p>Due to the flaw in the argument, this previous conclusion is false. The new conclusion: Julian is a dunderhead.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I introduce the game of Captive Queens, explain the rules, analyse the tactics and determine the chance of winning.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_s2mail":"yes","footnotes":""},"categories":[33],"tags":[],"class_list":["post-1777","post","type-post","status-publish","format-standard","hentry","category-puzzle-solving"],"_links":{"self":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/1777","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/comments?post=1777"}],"version-history":[{"count":14,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/1777\/revisions"}],"predecessor-version":[{"id":1788,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/1777\/revisions\/1788"}],"wp:attachment":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/media?parent=1777"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/categories?post=1777"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/tags?post=1777"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}