display | more...

One of the popular games distributed with Windows 95 and later is FreeCell, an interesting variety of the Solitaire card game.

The help file for this game contains the following statement:

It is believed (although not proven) that every game is winnable.

This rather strange claim indicates that someone at Microsoft has a warped sense of humor.

For one, it starts with the unclear "it is believed" postulate. Believed by whom? Microsoft? The author of the help file? Someone who has played the game and kept winning?

The postulate is worded very carefully. Obviously, the every game is winnable statement is false. But if there is at least one person somewhere who believes it true, the postulate makes the full statement true, i.e., it is indeed believed that...

Secondly, there is the although not proven assertion. This is what indicates the whole thing is actually a joke. Only someone who knows that not every game is winnable can state that the belief has not been proven. After all, if every game were winnable, how would you know that no one has proven its truthfullness? What if someone did prove it and did not tell you.

If, on the other hand, you have the proof that not every game is winnable, then you can state with certainty that the belief has not been proven.

Finally, there is the claim that every game is winnable. This statement is false.

How can we prove that not every game is winnable? Simple: All we need to do is find a game that cannot be won.

In the case of FreeCell, one such game would have all kings and jacks at the bottom, and all twos and fours right above them. This game is not winnable, hence not every game is winnable. QED.

Can we generalize this and find a way of proving or disproving the winnability of any card game?

In the days of computers this is quite easy: Simply write a program that plays all possible variations of the game until you either come to a hand that cannot be won (not all games are winnable), ot you play and win them all (all games are winnable).

Naturally, this program will take a while to run (possibly even several days), but it is certainly relatively easy to determine for any kind of card game whether every game is winnable.

Surely, someone at Microsoft knows that, and surely, Microsoft has enough resources to use this brute force approach to prove than not every FreeCell game is winnable. Hence, the whole It is believed (although not proven) that every game is winnable statement had to be a joke.

P.S. I was not aware of game -1 pointed out by post86. This game is a variation of the unwinnable game I listed above, and is a clear proof that the "it is believed" statement was indeed a joke.

For the record game 11982 is the only game that is not winnable. Dave Ring's Internet FreeCell Project involving over a 100 researchers and using at least five different programs has spent 1,000s of manhours looking for a solution and have yet to find one. Also games -2, -1 can not be solved but they are Easter Eggs and not real games.
For more then you would ever want to know about Freecell check out:

To draw the two above WUs together, we need to look at their wording VERY carefully.

It is believed (although not proven) that every game is winnable.

For the record game 11982 is the only game that is not winnable.

Also games -2, -1 can not be solved but they are Easter Eggs and not real games.

The current "official" version of Freecell, included with Windows XP, lets you select one of 1,000,000 games (ignoring the -1 and -2 games). In essence, this must be some form of seed to the random number generator that "deals" the cards.

But on the other hand, there are far more than one million permutations for dealing the cards. My A-Level probability knowledge has lapsed in the past 12 years, but I would say the cards can be dealt in 52! ways. However, the 8 columns are all equivalent, and they can also be "sorted" in any one of 8! ways. This therefore says to me the cards can be dealt in 52! / 8! ways - this comes to 2.0004507730888858772733292871132 x 10^63 (approximately 2 followed by 63 zeros). If I've got this bit hopelessly wrong, please let me know! But even if I have, I guarantee there's a lot more than one million theoretical games.

Swap points out that "The 8 columns are not all equivalent. 4 of them have one more card than the other 4, though this hardly affects the order of magnitude of your estimate.". Of course, he's correct, the columns aren't all the same. But the difference it will make isn't that significant when working with numbers this large.

Maths interlude: n! means "n factorial" - or 1 × 2 × 3 × 4 × .... × n-1 × n. So 5! = 1 × 2 × 3 × 4 × 5 = 120

So, Microsoft only let you play one million games, out of approximately two thousand trillion trillion trillion trillion trillion games. Now, it's quite possible that the way they have written their internal random deal system, all of those one million games should be winnable, and that the 11982 game is a mistake.

It's interesting to note that the version of Freecell supplied with Windows 2000 only supported 32,000 unique games. I believe (!) that in the Windows XP version, games 1 to 32,000 are the same as the Windows 2000 version, and that all these have been solved except for 11982. I don't believe that there has been a concerted effort to solve all games from 32,001 to 1,000,000 in total - correct me if I'm wrong - so there may be other unwinnable games. Addendum: According to http://solitairelaboratory.com/fcfaq.html, there are 8 unwinnable games out of the one million total - 11982, 146692, 186216, 455889, 495505, 512118, 517776, 781948.

So, this means that we can validate the statement "It is believed (although not proven) that every game is winnable". For the Windows 2000 version, Microsoft fixed the dealing code to ensure that all games are winnable, and they simply made a mistake with game 11982.

Regarding "Also games -2, -1 can not be solved but they are Easter Eggs and not real games.". This depends on how we define a "real game". If we look at Freecell as simply a card game, then the games they deal are just as real as any other. They would be two of the 2x10^63 games calculated above, and could theoretically be dealt with a normal set of cards in real play.

On the other hand, if we accept that Microsoft fixed the dealing code to ensure that these sort of games can't be dealt, then it's fair to call them Easter Eggs. If we look at every possible permutation for dealing the cards, apart from the one million that are officially dealt, I'm sure there are plenty of other unwinnable games, and Microsoft put these two in for a laugh.

So, on the basis of this, we can say that "For the record game 11982 is the only game that is not winnable" is a valid statement, because it's the only game in the "official games" that isn't winnable. That said, stupot points out that it probably hasn't actually been proven that it's unwinnable, just demonstrated that it's unlikely to be winnable.

swap (who's a member of e^2) added some more comments about my calculations.

Hm. Something is still funny about the counting. Consider the simpler case of 6 cards and two pairs of columns, one pair with two cards each and another pair with one card each. According to your count, this is 6!/(2!×2!) = 180. On the other hand, the hand dealt is determined by two cards in single columns (that's 6 choose 2 = 15 ways) times the possible arrangements of the other four cards, which can be found by the two cards you can pick to go on top times two, because the bottom two cards can either be "straight" or "reversed. That's... Oh, 180 again. Never mind. Counting is hard. :P

'nuff said!

Two more opinions on the total number of unique games.

Kalon says I think there's another problem in your calculation, which comes down to the way MS implement their dealing. There are 8 columns, but this means there are 8! ways of dealing EXACTLY the same combinations of cards. eg: deal a game, then swap columns 1 and 2. This reduces the number of EFFECTIVE games.

cereed says The number of distinct games is 52!/(4! * 4!), which is ~ 1.4003 times 10 to the 65 power, and exactly 70 times larger than your estimate. So actually this does change the order of magnitude, if order of magntude means power of 10. This makes your conclusion that there are far more than 1,000,000 games even truer.

Dawggy says heres a hint hehe every game is winnable in freecell... when you get to the point you can't win, hold control + shift+f10, click abort and then simply click and move any card and bang you win :). Perhaps. That's what we call cheating!!!

Log in or register to write something here or to contact authors.