Jump to content

Microsoft FreeCell

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 137.205.74.30 (talk) at 15:06, 3 October 2008 (→‎Unsolvable combinations). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

FreeCell
File:FreeCell Vista.png
FreeCell in Windows Vista
Developer(s)Oberon Games (Windows Vista version)
Microsoft (older versions)
Publisher(s)Microsoft
Platform(s)Microsoft Windows
ReleaseFebruary 4, 2008
Genre(s)FreeCell
Mode(s)Single-player

FreeCell is a card game that is included in Microsoft Windows. It is a version of FreeCell.

History

File:FreeCell XP.png
FreeCell in Windows XP

The game gained worldwide popularity thanks to Jim Horne, who learned the game from the PLATO system and implemented a version of the game with color graphics for Windows. It was first included with Win32s as a test program, then in the Microsoft Entertainment Pack Volume 2 and the later Best Of Microsoft Entertainment Pack. However, FreeCell remained relatively obscure until it was made a part of Windows 95 and has been included with every version of Windows since[1].

Today, there are many other FreeCell implementations for every modern system, some of them as part of solitaire suites. However, it is estimated that as of 2003, the Microsoft version remains the most popular, despite the fact that it is very limited in player assistance features, such as retraction of moves. With the introduction of Windows Vista, the FreeCell implementation contains basic hints and unlimited move retraction. However, features such as the option to restart the game and the flashing screen to warn the player of one move remaining have been removed.

Solving

There are 52! (!=factorial), or approximately 8.00×1067, unique deals. But some games are effectively identical to others because suits assigned to cards are arbitrary or columns can be swapped. After taking these factors into account, there are approximately 1.75×1064 games.[2]

The original Microsoft FreeCell package includes 32,000 games, generated by a 15-bit random number seed. These games are known as the "Microsoft 32,000". Later versions of Microsoft FreeCell include more games, of which the original 32,000 are a subset. All hands in the Microsoft 32,000 have been beaten except for Game #11982.[1]. Many humans and several FreeCell solving programs have been unable to find a solution; but without a mathematical proof, it (and the other unsolved games) can only be hypothesized to be unsolvable.

The original Help file remains through modern Microsoft versions: "It is believed (although not proven) that every game is winnable." This was known at the time to be untrue in its strictest sense. Games numbered -1 and -2 were included as a kind of easter egg to demonstrate that there were some possible card combinations that clearly could not be won. Nevertheless it started a flurry of interest in the question of whether all of the Microsoft 32,000 could be beaten. Good players could win most of their played games, but there wasn’t proof either way.

In later implementations of FreeCell in Microsoft Windows, there are at least 1,000,000 games.

One way to "win" at any Microsoft FreeCell game (prior to Windows Vista) was added as a way to help the original software testers; one must push the following key combination of Ctrl-Shift-F10 at any time during the game. When the dialog box appears on screen click 'Abort' to win, 'Retry' to lose, or 'Ignore' to cancel and continue playing the game as originally intended. Double-click any card for the results. However, this does not actually provide a correct solution to the game. Doing this combination on the unsolvable games however shows that there are decks that are not topped with Kings but instead with other cards, including Aces.

Another way is to open 'Select Game' and type -3 or -4 in the Select Game dialog box. When the game loads, simply drag an ace to the suit home pile, and the other cards will automatically follow onto the suit home pile, winning the game (Windows Vista only).

The Internet FreeCell Project

When Microsoft FreeCell became very popular during the 1990s it was not clear which of the 32,000 deals in the program were solvable. To clarify the situation, Dave Ring started The Internet FreeCell Project, took on the problem to try to solve all the deals using human solvers. Ring assigned 100 consecutive games chunks across volunteering human solvers and collected the games that they reported to be unsolvable, and assigned them to other people. This project used the power of multiprocessing, where the processors were human brains, to quickly converge on the answer. The project was finished in October 1995, and only one game defied every human player's attempt: #11,982. Although this deal has defied every attempt to solve it, even by several exhaustive-search software solvers, no definitive proof has yet been offered that it is, in fact, unsolvable.

Unsolvable combinations

Out of the Microsoft Windows games, there are believed to be 8 which are unsolvable. They are games No. 11,982, No. 146,692, No. 186,216, No. 455,889, No. 495,505, No. 512,118, No. 517,776, and No. 781,948. This conclusion was arrived at by the consensus of several authors of FreeCell solvers. The solvers of both Danny A. Jones and Gary D. Campbell have been run through the first million FreeCell games and have found solutions to all but these eight. Several other solvers have also failed to produce solutions to these games.[3]

In general, there are a huge number of unsolvable deals. Consider the following unsolvable deal (the aces and queens are in the first (covered) row):

A A A A  Q  Q  Q  Q
3 3 3 3 10 10 10 10
5 5 5 5  8  8  8  8
7 7 7 7  6  6  6  6
9 9 9 9  4  4  4  4
J J J J  2  2  2  2
K K K K

Each set of four cards have 24 permutations, so there are a total of 2413 total number of such deals. This equals 2.413 times 1013. 2.413 = 87,649, or roughly 9 x 104. So the total number of these unsolvable deals is roughly 9 X 1017. Noting further that the rows of aces, threes, and fives can be permutated, and so can the tens and queens, with the deal remaining unsolvable, there are 12 x the previous number, giving the rough result of 1019 (10 to the power of 19) possible unsolvable deals of this type. (Of course, this is a small number compared to the total number of possible deals, which is roughly 10 to the 68th power.) Game No. -3 is a permutation of this.

References

  1. ^ a b Kaye, Ellen (2002-10-17). "One Down, 31,999 to Go: Surrendering to a Solitary Obsession". New York Times.
  2. ^ "FreeCell FAQ and links". Retrieved 2008-08-27.
  3. ^ "FreeCell FAQ and links". Retrieved 2007-10-02.