freecell math

The only game that my father plays on his Mac is freecell. He plays the version available in Rick Holzgrafe’s Solitaire Till Dawn X. This is a pretty nice version of the game (although it lacks game numbers and the ability to automate supermoves), and my father occasionally saves deals that stump him.

Well, yesterday I tried one of them, and after a while, in frustration, decided to see if it was solvable by running it through the automated freecell solver.

Sure enough, it was winnable, although in order to win, the solution took us through two situations where Solitaire Till Dawn claimed that there were no more moves. It lied!

In any case, I’ve often idly wondered what the mathematical properties of freecell were. It is somewhat obvious that not all deals are winnable because one can construct a deal that cannot be won. I’ve wondered if anyone ever modeled freecell to the point where they could predict the winnability of a given deal, or, more likely, prove that certain deals were not winnable. This was predicated on my amazement at the ability for freecell applications to never (in my experience) give out an unwinnable freecell game.

Well, I haven’t seen that there is a solid mathematical model for freecell (although, clearly there are algorithms for solving freecell), but the game has been subject to a lot of empirical observation. In fact, it appears that freecell implementations have to do no special work, because it is estimated that 99.999% (or 1 loss in 79,000 deals)of freecell deals are winnable. Of course, reading the freecell FAQ made me realize that I’m a freecell amateur. A neophyte, even.