November 7th 2004 Solitaire Theory
Yesterday afternoon, I trekked up to The Bison from my room in Vedder and ordered a grilled chicken sandwich for lunch. The sandwich was scheduled to take roughly ten minutes to prepare, so I went out into the dining area and sat down. Not content to merely sit and tick off the minutes on my watch, I whipped out my iPod and began playing the solitaire game that is included with it. That’s when a thought occurred to me: is every game of Solitaire winnable? I decided to do a little research to solve the problem.
In solitaire, 8.06581751709 × 1067 different hands can be dealt out. Naturally, it can be assumed that there are a few hands that are impossible to win. The website FreeCell Cooked? outlines at least one unwinnable hand that can be dealt in a game of solitaire. Unfortunately, there doesn’t seem to be much information about winnable and unwinnable hands in games of traditional solitaire—that is, games in which you actually take out a deck of cards. However, because few people seem to actually play “traditional” solitaire anymore, there is much theoretical and empirical evidence about computer solitaire—specifically, the version of FreeCell that ships with Windows computers.
The help screens for Windows Solitaire report that “it is believed (although not proven) that every game is winnable.” This, of course, is possibly true for computerized solitaire, as most software-based solitaire games (including the one that is shipped with Microsoft Windows) contain only 32,000 different hands (which raises the question: why not 32,768?). This is enough to prevent frequent repeats of deals but prevent unwinnable hands from being dealt. Research has shown that every game of Windows Solitaire is winnable—except for one. Game #11982 is impossible to win. This fact has been proven both by human players and computer players. It is believed that this is the only game of Windows Solitaire that cannot be won.
Unfortunately, this does not answer my question as to whether every game of traditional, physical-world solitaire is winnable. However, considering that at least 1 in 32,000 games is unwinnable, it is absolutely conceivable that there are several hands in traditional solitaire that are unwinnable.
Jul. 23, 2010 — Nearly six years after I published this post, I discovered another article that discusses the probability of an unplayable game of Klondike solitaire (the incarnation with which I am most familiar), instead of Windows’ FreeCell solitaire. The author of that article uses Monte Carlo simulation to estimate the percentage of unplayable games of Klondike (that is, games in which the player may make no moves). Since all unplayable games of Klondike are unwinnable, this number provides a lower bound for the frequency of unwinnable games. The author estimates that 1 out of 400 games of Klondike are unplayable, and suggests that anywhere from 1 in 40 to as many as 1 in 10 games of Klondike cannot be won.