Four Kings Solitaire

I've spent many hundreds of hours playing solitaire card games over the years, but my favorite solitaire is Four Kings Solitaire, described at Wikipedia using a different name. In contrast to FreeCell, where some cards may be moved hundreds of times before victory, in Four Kings each card can be moved at most twice; indeed the object of the game is to move each card legally exactly two times.

Rules of Four Kings

Use an ordinary deck of 52 cards; the suits and colors will be irrelevant. It's good to think of the Ace, Jack, Queen and King simply as 1, 11, 12, 13 (but we use the names A, J, Q, K here, along with T for Ten). There are four Goal piles, three Work piles, and the stock. The Goal piles and Work piles are initially empty. Goal pile #1 needs one card of each rank, played in order, counting by 1's, i.e. A 2 3 4 5 6 7 8 9 T J Q K. Goal pile #2 again needs thirteen cards in order, now counting by 2's: 2 4 6 8 T Q A 3 5 7 9 J K. Similarly Goal pile #3 needs 3 6 9 Q 2 5 8 J A 4 7 T K; and Goal pile #4 needs 4 8 Q 3 7 J 2 6 T A 5 9 K. If you win the game, all 52 cards will be in the Goal piles, all with Kings on top, hence the name of the game. Here is the procedure:

  1. Shuffle the 52 cards and leave them in a pile face-down. This is the stock or residue.
  2. Turn over the top card of the stock and place it on the top of one of three work piles.
  3. At your option, take the top card from any work pile and place it on the top of any Goal pile if that Goal pile is ready for it. For example, a Seven can be placed only on top of a Six in Goal pile #1, on top of a Five in Goal pile #2, on top of a Four in Goal pile #3, or on top of a Three in Goal pile #4.
  4. Repeat Step 3 as long as wish, if there are legal plays.
  5. Repeat from Step 2 unless the stock is empty.

(In practice, you will often turn over a card from the stock and move it to a Goal pile immediately; the rules pretend that you will park it tempoarily on a Work Pile just to be slightly simpler to state.)

Instead of just three Work piles, you will want to use four until you gain expertise. It is easily seen that you would always win if 12 Work piles were allowed: you'd place the 13th cards (all Kings) for the Goals on one Work Pile, the 12th cards (Q, J, T, 9) on another Work pile, and so on. It is also easily seen that 11 Work piles may not be enough. For example, if the cards come in the order 2 2 2 2 3 3 3 3 4 4 4 4 ... J J J J Q Q Q Q K K K K A A A A, then one of the threes will have to go on a Work pile different from a 2, else you will be unable to get to a 2 to play it on Goal pile #1. Similarly, a 4 must be on a pile distinct from the 3 and 2 destined for Goal pile #1; similarly a 5 will use a 4th Work pile, a 6 a 5th Work pile, ..., a Q an 11th Work pile, and a King would need a 12th Work pile.

An Interesting Tableau

To make the game more fun for me, I try to "claim" when victory is guaranteed. The remainder of this webpage considers a specific position in an actual Four Kings solitaire that I played, which seemed interesting enough to write down, analyze and discuss. The contents of Work pile #3 already make the game a bit funny-looking. Twelve cards are still in the Residual Stock; remember that you do not know in what order the Residue cards will appear.

This game started somewhat unluckily. The first King appeared late, so only two Work piles were available for much of the game. (It is usually best to dedicate one Work pile to receiving Kings.) By the diagram, however, all four Kings had appeared; and I turned over a 3 which I placed on Work pile #2. I think that was the best card I could hope for at that turn, and I paused to see if I could "claim" a win.

The first step in a claim is to guess which Goal pile a given card will play on to. (You actually keep track of this as you play.)

It is best, of course, to retain flexibility. I've marked two of the Sevens as flexibly assigned, as well as two of the Threes.

Only this Ace is troublesome

I will redraw the above, but moving the Residue cards to where they are likely to next be placed.

I've shown the Ace from the Residue at two different places with question marks. We'll get to this. (I also show alternate placements for Jack and Three.)

With the exception of that Ace, the placements shown are all feasible. Note that (again excepting Ace), at most one Residual card destined for any Goal is placed on a given Work. Victory is visible: The Goals will be ready for 6, T, 2, 3; all but the T are immediately playable from Work #3; after further plays from Work #3 the Goals will be ready for 8, Q, 5, J; three of these are cards we just added to Work #2 from the Residue. After moving them, place the troublesome Ace on Goal 2. And so on. Victory is guaranteed except for that troublesome Ace.

I couldn't claim the game, yet I abandoned it to devote my attention to solving it with computer assistance. I concluded that with perfect play this tableau can be won well over 99.9% of the time, and with omniscient play 100% of the time. The remainder of this webpage summarizes this analysis.

Success chance

So what is the actual chance of winning the solitaire? If the Ace turns up either after both of the Nines in the Residue, or before at least one of the three Queens, then we can place the Ace to one of its desired Work locations and certainly win. In other words, of the 60 ways to permute {A, 9, 9, Q, Q, Q} only 5 ways (9QQQA9, Q9QQA9, QQ9QA9, QQQ9A9, QQQA99) present any difficulty at all. Therefore winning chance is at least 11/12.

