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:
- The first row has 25-choose-5 possibilities, or 53,130.
- The second row has 20-choose-5 possibilities, or 15,504.
- The third row has 15-choose-5 possibilities, or 3,003.
- The fourth row has 10-choose-5 possibilities, or 252.
- 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:
Is the same as this layout:
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!
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.