FreeCell
Encyclopedia
FreeCell is a solitaire
-based card game
played with a 52-card standard deck. It is fundamentally different from most solitaire games in that nearly all deals can be solved. Although software implementations vary, most versions label the hands with a number (derived from the random number seed used to generate the hand).
A version of FreeCell
was created by Microsoft for release with the Windows operating system.
Building during play:
Moves:
Victory:
For games with the standard layout (four open cells and eight cascades) most games are easily solved.
. In the June 1968 edition of Scientific American
, Martin Gardner
described in his "Mathematical Games" column a game by C. L. Baker that is similar to FreeCell, except that cards on the tableau are built by suit rather than by alternate colors. Gardner wrote "The game was taught to Baker by his father, who in turn learned it from an Englishman during the 1920's". This variant is now called Baker's Game
. FreeCell's origins may date back even further to 1945 and a Scandinavian game called Napoleon in St. Helena (not the game Napoleon at St. Helena, also known as Forty Thieves).
Paul Alfille changed Baker's Game by making cards build according to alternate colors, thus creating FreeCell. He implemented the first computerised version of it in the TUTOR programming language for the PLATO educational computer system in 1978. Alfille was able to display easily recognizable graphical images of playing cards on the monochrome display on the PLATO systems.
This original FreeCell environment allowed games with 4–10 columns and 1–10 cells in addition to the standard game. For each variant, the program stored a ranked list of the players with the longest winning streaks. There was also a tournament system that allowed people to compete to win difficult hand-picked deals. Paul Alfille describes this early FreeCell environment in more detail in an interview from 2000.
; it is unlikely that any algorithm more efficient than a brute-force search exists that can find solutions for arbitrary generalized FreeCell configurations.
There are 52! (i.e., 52 factorial
), or approximately 8, unique deals. However, 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 unique games.
Another known solver is Patsolve by Tom Holroyd. Patsolve uses atomic moves, and since version 3.0 has incorporated a weighting function based on the results of a genetic algorithm
that make it much faster.
Shlomi Fish started his own solver in 2000, written in C
and distributed with source under the public domain
(later relicensed under the MIT License
). This solver was simply dubbed Freecell Solver.
Gary Campbell wrote his FCELL solver for DOS
in 8086
assembly language
. This solver is 12 kilobytes, and is quite fast. FCELL was incorporated into the Faslo FreeCell AutoPlayer in 2007.
Some of these solvers and others have been incorporated into larger FreeCell or Solitaire programs. FreeCell Pro, the enhanced Windows-based Solitaire implementation by Adrian Ettlinger and Wilson Callan (formerly freeware
, later licensed under GPL
), first integrated Don Woods' solver and later on used Fish's Freecell Solver and Holroyd's Patsolve. PySolFC
has integrated Freecell Solver, while KDE
's KPatience
solitaire suite had initially integrated Freecell Solver as well, but later switched to a heavily modified version of Patsolve.
version of FreeCell, there are 8 deals that were shown to be unsolvable. Currently, no computer simulation has been able to solve #11982 while using only four free spaces.
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 and took on the challenge of trying 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 crowdsourcing 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. This deal has also defied every attempt to solve it by several exhaustive-search software solvers, and is therefore assumed to be impossible.
11,982 is inherently difficult due to the large number of aces and other small cards high in the stack, as well as the high cards being relatively evenly distributed among the stacks, requiring one to use many of the cells to get to any useful cards.
Out of the current Microsoft Windows games, there are eight that are unsolvable: the games numbered 11,982; 146,692; 186,216; 455,889; 495,505; 512,118; 517,776 and 781,948. Exhaustive search has shown that 5 free cells (rather than the standard four) are required for these games. Adrian Ettlinger, using Don Woods' solver, has used the same random hand generator as Microsoft Windows FreeCell to explore a further 10 million games. Of the 130 unsolvable games in the first 10 million, all of them require 5 free cells. Ryan L. Miller, with the help of others explored 100 million games, with a total of 1282 being unsolvable. This gives FreeCell a win rate of about 99.998718%.
In the earliest versions, 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. Following that, the cards are arranged in order of value, such as King, Queen, Jack, 10, 9 and 8 in the first four piles, and the remaining numbers in the other.
In versions before Windows Vista
, if the user pushes the combination of Ctrl+Shift+F10 at any time during the game, the user will be presented with a tool used by the developers during testing.
In the Windows Vista and Windows 7 versions, if the user hits 'Select Game' and types -3 or -4 in the dialog box, then, when the game loads, drags an ace to the suit home pile, the other cards will automatically follow onto the suit home pile, winning the game.
Patience (game)
Patience is a genre of tabletop games, consisting of card games that can be played by a single player. Patience games can also be played in a multiplayer fashion....
-based card game
Card game
A card game is any game using playing cards as the primary device with which the game is played, be they traditional or game-specific. Countless card games exist, including families of related games...
played with a 52-card standard deck. It is fundamentally different from most solitaire games in that nearly all deals can be solved. Although software implementations vary, most versions label the hands with a number (derived from the random number seed used to generate the hand).
A version of FreeCell
FreeCell (Windows)
FreeCell, as included in Microsoft Windows, is a computer implementation of the card game FreeCell.-History:The first computer version of the game is believed to have been created by Paul Alfille in 1978 for the PLATO system. Microsoft developer Jim Horne, who learned the game from the PLATO...
was created by Microsoft for release with the Windows operating system.
Rules
Construction and layout:- One standard 52-card deck is used.
- There are four open cells and four open foundations. Some alternate rules use between one to ten cells.
- Cards are dealt into eight cascades, four of which comprise seven cards and four of which comprise six. Some alternate rules will use between four to ten cascades.
Building during play:
- The top card of each cascade begins a tableau.
- Tableaux must be built down by alternating colors.
- Foundations are built up by suit.
Moves:
- Any cell card or top card of any cascade may be moved to build on a tableau, or moved to an empty cell, an empty cascade, or its foundation.
- Complete or partial tableaus may be moved to build on existing tableaus, or moved to empty cascades, by recursively placing and removing cards through intermediate locations. While computer implementations often show this motion, players using physical decks typically move the tableau at once.
Victory:
- The game is won after all cards are moved to their foundation piles.
For games with the standard layout (four open cells and eight cascades) most games are easily solved.
History
One of the oldest ancestors of FreeCell is Eight OffEight Off
Eight Off is a form of Patience, named after its employment of eight cells, played with one deck of playing cards. The object of the game is to move all the cards into the foundations.-Rules:...
. In the June 1968 edition of Scientific American
Scientific American
Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...
, Martin Gardner
Martin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...
described in his "Mathematical Games" column a game by C. L. Baker that is similar to FreeCell, except that cards on the tableau are built by suit rather than by alternate colors. Gardner wrote "The game was taught to Baker by his father, who in turn learned it from an Englishman during the 1920's". This variant is now called Baker's Game
Baker's Game
Baker's Game is a Patience game similar to FreeCell which differs in the fact that sequences are built by suit, instead of by alternate color.- History :...
. FreeCell's origins may date back even further to 1945 and a Scandinavian game called Napoleon in St. Helena (not the game Napoleon at St. Helena, also known as Forty Thieves).
Paul Alfille changed Baker's Game by making cards build according to alternate colors, thus creating FreeCell. He implemented the first computerised version of it in the TUTOR programming language for the PLATO educational computer system in 1978. Alfille was able to display easily recognizable graphical images of playing cards on the monochrome display on the PLATO systems.
This original FreeCell environment allowed games with 4–10 columns and 1–10 cells in addition to the standard game. For each variant, the program stored a ranked list of the players with the longest winning streaks. There was also a tournament system that allowed people to compete to win difficult hand-picked deals. Paul Alfille describes this early FreeCell environment in more detail in an interview from 2000.
Complexity
The FreeCell game has a constant number of cards. This implies that in constant time, a person or computer could list all of the possible moves from a given start configuration and discover a winning set of moves or, assuming the game cannot be solved, the lack thereof. To perform an interesting complexity analysis one must construct a generalized version of the FreeCell game with cards. This generalized version of the game is NP-completeNP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
; it is unlikely that any algorithm more efficient than a brute-force search exists that can find solutions for arbitrary generalized FreeCell configurations.
There are 52! (i.e., 52 factorial
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
), or approximately 8, unique deals. However, some games are effectively identical
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
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 unique games.
Solvers
One of the passions of several FreeCell enthusiasts was to construct computer programs that could automatically solve FreeCell. Don Woods wrote a solver for FreeCell and several similar games as early as 1997.Another known solver is Patsolve by Tom Holroyd. Patsolve uses atomic moves, and since version 3.0 has incorporated a weighting function based on the results of a genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
that make it much faster.
Shlomi Fish started his own solver in 2000, written in C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and distributed with source under the public domain
Public domain
Works are in the public domain if the intellectual property rights have expired, if the intellectual property rights are forfeited, or if they are not covered by intellectual property rights at all...
(later relicensed under the MIT License
MIT License
The MIT License is a free software license originating at the Massachusetts Institute of Technology . It is a permissive license, meaning that it permits reuse within proprietary software provided all copies of the licensed software include a copy of the MIT License terms...
). This solver was simply dubbed Freecell Solver.
Gary Campbell wrote his FCELL solver for DOS
DOS
DOS, short for "Disk Operating System", is an acronym for several closely related operating systems that dominated the IBM PC compatible market between 1981 and 1995, or until about 2000 if one includes the partially DOS-based Microsoft Windows versions 95, 98, and Millennium Edition.Related...
in 8086
Intel 8086
The 8086 is a 16-bit microprocessor chip designed by Intel between early 1976 and mid-1978, when it was released. The 8086 gave rise to the x86 architecture of Intel's future processors...
assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
. This solver is 12 kilobytes, and is quite fast. FCELL was incorporated into the Faslo FreeCell AutoPlayer in 2007.
Some of these solvers and others have been incorporated into larger FreeCell or Solitaire programs. FreeCell Pro, the enhanced Windows-based Solitaire implementation by Adrian Ettlinger and Wilson Callan (formerly freeware
Freeware
Freeware is computer software that is available for use at no cost or for an optional fee, but usually with one or more restricted usage rights. Freeware is in contrast to commercial software, which is typically sold for profit, but might be distributed for a business or commercial purpose in the...
, later licensed under GPL
GNU General Public License
The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....
), first integrated Don Woods' solver and later on used Fish's Freecell Solver and Holroyd's Patsolve. PySolFC
PySol
PySol is an open source and platform independent computer game that incorporates around 1,000 solitaire games, including card games and other types of single-player games.. It is written in the Python programming language. PySol was originated by Markus F.X.J...
has integrated Freecell Solver, while KDE
KDE
KDE is an international free software community producing an integrated set of cross-platform applications designed to run on Linux, FreeBSD, Microsoft Windows, Solaris and Mac OS X systems...
's KPatience
Kdegames
The kdegames package contains games written for the KDE. kdegames provides games in a number of genres including card games, arcade games and board games.- Arcade :*KBlocks - A Tetris clone*KBounce - A JezzBall clone for KDE...
solitaire suite had initially integrated Freecell Solver as well, but later switched to a heavily modified version of Patsolve.
Impossible games
It is believed that game #11982 is the only unbeatable game out of the original 32,000 Windows FreeCell games. In the new one million deals in the Windows XPWindows XP
Windows XP is an operating system produced by Microsoft for use on personal computers, including home and business desktops, laptops and media centers. First released to computer manufacturers on August 24, 2001, it is the second most popular version of Windows, based on installed user base...
version of FreeCell, there are 8 deals that were shown to be unsolvable. Currently, no computer simulation has been able to solve #11982 while using only four free spaces.
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 and took on the challenge of trying 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 crowdsourcing 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. This deal has also defied every attempt to solve it by several exhaustive-search software solvers, and is therefore assumed to be impossible.
11,982 is inherently difficult due to the large number of aces and other small cards high in the stack, as well as the high cards being relatively evenly distributed among the stacks, requiring one to use many of the cells to get to any useful cards.
Out of the current Microsoft Windows games, there are eight that are unsolvable: the games numbered 11,982; 146,692; 186,216; 455,889; 495,505; 512,118; 517,776 and 781,948. Exhaustive search has shown that 5 free cells (rather than the standard four) are required for these games. Adrian Ettlinger, using Don Woods' solver, has used the same random hand generator as Microsoft Windows FreeCell to explore a further 10 million games. Of the 130 unsolvable games in the first 10 million, all of them require 5 free cells. Ryan L. Miller, with the help of others explored 100 million games, with a total of 1282 being unsolvable. This gives FreeCell a win rate of about 99.998718%.
Easter eggs
In versions before Windows Vista
Windows Vista
Windows Vista is an operating system released in several variations developed by Microsoft for use on personal computers, including home and business desktops, laptops, tablet PCs, and media center PCs...
, if the user pushes the combination of Ctrl+Shift+F10 at any time during the game, the user will be presented with a tool used by the developers during testing.
In the Windows Vista and Windows 7 versions, if the user hits 'Select Game' and types -3 or -4 in the dialog box, then, when the game loads, drags an ace to the suit home pile, the other cards will automatically follow onto the suit home pile, winning the game.