But victory is even much likelier than that. For example, we also win easily if the next card from Residue is a Queen. We then redirect the card shown as 32 to be 34 and build Goal 4 up to 7, then place Ten on Goal 2. Goal 2 is no longer troublesome: the Three from the residue is now 32 and will go on Work #2, A2 will go on Work #3, and Q2 plays directly onto the Goal pile.

I wrote software to calculate the best strategy in a Four Kings position and used it to partially analyze this position. There are (12! / 3!2!2!) = 19,958,400 possible orderings of the Residue. Note that it's not good enough to look for winning strategies for those orderings one-by-one; we must make some decisions before we know what the actual ordering is. Despite a transposition cache which speeds the software up by orders of magnitude, it would take too long to completely analyze the position, so I made some stipulations. Worst start from the Residue seems to be Two. So I assumed Two followed by Six are the top of the Residue. There are only 151,200 possible orderings of the remaining ten cards in the Residue, and my program could almost handle that. (I say "almost" handle, because I made two more stipulations to speed the program up: that the Nines from Residue must be played on Work #1, and that the Queen in Work #1 must be played on Goal 1. These correct-seeming plays were stipulated so that the program wouldn't waste time considering alternatives. Later, I noticed that the Queen stipulation is sometimes suboptimal, so the win chances may be slightly higher than shown here.)

When those first two Residue cards are Two and Six (an undesireable case), the program wins 99.84% of the time, i.e. in all but 240 of the 151,200 cases. I tried some other starts; Nine-Two-Six wins 99.993%, its only losses coming when Jack is next.

Jack-Two wins 99.962% of the time, if you place the Jack on Work #1, instead of Work #2 as asssumed above. When that Jack is placed on Work #2, Jack-Two-Six and Jack-Two-Five (relatively bad-looking starts) each win 99.583%, most of their losses coming when Queen then follows; and Jack-Two-Queen wins only 98.72%. However, with the Jack placed on Work #1, Jack-Two-Six wins 99.795%, Jack-Two-Five wins 100% and Jack-Two-Queen wins 99.947%. I did check another case: Jack-Nine-Queen. With Jack and Nine both directed to Work #1, we win 100%, but only 99.285% if Jack goes to Work #2. After Jack-Nine we win 99.9934% if we place both on Work #1, the only troublesome third cards being Six and Two. (Jack-Nine-Queen wins only 99.285% if Jack goes to Work #2.)

That we can almost claim after Jack-Nine wouldn't have been clear to me, so I looked into it. A key point, as usual, is that the Ace may only need to go to Work #1 when both of the remaining Queens appear first. The Three appearing before the Ace also savews us; consider the Residue J 9 6 Q Q Q 3 A 9 2 5 5.

Since Two-Six and Jack-Two are among the worst cases, the chances in the original position with 12 Residual cards must be well over 99.9%.

Among the 240 losing orders that start 2-6, 144 losses are from 2-6-Q, 63 from 2-6-3, 31 from 2-6-J and 2 from 2-6-9. 2-6-A would guarantee victory of course, as would, less obviously 2-6-5.

I then stipulated an initial order of 2-6-Q. (As just mentioned, the software told us best play leads to a mere 144 losses with the Queen, but where should we play the Queen? Playing on either Goal 2 or Goal 3 gives 162 losses; we must instead temporize by playing the Queen to Work 3.) Among the 144 losses from these 45,360 orderings, 88 are from 2-6-Q-Q, 32 are from 2-6-Q-3, 24 are from 2-6-Q-J.

Let us stipulate 2-6-Q-J. This Jack is best played, on Work pile #1 -- the "Kings' pile" -- not where we expected to play that Jack at all; we move the Queen just seen up to Goal 4. From here, Queen next gives 18 losses, Three 4 losses, and Nine 2 losses. We'll suppose Queen, which we place on Goal 3. Our chance of success is now 98.57%; the position is:

From here, Queen gives 13 losses, Three 3 losses, Nine 2 losses. We will suppose Nine followed by Queen followed by Ace, yielding

From here the chance is still 5/6 -- we win unless the two Fives are at the bottom of the stock.

So, we've explored two failing orders in detail: 2-6-Q-J-Q-9-Q-A-9-3-5-5 and the same order with the 9-3 near end reversed. Yet we could have won with these if we were ominiscient. Play the 2-6 as before, then Q and 3 to Goal 4 and a Q to Goal 3. Play J on Work 2, Q-9 on Work 1, Q on Work 2, the 3-9 in either order to Work 1. In this case, the Ace and Three from Residue each plays differently than our default exectation.

Success chance, omnisciently

The above estimate assumes ordinary play, where you must make your decisions without knowing the order of remaining cards in the stock (Residue). What if you do know; what if you are allowed to inspect these cards? The software would take too long to confirm victory in all 19,958,400 cases, or even the 1,663,200 cases where the (QQQA99) ordering is troublesome. But there are only 25,200 cases where that ordering is troublesome and the two Fives are at the very end, which sure seems like our worst-case.

The software reports it can win 100% of those 25,200 most troublesome cases. Thus I assume it wins 100% from among all 19,958,400 cases, though I wouldn't stake my life on it.