Which deals of the solitaire game FreeCell are impossible to win?
competition/games/freecell New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Which deals of the solitaire game FreeCell are impossible to win? [ Editor: problem statement reconstructed from the postings. ]
Show solution
[ Editor: from posting number 27 (February 2002) of the FreeCell mailing
list run by Michael Keller. The list's FAQ was at
<http://home.earthlink.net/~fomalhaut/fcfaq.html>. ]
The newest version of Pretty Good Solitaire (www.goodsol.com) increases
the number of available variants of solitaire to 500, and also now uses
the same deal numbers as FreeCell Pro and MS Windows XP FreeCell for the
first million deals.
Dr. Tom Holroyd's discovery of a deal impossible with five freecells in
the second ten million deals of FreeCell Pro has rekindled our interest
in searching for deals impossible in the standard four-freecell game of
FreeCell. We have run 10 million more deals through the Woods solver
used in FCPro, using Holroyd's solver to verify the results. The block
of deals from 20-30 million has 107 verified impossible deals, with four
more (24795893, 25946430, 28236172, and 28260761) having produced no
definite answer -- attempts to solve these four by hand have also proved
fruitless so far. We have no explanation for why there are
significantly fewer impossibles (between 107 and 111) in this block of
10 million than the first two blocks (126 and 137). All ten million are
solvable with five freecells, so we can't even guess yet at how rare
5-impossibles are.
Impossible deals in FreeCell Pro (20-30 million):
20001314, 20071907, 20189056, 20320311, 20385961, 20406513,
20433342, 20518564, 20708407, 20793961, 20822616, 21142208,
21129951, 21222789, 21537381, 21805363, 21929423, 21942519,
22114810, 22163461, 22200703, 22201670, 22269191, 22422348,
22558888, 22696127, 22871243, 22916800, 22923064, 22934678,
23154641, 23475247, 23699849, 23759201, 23796844, 23859543,
23892853, 23904084, 24032064, 24121426, 24150534, 24155427,
24359967, 24389334, 24423283, 24485481, 24504750, 24555726,
24575738, 24626162, 24704507, 24878221, 25004745, 25020803,
25201614, 25319257, 25415739, 25775645, 25896720, 25915651,
25980259, 26209120, 26227144, 26231145, 26461140, 26752865,
26823491, 26960143, 26965125, 27005706, 27083753, 27304749,
27306844, 27376127, 27437151, 27616230, 27824790, 28205100,
28269290, 28273176, 28321512, 28334327, 28435672, 28504123,
28595526, 28620288, 28656330, 28730691, 28737488, 28827039,
28857746, 28874355, 28935939, 29007113, 29070099, 29159197,
29182185, 29185136, 29187150, 29273230, 29289973, 29298230,
29484565, 29577046, 29719033, 29726206, 29939055
NetCELL (www.freecell.com) has a fantastic new feature displaying the
statistics for every one of the 32,000 deals (in the standard 8x4 game
or any variant). This shows how many times each deal has been played
and won (by all of the NetCELL players combined), and can be sorted by
deal number or by win percentage. All of the 8x4 deals up through
level 10 have been played, and only two have been found impossible:
27271-10 and 10537-6. This is a good way to find extremely challenging,
but winnable deals: for example, 7913-10 and 6795-9 have been won less
than 1% of the time, and 17816-5 slightly more than 1%.
-- Michael Keller <fomalhaut@earthlink.net>, Solitaire Laboratory
<http://home.earthlink.net/~fomalhaut/solitlab.html>
[ Editor: from posting number 21 (March 2000) of the FreeCell mailing
list run by Michael Keller; the list's FAQ was then at
http://members.aol.com/wgreview/fcfaq.html. The paragraph on the
statistics of cards played at the start appears twice in the posting,
in two versions; both are kept. ]
The current release of FreeCell Pro, version 6.2, has support for up to
seven freecells, and allows statistics (and/or related messages) to be
turned off at the user's option. Thanks to Mike Moak and Terry Thomas,
we know what causes the "Card appears twice" bug which has plagued the
solver, and Adrian Ettlinger is working on a new version to fix that
problem.
The deal Adrian constructed which we gave in the previous news posting
is solvable with seven freecells. Adrian now challenges anyone to
construct a deal which cannot be solved with seven freecells, or to
prove that this is impossible.
Based on independent work by Adrian Ettlinger and Bill Raymond, a
number of deals previously analyzed as impossible by FCPro have now
been discovered to be solvable: 717025, 1940838, 3113705, 3917750,
5862173, 6511428, 7139586, 8470523, 9902420, and 9773169. This lowers
the number of impossible deals in the first ten million to 126.
Adrian Ettlinger ran all of the 126 deals from the first ten million
which are impossible with four freecells through the FreeCell Pro
solver, using five freecells. All of them are solvable. Are there any
deals in the more than four billion available in FreeCell Pro which are
impossible with five freecells?
Bill Raymond, who encountered a random deal (27245) in which eight
cards go to the homecells at the start, wrote a program to search for
FreeCell deals in which large numbers of cards go to the homecells on
the first play (using Microsoft's autoplay rule). His search of the
32,000 Microsoft deals turned up no other eight-card deals, and only
one other seven-card deal (22265) in addition to the deal (8695)
previously found by Mike Dykstra. All three of these are one-freecell
deals.
Bill extended the search through some of the FreeCell Pro deals,
The first nine-card deal is 270618; this requires two freecells to
solve, but is fairly easy.
The first 10-card deal is 2710330, a hard one-freecell deal.
The first 11-card deal is 3060287, a very hard zero-freecell deal.
If you're looking for an extremely easy deal, try 22350203, an 11-card
deal which is very easy even with zero freecells (my solution is only
35 moves).
The first 12-card deal is 12172106, a medium-hard one-freecell deal.
The first 13-card deal is 17332733, another hard zero-freecell deal.
The first 14-card deal is 181627041, an easy one-freecell deal.
The first 15-card deal is 143973501, a hard zero-freecell deal.
Some other curious statistics: slightly over half (50.15%) of all deals
play no cards initially to the homecells; another 30 percent (30.38%)
play one card; another 14 percent (13.56%) play two; another four
percent (4.38%) play three. Slightly over one percent play four or
more; less than one in a million play ten or more. It seems likely
that the odds against all 52 cards playing automatically in a random
deal are astronomically high; even if five percent of random columns
are sufficently well-ordered, the odds are more than 25 billion to one
against a complete deal playing automatically.
The more complex autoplay rules used by NetCELL (described in the FAQ)
sometimes allow many more cards to be played initially. There are no
large increases in the 32,000 Microsoft deals (deal 27245 plays 10
cards, and 2217 and 22265 play 8 each). The most extreme case Bill
found is 1195233675, in which the simple Microsoft rule plays six cards
to the homecells, but the NetCELL rule plays twenty-three! This is a
zero-freecell deal, and might be the easiest in the entire
8-billion-plus FCPro deals. Another interesting deal found by Bill is
446806382, another zero-freecell deal, which plays only four cards
using the MS rule but 16 using the NetCELL rule.
Joe McCauley independently wrote a program to count how many cards were
autoplayed, and extended the search through the entire 8 billion-plus
FreeCell Pro deals. He also checked to see how many cards could be
played to the homecells if *every* possible homecell play was made (Joe
calls this AllPlay): three of the 32,000 Microsoft deals (4196, 5319,
and 27245) play 10 cards using AllPlay, with one other (27403) playing
9. Interestingly, 4196, 5319, and 27245 are all one-freecell deals,
but 5319 *cannot* be won with one freecell if you play all ten cards
immediately to the foundations! (Nine works, but the four of hearts is
needed.)
Using the Microsoft rule, there are five deals in which 16 cards play to
the homecells (2016704153, 3453036771, 4418013924, 5856288588, and
8110636965). The first deal to break 16 using NetCELL rules is
1000572852, which plays 17 cards (only 5 in MS) -- despite 17 cards
played and a whole column emptied, it cannot be solved with zero
freecells, though it's not hard with one. 4418013924 plays 19 using
the NetCELL or AllPlay rules. Using the NetCELL rules, two other deals
play 19 cards (2178166022 and 2587385892), well short of the deal
mentioned above which plays 23.
Using AllPlay, three other deals play 23 cards (2587385892, 4931624547,
and 7372172513) -- the last two play only four and six respectively
under both MS and NetCELL rules. But two deals play more than 23 using
AllPlay: 8305804964 plays 25 (only 5 under MS and NC), including all of
the diamonds; 7841153263 plays 28, the only FCPro deal in which half
the deck can be played at the start. Except for 1000572852, all of the
hands mentioned in the last two paragraphs can be solved with zero
freecells.
Some other curious statistics: slightly over half (50.15%) of all deals
play no cards initially to the homecells (remarkably close to the
theoretical value 19393/38675 = 0.50144). Another 30 percent (30.38%)
play one card; another 14 percent (13.57%) play two (slightly *less*,
12.6%, with AllPlay). Slightly over one in a million play ten or more
using the MS rule (about four in a million in NetCELL and thirty-six in
a million using AllPlay). It seems likely that the odds against all 52
cards playing automatically in a random deal are astronomically high;
even if five percent of random columns are sufficently well-ordered,
the odds are more than 25 billion to one against a complete deal
playing automatically. Even with AllPlay rules, only 38 FCPro deals
play 20 or more cards to the homecells.
Curtis Cameron has written a new version (3.0) of his popular FreeCell
program for Hewlett-Packard 100LX and 200LX palmtop computers,
available from his web page at
<http://members.aol.com/FreeWhL44/lxgames.html>. The new version
includes an option to enter a Microsoft deal number (from 1 to 32000),
and to export deals in the same simple format used by FreeCell Pro.
The program also is able to save a solution to a file.
Curtis sent me the tableau of a deal (947293, using his original deal
numbering) which had been reported to him by Peter Prime as "probably
impossible". FreeCell Pro confirmed that this was in fact the case;
this is the first unsolvable random deal to be reported outside of the
Microsoft/FreeCell Pro system.
Another version of FreeCell which can generate the 32,000 Microsoft deal
numbers is PySol, a package written by Markus F.X.J. Oberhumer using
the Python development package for Linux. The package currently
(version 3.40) contains 163 games, including FreeCell, Forecell, and
the other close relatives of FC. Although it is written for the Linux
operating system, conversion packages are available for other
platforms, including Windows. I had no trouble getting it to run on my
Windows 98 system. The package is free (under the terms of the GNU
General Public License), and the program and other necessary packages
can be found at <http://pysol.tsx.org>.
A report of an unsolvable deal in NetCELL was sent to me, but the
report turned out to be incorrect. The deal in question is 17816 level
5, and it was mistakenly analyzed as impossible with FreeCell Pro (the
person testing it ran it with three freecells instead of four). I
downloaded a screenshot of the deal from NetCELL and typed it in to
verify the report, but FCPro indicated the deal was solvable. I
managed with great difficulty to find a solution by hand -- it is one
of the most difficult deals I have seen so far. If you have access to
a browser with Java, log into NetCELL at
<http://www.freecell.com/way/cool/cell/play.html> and try it out.
Sometime later, Denny Cronin set me another report of an impossible
(four freecell) NetCELL deal. This one turned out to be correct; the
deal is 27171 level 10.
David Reiss reported a version of FreeCell written by Ben Mickle for the
Texas Instruments TI-86 graphing calculator (a machine which supports
Z80 assembly language programming). A screenshot and other information
can be found at
<http://www.ticalc.org/archives/files/fileinfo/92/9230.html>; the
program is free and can be downloaded (with source code) at
<http://www.ticalc.org/pub/86/asm/games/freecell.zip>.
-- Michael Keller <Wgreview@aol.com>, March 2000
[ Editor: an earlier announcement and FAQ extract by Michael Keller,
mailed in March 1998 to a FreeCell mailing list. The addresses are as
given then. ]
Announcements:
The catalog of solutions to the standard FreeCell games, begun by Dave
Ring and later maintained by Wilson Callan, is now located at my WWW
site at: <http://members.aol.com/wgreview/freecell.html>. Some of the
links are not yet active, but will be soon. The original site at
<http://www.capecod.net/~wcallan/freecell.htm> is still available at
the moment, but may be removed in the future.
The current FAQ file is located at:
<http://members.aol.com/wgreview/fcfaq.txt>. At present the latter is
in plain text form; eventually I will convert it to HTML.
* How are the games (deals) numbered? Are those deals random or were
they selected in some way?
The way computers create "random" deals is by using a number as a
"seed" for a random number generator. The Microsoft version of
FreeCell uses a number with a range of 1-32000 as its seed; the New
Game (F2) function selects one of these using, I believe, the "seconds
of day" system function. You can also type in any number you choose
yourself. The deals are not "preset" in the sense of being
deliberately chosen; they are the result of the algorithm Jim Horne
used, and are as "random" as a computer can make them. The only way I
know to get more "random" deals is to shuffle and deal an actual deck
of cards.
* What is FCPro? What can it do that most other programs cannot?
FCPro is a Windows 95 version of FreeCell written by Wilson Callan
and Adrian Ettlinger. (Available free at the FreeCell site at
<http://members.aol.com/wgreview/fcpro.htm>.) FCPro was originally
written for the purpose of automatically recording solutions to
interesting deals as they are solved by the user. The first version
was a "tracking" program which ran while the user was playing the
standard Microsoft FreeCell. It read mouse clicks, interpreted them,
and correctly recorded solutions according to the standard FC notation
devised by Andrey Tsouladze.
In correspondence with Jim Horne, I asked about his algorithm for
generating random deals, and he sent me the full C code for the
dealing routine. There's nothing particularly tricky about it; a
clever programmer could probably work it out by trial and error. But
Jim kindly allowed us to incorporate the code into FCPro, and this
allowed us to recreate the entire set of 32,000 deals of the Microsoft
version (e.g. 11982 is unsolvable in FCPro too). Adrian later realized
he could create a larger range of deals using a different storage type
for the deal number, and extended the range of deal numbers to over 4
billion (and the first 32,000 are still the same as those in
Microsoft's). The New Game function in FCPro does not use the whole
range, but selects a deal at "random" from the first million. Having
Jim's dealing code and the FCPro solution-recording function allowed us
to generate (and later check) solutions to the standard deals. I used
FCPro to record and send to Wilson dozens of new solutions to difficult
or interesting deals.
The next big leap forward for FCPro occurred when Don Woods sent us
the C code for his automatic solving program. He had used this to
analyze one million random deals, and found that all but 14 were
solvable. Adrian incorporated the code into FCPro, and added a
function to allow a range of hands to be automatically processed. He
also added some sorting routines to rearrange the eight starting
columns according to various schemes; this frequently allowed the
program to quickly solve a hand which otherwise proved difficult. The
most recent advance in the program is to allow the user to select any
number of freecells from 0 to 4 -- this works with both the manual
play function and the automated solver.
* How often can I win?
Adrian Ettlinger, using Don Woods' solver with some extensions of
his own, has analyzed 3 million deals, starting with the standard
32,000 of the Microsoft version, and continuing on through deals
numbered up to 3 million (using the same random number scheme as
Microsoft FreeCell, thanks to Jim Horne). This analysis was carried
out with the FreeCell program FCPro, written by Ettlinger and Wilson
Callan. Of the 3 million deals, exactly 30 are unsolvable in the
standard game (a 99.999% win rate):
11982, 146692, 186216, 455889, 495505, 512118, 517776, 717025,
781948, 1155215, 1254900, 1387739, 1495908, 1573069, 1631319,
1633509, 1662054, 1940838, 2022676, 2070322, 2166989, 2167029,
2607073, 2681284, 2712622, 2843443, 2852003, 2855691, and 2923820.
[ Editor: the list has 29 numbers, not 30. The FreeCell entry above
reports that 717025 and 1940838 were later found to be solvable. ]
Most notably, we verified the result of the Ring project: all but
one deal (11982) [Editor: "11892" in the original; the deal is 11982
in the list above] of the 32,000 standard deals is solvable! No more
unsolvables turned up for more than 100,000 more deals.
A more difficult variant of FreeCell is to play with fewer than
four freecells. Even with three freecells, approximately 99-1/3% of
deals can be won (208 of the first 32,000 cannot be won with three
freecells; Ettlinger also ran another segment of some 67,000 deals with
a similar win rate).
Based on analysis of the first 32,000 deals, we can also give
tentative results for smaller numbers of freecells. With two
freecells, the win rate is about 78 or 79%, and with one freecell, the
win rate is about 19%. Wilson Callan had received several claims of
deals which could be won without using any freecells at all (even for
indirect moves), but we were unable to verify any of these reports (in
fact, the solver contradicted every such claim). But remarkably, it
turns out to be possible to win about one out of 500 deals with zero
freecells: 64 of the 32,000 standard deals are winnable this way. The
first dozen are: 164, 892, 1012, 1081, 1150, 1529, 2508, 2514, 3178,
3225, 3250, and 4929. My solution (found by hand) to 1150 is posted in
the solution catalog.
* Is it possible to get all 52 cards to the homecells at once?
Yes. While I was participating in Dave Ring's project, I noted
that some deals ended with 40 or more cards going to the homecells at
the end of the game (called a flourish, cascade, or sweep -- the latter
term coming from peg solitaire). The best I managed was 47 cards.
George W. Edman discovered a number of deals on which he could end
with a 50-card flourish, and submitted solutions to Wilson Callan's
solution catalog: 7329, 7851, 15824, 23600, and 26963, 31126 (game
found by Carol Philo), and 31637. Since the standard version of
FreeCell plays aces automatically to the homecells as soon as they are
available, these games depend on having two aces buried at the bottom
of the same column, and arranging the remaining cards into sequence
before uncovering the last two aces.
But a few weeks ago, Andy Gefen found the ultimate: a 52-card
flourish. After noticing that deal number 18492 had FOUR aces at the
bottom of column six, he realized that if he could get all of the other
cards in order without moving the seven of diamonds which covers the
aces, he could achieve the 52-card flourish! He was able to do so
after considerable effort, and his solution is now available in the
solution catalog at
<http://members.aol.com/wgreview/freecell.html>.
Thanks for questions and answers to: Wilson Callan, George W. Edman,
Adrian Ettlinger, Andy Gefen, Jim Horne, Brian Jaffe, Dave Ring, George
West, and Don Woods.
-- Michael Keller <Wgreview@aol.com>, March 1998
[ Editor: earlier FreeCell material, 1994-1998: a solution to deal
23017 and the notation discussion that followed, Dave Ring's Internet
FreeCell Project, two program announcements, and parts of Michael
Keller's FreeCell FAQ as mailed to Chris Cole and posted to
rec.puzzles. Addresses are as given then. ]
In article <JUHANIHE.94Oct15114751@waltari.helsinki.fi>,
juhanihe@waltari.helsinki.fi (Juhani Heino) writes:
> [other soln...]
Here's an explicit solution to FreeCell #23017 as someone asked...
Notations:
[1]
Card is indicated by number & suit, i.e.
2C = two of clubs, QD = queen of diamonds, etc.
[2]
A single card move is shown like:
2C -> 3H
which reads, "two of clubs played onto three of hearts"
[3]
Cards may also be played onto a FreeCell, i.e "fc", or onto an empty
column, i.e. "col", or may be played into discard piles, i.e. "remv".
Ex:
2C -> fc
2C -> col
2C -> remv
[4]
A group move is enclosed in square braces, naming the bounding cards,
i.e.
[QH ~ 9S] -> KC
reads, "Queen Hearts thru 9 spades played onto King Clubs"
[5]
If a move takes place automatically (to the discard piles) it is noted
in parentheses. i.e.
(2C,3C -> remv)
NOW, FINALLY, THE SOLUTION TO FREECELL #23017....
7H -> 8S
2C, 3D -> fc
10S -> JD
3D -> 4C
2C -> 3D
3S -> fc
[QC ~ 10S] -> KD
9H -> 10S
8C -> 9H
6S -> 7H
KS, QH -> fc
7D -> 8C
KS -> col
QH -> KS
KC -> fc
3S -> 4D
8H -> 9C
5S -> fc
9D -> fc
JC -> QD
2H -> 3S
9D -> 10C
[8S ~ 6S] -> 9D
3H -> fc, (AH, 2H -> remv)
3H -> remv
8D -> fc
6D -> fc
JS -> QH, (AD -> remv)
6D -> col
5S -> 6D
[4D ~ 3S] -> 5S
4S -> fc
10H -> JS, (AC, 2C -> remv)
[9C ~ 8H] -> 10H, (2D, 3D -> remv)
KC -> col
[QD ~ JC] -> KC, (3C, 4C -> remv)
10D -> JC
5C -> remv
QS -> fc
KH -> col
QS -> KH
JH -> QS
4H -> remv
7C -> 8H
[6D ~ 3S] -> 7C
[10C ~ 6S] -> JH
[KD ~ 7D] -> col
6C -> 7D
5D -> 6C
9S -> 10D
6H -> 7S
5H -> 6S, (ALL -> remv)
-- BrocS <brocs@aol.com>, October 1994
Dave Ring (of The Freecell Project) has come up with a simple, elegant
notation for Freecell. The 4 free cells are a, b, c, d. The Home area
is h. The columns are 1-8. To move from column 8 to column 5, the
notation is 85. Freecell b to column 3 is b3. Column 5 to home is 5h.
Forced moves are not shown. When asked if you want to move 1 card or a
column, default is a column. Moving a single card is 68(1). Moves are
shown 10 to a line, like this:
52 25 84 1a 14 1b 1c 13 18 81
81 a1 51 2a 25 c5 2c 2d 71 d2
etc.
> NOW, FINALLY, THE SOLUTION TO FREECELL #23017....
> 7H -> 8S
In the new notation, on my screen, this becomes 85.
> 2C, 3D -> fc
Here's where the problem lies. I think you are using the old version
of Freecell, not the new version used by the Freecell project. On my
layout for #23017, 2C is the 2nd from the top card in the 5th column.
3D is the 2nd from the bottom in the 1st column. Obviously, yours are
elsewhere. Bring up puzzle #11982. If the upper left card is the Ace
of Hearts, you have the newer version of Freecell.
-- <blask@gpx01.d39.lilly.com>
For the record, this notation was invented by Andrey Tsouladze.
-- Dave Ring <dwr2560@tam2000.tamu.edu>
***********************************************************************
The Internet FreeCell project.
Most people who have used ms-windows are familiar with FreeCell, one of
the 'game pack' games, that every windows system seems to have. It is
described as a logic puzzle in the form of a solitaire card game.
There are 32000 numbered deals. The online help claims:
"It is believed (although not proven) that every game is winnable."
There is some debate about the meaning of this, in particular does
'every game' mean just the 32000, or all possible games. It is known
that unwinnable deals are constructible. With this in mind, many
people have searched for unwinnable hands systematically from hand 1.
The purpose of the project is to organize the individual searchers to
cover different hands.
In addition to unwinnable deals, it is also useful to make a list of
difficult hands, so that advanced solvers can still enjoy the game
without getting bored.
If you would like to participate in this historic endeavor, just send
me an email (don't post!), and I will reply with a set of 100 (or more
or less if you want) hands for you to try at your own pace. When you
are finished (or get bored) you can send me a note, letting me know
which hands you solved, which you skipped, and which, if any, were
especially hard.
I am told the game is available by anonymous ftp at ftp.cit.cornell.edu
in /pub/windows/comm/win32s.zip .
If you have already done a study, please let me know so I don't have to
assign those hands.
*******************************************************************
Update:
1. We now have over 70 volunteers and over 27000 assigned hands. Over
fifteen thousand hands are now known to be solvable. 11982 remains the
only unsolved hand. Results have slowed down quite a bit and we need
to reassign many hands, so we need lots of new volunteers!
2. The hard hands which have been reported to me are: 1941, 11982,
25599, 454, 3973, 718, 16191, 8534, 5374, 2577, 20055, 2772, 5482, 617,
4257, 5548, 5557, 4946, 3801, 4368, 8323, 1689, 9538, 8820, 2350, 9617,
9700, 7107, 7160, 30801, 30108, 7600, 8005, 17524, 18992, 16575, 16576,
19633, 26421, 8678, 8652, 19763, 20715, 26576, 26694, 17277, 2670,
17764, 17768, 19861, 21278, 27188, 21051, 13015, 24457.
3. There are many versions floating around, but only a rare few have a
different set of hands. One of these versions dates back to before the
game was (presumably) bought by Microsoft. You have the right version
if the upper left card in the layout of 11982 is AH.
-- Dave Ring <dwr2560@tam2000.tamu.edu>, November 1994
[ Editor: items 1 and 2 of the update also appeared, word for word, as
"The Internet FreeCell Project Status Report (10/29/94)" in Ring's
reply of 31 October 1994 to the question "what happened to freecell
project?", which added: "We are somewhat more than half done." ]
There is a new Freeware that replaces Freecell from Microsoft:
It has an own homepage at:
http://huizen.dds.nl/~ren-hoek
or download directly:
ftp://ftp.info.isbiel.ch/udd/ftp/win95/uploads/xcell30.zip
ftp://ftp.cdrom.com/pub/win95/new/xcell30.zip
THE SOURCE of Xcell 1.0 is Free! and can be obtained by downloading the
Windows Eiffel Library Examples:
ftp://ftp.eiffel.com/pub/windows/wel/examples/wel_ex2.zip
Xcell has a lot of features more than Freecell:
o Saving / Restoring a game
o Hall of Fame
o Merging hall of fames (to share with friends :)
o Selecting a number of cards to play with
o Selecting a game number 1-65000
o Replay possibilities after finishing a game
o Undo / Redo in a game
o Card movement (drag and drop)
o TOTALLY FREE!
-- Ren Hoek <ren-hoek@dds.nl>, March 1996
NetCELL is a web-based version of the popular solitaire game Freecell.
Scores are kept and games are saved at a central server so you can see
how you rank against other folks on the net.
http://www.cd.com/netcell
Note: you must have Netscape 2.0 or better and be running a 32 bit OS
such as Win95/NT or Unix/Linux.
Hope to see you in the Top 100!
-- Denny Cronin <denny@prairienet.org>, April 1996
[ Editor: the initial posting, December 1997, of Michael Keller's
FreeCell mailing list ("FreeCell Forum"), with part 1 of his FAQ. ]
FreeCell -- Frequently Asked Questions (FAQ)
written by Michael Keller (Wgreview@aol.com),
<http://members.aol.com/wgreview/>
Please report any errors (even typos), omissions, or suggestions for
additional questions to me.
Proposed Table of Contents (* to be written)
1. History of the Game
2. The Microsoft 32,000
*3. More Statistical Facts
*4. Variations and Related Games
*5. Computer Versions and Features (URL's included)
Note: I have looked at every Windows and Java version I am aware
of. There are versions for Macintosh, OS/2, and other platforms which
I cannot run on my system. If anyone has access to any such machines
and would like to try out one of the other versions and make a brief
report, let me know and I will send you the URLs.
1. History of the Game
* Who invented FreeCell? How did it get started?
The idea of a game with temporary storage locations to hold single
cards is not new. One of the oldest games of this type is Eight Off,
which provides eight depots (or freecells) which can each hold one card
at a time. The tableau consists of eight columns of six cards each,
with the four remaining cards being dealt initially to four of the
eight depots. Cards are packed on the tableau downward IN SUIT, not in
alternate colors as in FreeCell. The foundations are built up in suit
just as in FreeCell, but empty columns can be filled only with kings.
In Martin Gardner's June 1968 Mathematical Games column in
Scientific American (reprinted in his 1977 book Mathematical Magic
Show), he describes a game by C.L. Baker which is a variant of Eight
Off. Baker's Game, as it is now called, differs from Eight Off in
having only four depots instead of eight -- the four extra cards are
dealt to the first four columns. An empty column may be filled with
any card, not just a king -- this allows them to be used as temporary
storage areas too, and allows large sequences of cards to be moved from
one column to another. This makes a better, more interesting game in
my view, though it is harder because it has only four depots instead of
eight. (An excellent freeware version of Baker's Game is available
under the trademark Brain Jam at many shareware sites, or from their
home page at <http://www.interlog.com/~brainjam/>.
Someone had the brilliant idea of changing Baker's Game in one
respect, packing the tableau downward in alternate colors as in
familiar games like Klondike and Canfield, thus producing the game we
know as FreeCell. This has the happy effect of making nearly every
deal winnable, though many are still quite difficult.
I don't actually know who invented FreeCell, though the current
suspect is Paul Alfille [Editor: spelled "Allfile" in the original;
Keller's later postings below give "Alfille"], who, according to
Dennis Cronin's NetCELL (Java) site at
<http://www.freecell.minivend.com/>, wrote a version for the PLATO
educational computer system in the early 1980's. The popularization of
the game is largely due to Jim Horne, who wrote a character-based
version for DOS and later a full graphical version for Windows. The
latter first appeared in 1992 on Microsoft Entertainment Pack 2, and
was later bundled with Microsoft's Windows 95. Dennis Cronin also
wrote a freeware version for UNIX in the mid-80's, and undoubtedly
there were other character-based versions floating around too.
2. The Microsoft 32,000 -- can they all be solved?
Jim Horne's version for Windows 3.1 contained 32,000 numbered
deals (games), so that selecting a specific number would always produce
the same deal. (These are random deals, generated by integer seeds
using the random number generator in the Microsoft C compiler). He
numbered the deals so that people could exchange the numbers of
difficult/interesting games with their friends, and also in the belief
that some people would try to play sequentially through the games.
Many people have in fact done so; I do not know of anyone who has
completed the entire set, but I know of one player nearly two-thirds
finished, and several others who have completed 5000 or more. Happily,
when the game was ported to Windows 95, the set of 32,000 deals was the
same, so any discussion of deal numbers applies equally to both
systems.
The help file for Microsoft FreeCell contains the claim "It is
believed (though not proven) that every game is winnable." When Horne
wrote this, he knew that unsolvable deals could be constructed. (As a
joke, the Windows 95 version includes two such games, numbered -1 and
-2). He purposely made the claim ambiguous in order to challenge
people to find such impossible games, but intending it to mean that all
of the 32,000 included deals were winnable. This comes as close as
possible to being true...
Part of the popularity of the game, besides Microsoft providing the
game free with Windows 95, is due to Dave Ring's Internet FreeCell
Project. Ring solicited volunteers on rec.puzzles and elsewhere
(eventually getting more than 100 people involved), and coordinated the
volunteers in an effort to solve all 32,000 of the deals in the
Microsoft versions. He assigned each volunteer a set of 100
consecutive deals, and the volunteers would report back when they had
solved (or tried to solve) all 100, when they would be assigned another
set if interested. Ring would reassign any hands reported as unsolved
to his best solvers. I got involved in the project fairly late, but
still managed to solve 1,970 deals.
Eventually the project was completed, and all but one deal was
reported solved! This is the famous game number 11982. I wrote an
article on FreeCell and Baker's Game which was published in the June
1995 issue of Games (Big Deal, pages 10-13) while the project was still
finishing up. Dave Ring wrote to Games after the project was finished,
reporting that the project was finished. Games printed Ring's letter,
along with a layout of the unsolved number 11982, in the October 1995
issue (page 4). A report that 11982 had been solved turned out to be
incorrect when it was discovered that the solver was playing Baker's
Game rather than FreeCell. 11982 has now eluded solution by probably
hundreds of human solvers, and at least three computer programs I am
aware of.
A report on the Ring project can be found at
<http://physics.tamu.edu/~Cdude/freecell.html>. A large catalog of
solutions to (mostly difficult) deals, including all of those reported
as hard during the project, can be found at
<http://www.capecod.net/~wcallan/freecell.htm>, along with other
FreeCell information and links. The solution catalog was begun by Dave
Ring, but is now being maintained by Wilson Callan.
A large-scale computerized statistical study, conducted by Don
Woods, analyzed a million random hands. Woods reported to the Usenet
group rec.games.playing-cards that the program had solved all but 14
of them, making the win rate for FreeCell better than 99.99%.
-- Michael Keller <Wgreview@aol.com>, December 1997
[ Editor: "FCF003 -- Unsolvable six-freecell games??", mailed by Keller
in January 1998: ]
[Note: This was Bill Taylor's reply to me about whether certain deals
could be solved with six freecells -- M. Keller]
The initial puzzles sent out were interesting, though initially seeming
trivial. This one posted by Don Woods and credited to Jim Boyce:
Ac Ad Ah As 2c 2s 3c 3s
4c 4s 5c 5s 6c 6s 7c 7s
8c 8s 9c 9s Tc Ts Jc Js
Qc Qs Kc Ks Td Th Jd Jh
Qd Qh Kd Kh 6d 6h 7d 7h
8d 8h 9d 9h 2d 2h 3d 3h
4d 4h 5d 5h
....wasn't too hard - I got it out first attempt, with 6 freecells.
>Can this be solved with six freecells? What if the suits
>are mixed up differently?
Haven't checked on that though. Next coming to "pattern -1"
A A A A Q Q Q Q
3 3 3 3 T T T T
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
....this also seemed easy, in that with a random suit-deal it came out
first time. However, there were some easy bits in the deal, so I
looked at the worst type of suit mixing that seems possible:-
That is: alternate red and black in every column, (this is maximally
unhelpful!), and, just to be on the safe side, within each column make
sure that all same-suits are at least 3 apart.
Then this is so awful, that not only does it seem to be impossible with
6 freecells, it even seems to be IMPOSSIBLE WITH 7 FREE-CELLS!
Even with 8 freecells, it is quite tough! (Though then it *can* be
done without putting out any aces - just piling up the four columns.
(Though, on the other hand, to do this seems to require using all 8
freecells several different times!))
So; if this is all old hat, sorry.
If not, can anyone confirm or deny these results?
-- Bill Taylor <W.Taylor@math.canterbury.ac.nz>
[ Editor: "New FC questions and answers", mailed by Keller in May
1998: ]
Updates:
Dave Ring's pages on the FC Internet Project have moved to:
<http://chaos.physics.tamu.edu/~Cdude/freecell.html>. His e-mail
address does not appear to work any longer, and I do not know how to
contact him at present.
Denny Cronin's online Java version NetCELL
<http://www.freecell.minivend.com/play.html>, now has a number of
variant games, ranging from 6 to 10 columns wide, and from 2 to 6
freecells available. Almost certainly some of these are too hard or
too easy, but the 10x2 (10 columns of 5 or 6, two freecells) and 6x6 (6
columns of 8 or 9, six freecells) are interesting. The top current
streak in the standard 8x4 game is 734 and the all-time best is 1005
(in order to break into the current top 100, you need to win 29 or 30
in a row)!
Adrian Ettlinger completed his survey of the first ten million
deals (using FCPro). There are 136 deals which cannot be solved with
four freecells, suggesting a loss rate of 1 in 70,000 to 75,000 deals
(a bit higher than the earlier estimate). Here is the full list:
11982, 146692, 186216, 455889, 495505, 512118, 517776,
717025, 781948, 1155215, 1254900, 1387739, 1495908, 1573069,
1631319, 1633509, 1662054, 1940838, 2022676, 2070322, 2166989,
2167029, 2501890, 2607073, 2681284, 2712622, 2843443, 2852003,
2855691, 2923820, 3113705, 3163790, 3172889, 3194539, 3217820,
3225183, 3366617, 3376982, 3402716, 3576395, 3595299, 3878212,
3917750, 3946538, 4055965, 4207758, 4266168, 4269635, 4324282,
4334954, 4440758, 4446355, 4765843, 4863685, 4910222, 5046726,
5050537, 5086829, 5225172, 5244797, 5260342, 5401675, 5478410,
5611185, 5672090, 5817697, 5862173, 6020049, 6099064, 6100919,
6234527, 6314799, 6332629, 6416342, 6511428, 6749792, 6761220,
6768658, 6844210, 6895558, 6898316, 7035805, 7139586, 7261039,
7334559, 7360592, 7400819, 7484159, 7497878, 7530003, 7536454,
7801943, 7814345, 7825750, 7863486, 7887312, 7923001, 7965413,
8000527, 8046431, 8076134, 8104908, 8105324, 8114984, 8119415,
8121228, 8237732, 8267373, 8354257, 8381178, 8470523, 8527378,
8608154, 8712426, 8719444, 8736337, 9093368, 9110337, 9190487,
9222830, 9262134, 9414989, 9415104, 9435589, 9452398, 9626317,
9647001, 9660366, 9747437, 9771903, 9773169, 9830419, 9855268,
9861848, 9902420, 9917279.
[ Editor: the March 2000 posting above reports that ten of these,
717025 among them, were later found solvable, leaving 126. ]
* Is it cheating to use computers?
Well, most of us are using a computer to deal and keep track of
the hands, and FCPro can record solutions automatically. I think it
is quite reasonable to use a computer to do things which would be
impossible, tedious, or time-consuming to do otherwise. The Internet
FreeCell Project took 110 people to finish; Adrian Ettlinger did more
than 300 times as many deals alone using FCPro and his computer. The
variable-freecell solver makes it possible to categorize deals into six
groups based on a rough difficulty rating, while leaving the more
interesting task of actually solving individual deals to humans (all of
the solutions in the main catalog were found by humans).
* Are all of the solutions in the catalog correct?
I hope so, but I can't be sure. A week's worth of work checking
hundreds of solutions one-by-one (loading each one into FCPro's replay
mode) should have found all of the mistakes, but at least one error we
know of slipped through. If you do find any errors, please let me
know.
* Why won't you post improved (shorter) solutions in the catalog?
There are several reasons. First of all, it means extra work for
me, and doesn't do much for anyone except the person sending in the
improved solution, who gets to see his/her name there. But the
catalog was never supposed to be a competition; the main purpose is to
give solutions to hard deals so that people who are stumped by a
particular deal can look up a solution. For that purpose, any decent
solution will do. Another point is that minimum-length solutions are
likely to be tricky rather than elegant -- solid technique will not
help you find the shortest solution; only playing around and cutting
corners will.
One of the reasons I stopped playing Championship FreeCell is that
if someone is the first to post a 2-freecell solution to deal number
xxxx, and someone else posts a shorter solution, the original poster
loses all credit whatsoever for having posted it -- so there is little
incentive (from a competitive point of view) to investigate and find
the minimum number of freecells needed to solve a particular deal for
which no solution has been posted -- it's better to steal deals from
someone else, especially if they are ahead of you in the rankings.
* Why won't you post every new solution submitted?
Because there isn't room for solutions to all 32,000 deals. Most
of them aren't interesting anyway: with reasonable experience almost
anyone can solve about half of the deals on the first try. Mainly
we're interested in solutions to hard deals, although solutions to
deals using zero and one freecells may be included, as well as
curiosities like flourishes (e.g. Andy Gefen's solution to 18492).
* Is there a version of FreeCell for Macintosh?
While there are at least two versions of FreeCell in Java, a couple
for OS/2 and other platforms, and probably a dozen in Windows, I know
of only two for Macintosh at the moment:
David Bolen's Super Mac Freecell at
<http://www.brbosoftware.com/super_mac_freecell/index.html>,
and Rick Holzgrafe's Solitaire Till Dawn (which includes FreeCell among
its 32 games) at <http://www.opendoor.com/Rick/STD.html>.
I have no access to a Macintosh, and have not seen either of these
programs.
Some of the versions for palmtops, OS/2, and other operating
systems are listed on the links page at
<http://members.aol.com/wgreview/fclinks.html>.
If anyone knows of other versions of FreeCell, please let me know.
We will be writing up versions found in various Windows packages when
we have time.
[ Editor: "New FC questions and answers", mailed by Keller in July
1998: ]
Updates:
I got in touch with Paul Alfille, who confirmed that he is the
inventor of FreeCell.
Dave Ring's pages on the FC Internet Project are gone. His e-mail
address does not work any longer -- if anyone knows how to contact him
please let me know. I would also like to get in touch again with Greg
Schmidt (one of the programmers who demonstrated that 11982 is
impossible) again.
* Why is FreeCell so popular?
I believe it is primarily because of the puzzle-like nature of
the game, and the fact that nearly every game can be won. Most
solitaires (including the most popular ones like Klondike, Spider,
Pyramid, Forty Thieves, and Miss Milligan) can be won less than half of
the time even with perfect play. Almost every FreeCell deal can be won
if played correctly; it has one of the highest win rates of any
solitaire (Fortune's Favor and Westcliff, among others, may possibly be
easier to win), yet individual deals run the gamut from trivially easy
to excruciatingly hard.
FreeCell is an open solitaire, meaning that all of the cards are
dealt out face-up at the start of the game, and the effect of any
series of moves can be worked out, without having to rely on judgement
and probability as in games like Klondike. FreeCell is also unique
among its relatives in using alternate-color packing on the tableau, a
feature which has proved its popularity in Klondike, Canfield, and many
other solitaires. Alternate-color packing gives the player a much
wider range of plays than in-suit games like Baker's Game and Seahaven
Towers, and also makes the win rate a bit higher.
* What has been written (off-line) about FreeCell?
Hardly anything. I wrote an article for _Games_ Magazine
(Michael Keller, "Big Deal", June 1995, pages 10-13) about FreeCell and
Baker's Game. FreeCell has not to my knowledge appeared in any books
on card solitaire or card games in general, despite its popularity in
the on-line world.
* I have played hundreds of the games randomly and started keeping
a log by game number. But I notice that I never seem to win one
twice. Does the game automatically turn up games which have not
been won?
No. The Microsoft program does not keep track of games which
have been played (whether won or lost). The New Game (F2) function
picks games entirely at random.
If you have kept track over 200 games, there is still a 53.2%
chance of seeing no repeated game numbers. For 300 games, the chance
drops to 24.2%; for 400 games, to 0.08%. So if you continue to keep
track, you should eventually see a repeat if you play enough games.
[ Editor: for 400 games the chance is about 8%, not 0.08%:
exp(-400*399/(2*32000)) = exp(-2.49) = 0.083, by the same
approximation that gives about 53.7% and 24.6% for 200 and 300. ]
* Which deal is the easiest? Are there any deals in which all
of the cards go automatically home at the start?
A deal where all of the cards go home at the start is easy to
construct, but it is fantastically unlikely for such a deal to occur
at random, since a card is only played to its home cells automatically
when all of the lower-ranked cards of the opposite color are already on
the home cells (I call this "safe autoplay"). So every column needs to
be in (nearly) descending order of rank. I would be surprised if there
were any automatic deals even in the 4 billion FCPro deals.
The 32,000 Microsoft deals include 62 deals which can be won
using no freecells at all. The largest number of cards which go to
the homecells at the start of any of these deals is six (including all
four aces), in deals 9998 and 11987. It's possible to get quite a few
more cards to the homecells with a minimal amount of moves in both
games, and these seem the two most likely candidates for the title of
"easiest deal".
[ Editor: the March 1998 extract above gives 64 zero-freecell deals
among the 32,000. ]
-- Michael Keller <Wgreview@aol.com>, 1998
[ Editor: posted to rec.puzzles in August 1998 (twice, identically). ]
FreeCell -- Frequently Asked Questions (FAQ) -- Condensed version
A full version of this FAQ is at
<http://members.aol.com/wgreview/fcfaq.txt>.
* Who invented FreeCell?
Paul Alfille, who also programmed the first version in 1978 for the
PLATO system.
* Where can I find solutions to difficult deals?
<http://members.aol.com/wgreview/freecell.html>.
* Are all deals solvable?
No. It is fairly easy to construct impossible deals. In the
Microsoft version of the game, every deal except 11982 can be solved.
A solving program written by Don Woods estimates that unsolvable
deals occur at random every 70,000 to 75,000 deals.
* Is there a way to objectively measure solving difficulty?
Yes, by determining how many freecells are needed to solve a
particular deal. About 1 in 500 deals can be solved without using
any freecells at all (see the solution to deal number 1150). Some
deals (about 19 percent) can be solved with only one freecell, and
most (nearly 79 percent) can be solved with two freecells. Nearly
all (99-1/3 percent) can be solved with three freecells. Many of the
deals most often reported as hard fall into the small category
requiring four freecells to solve, so this classification seems to
mirror human solving difficulty fairly well.
* Is it possible to get all 52 cards to the homecells at once?
Yes. Andy Gefen discovered such a solution for Microsoft deal number
18492. See the solution catalog.
* What are some other solitaires closely related to FreeCell?
Baker's Game, identical except that the tableau is packed in suit,
appears to be FreeCell's direct predecessor. A more distant ancestor
is Eight Off, found in most solitaire books. Recent relatives are
David Parlett's Penguin and Art Cabral's Seahaven Towers.
* How can I record solutions automatically?
Use FCPro, a free Windows 95 version of FreeCell written by Wilson
Callan and Adrian Ettlinger (available at
<http://members.aol.com/wgreview/fcpro.html>). This has the same
deal numbers as Microsoft's version and many other features.
-- Michael Keller, World Game Review, 1747 Little Creek Drive,
Baltimore, MD 21207-5230, <http://members.aol.com/wgreview/index.html>