Poker Solitaire II – No (Quick) Program for Winning

This entry was originally stored in my personal blog engine, but has been imported into WordPress.

As discussed in my last entry, it’s possible to deal an unwinnable game of Poker Solitaire. I need to keep this from happening.

My initial response was to add some code that would, at the start of a game, examine the 25-card deal, and determine if it was winnable. The idea was to shift the cards into every possible layout, then check to see if that layout held 5 pat poker hands. If a winning layout isn’t found, the deal isn’t winnable, and it’s time to deal again.

Luckily, before I started coding that, I actually sat down and tried to figure out how long such a program would take. The answer: way too long.

After breaking out my old discrete mathematics textbook, I came up with this initial approach. This approach is wrong. However, it’s easier to explain the final solution if I show this first.

Whenever you form a layout with the 25 cards dealt, you form them into 5 rows of 5 cards each. There are 25! different ways to lay the cards down (a number so large I’m not going to type it out). However, since the order of the cards in the rows doesn’t matter, you can view it as a set and use this math to figure out all the possible combinations:

  1. The first row has 25-choose-5 possibilities, or 53,130.
  2. The second row has 20-choose-5 possibilities, or 15,504.
  3. The third row has 15-choose-5 possibilities, or 3,003.
  4. The fourth row has 10-choose-5 possibilities, or 252.
  5. The fifth row has 5-choose-5 possibilities, or 1.

Multiply all these together, and you get 623,360,743,125,120 (623 trillion) possible layouts!

Here’s my mistake. Someone checked my math and pointed out that the true number of possibilities is smaller than this. It fails to account for the fact that the order of the rows doesn’t matter. For example, the following layout:

2H 2D 2S KH KD
3H 3C 3S QD 7C
4H 4C 4S AD 5C
8S 9S 10S 7S AS
8H 9H 10H 8H 5H

Is the same as this layout:

3H 3C 3S QD 7C
2H 2D 2S KH KD
4H 4C 4S AD 5C
8S 9S 10S 7S AS
8H 9H 10H 8H 5H

In mathematical terms, you could call each possible layout a set of sets. When I initially looked at the problem, I realized that the cards in each row constituted a set. I forgot that the collection of rows itself was also a set.

At this point, I reached the limits of my education in combinatorics. I had to Google this problem until I found a solution using something called Benjamin Dickman’s formula. Let the problem be: from 25 cards, I’m dividing them into n groups of k cards each.

Plug the numbers into that formula, and you get a much nicer number: 5,194,672,859,376. Much smaller than my original estimate!

Unfortunately, looking through all these combinations would still take way too long for my purposes. Imagine pulling this game up on your cell phone, then waiting for the code (in JavaScript) to iterate through 5 trillion possible layouts!

This approach is not viable.

An aside: I chose Poker Solitaire for my first app game since it seemed simple and was easy to code. It no longer seems simple.

The calculations were done on Wolfram Alpha.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s