FreeCell is a logic puzzle in the form of a solitaire card
game. It is unlike most solitaire games ... in that there
is no luck involved after the initial shuffle. There are
no hidden cards; they are all dealt face up at the start of
the game. It is believed (although not proven) that every
game is winnable.
In essence, FreeCell is a problem in finite combinatorics. It
asks whether eight stacks of playing cards can be sorted to four
output stacks, using a four card register and permitting a card
to be moved from the top of one stack to the top of another when
the usual usual solitaire rule holds: the moved element must be
one less and a different color than the card onto which it is
moved.
After thinking about it some, I believe that the answer is "no."
As a counter-example to the hypothesis that the game is always
winnable, I offer the deal below, which I believe is unwinnable.
(Card colors are irrelevant in this counter-example.)
A A A A 7 7 7 7
K K K K 6 6 6 6
Q Q Q Q 5 5 5 5
J J J J 4 4 4 4
10 10 10 10 3 3 3 3
9 9 9 9 2 2 2 2
8 8 8 8
Is this (1) a trivial result that almost everyone reached after
playing the game a little bit (except for the author of the help
file), (2) a wrong result, in which I misunderstand the game or
the strategy for playing it, or (3) of sufficient interest that
readers here might like a proof that the above hand cannot be
won?
Russell
--
The average Ph.D thesis is nothing but the transference of bones
from one graveyard to another.
-- Frank J. Dobie
>FreeCell is a game that Microsoft distributes with Win32. As it
>Is this (1) a trivial result that almost everyone reached after
>playing the game a little bit (except for the author of the help
Or does the freecell program use some strategy so as not to generate
obviously unwinnable games
>-*----
>FreeCell is a game that Microsoft distributes with Win32. As it
>says in its online help:
> FreeCell is a logic puzzle in the form of a solitaire card
> game. It is unlike most solitaire games ... in that there
> is no luck involved after the initial shuffle. There are
> no hidden cards; they are all dealt face up at the start of
> the game. It is believed (although not proven) that every
> game is winnable.
> A A A A 7 7 7 7
> K K K K 6 6 6 6
> Q Q Q Q 5 5 5 5
> J J J J 4 4 4 4
> 10 10 10 10 3 3 3 3
> 9 9 9 9 2 2 2 2
> 8 8 8 8
>Is this (1) a trivial result that almost everyone reached after
>playing the game a little bit (except for the author of the help
>file), (2) a wrong result, in which I misunderstand the game or
>the strategy for playing it, or (3) of sufficient interest that
>readers here might like a proof that the above hand cannot be
>won?
Well, I've never seen this deal in the game. Doesn't look like
it could be won. I have won every deal I've seen in the game,
though. Some were very hard, and I had to play many times to
figure out (169 was the hardest one I can remember). There
are only 32000 deals avaliable, obviously not every one that
is possible. Perhaps the deal # somehow builds the deal in a
systematic way, assuring that it can be finished.
Adam Hayek
Well, it's no estimate, it's a statement. The statement is clearly false
and probabilities have nothing to do here. I agree that almost all games
are winnable, but you can just fiddle around with the counterexample and
come up with some (I don't know how many) that are unwinnable.
The poster did not argue that it was a regularly happening thing, It's just
that the claim is false (as the author should have understood himself IMHO).
|> > the game. It is believed (although not proven) that every
|> > game is winnable.
Jarle.
---------------------------------------------------------------------
Nuke the Whales ! | Jarle Brinchmann,
| Email: Jarle.Br...@astro.uio.no
International Krill Union. | or : jar...@astro.uio.no
The odds of shuffling a deck and dealing that exact setup are the same
as the odds of shuffling a deck and dealing any other particular
setup.
>Pleas edon't flame this message, I was just pointing out that ALL solitaire
>games are based on RANDOMNESS !! and we CANNOT Exclude That !!
But nowhere does it say that the initial setup has to "look random".
Seth
: Russell
From the help which comes with this game, it is not clear whether the
author speaks of _all_ combinations possible or only of those provided
(32,000). I tried to solve them one by one. Among the first 500, I failed
to make three. Yes the counter-example you are giving is correct. Now
come two questions.
1. How many hands are there in this game?
2. How many of them are solvable?
Andrey
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Andrey Tsouladze * *
* Department of Biology * You *
* Technion - Israel Institute of Technology * have *
* Haifa 32000 * been *
* Israel * warned... *
* E-mail: ts...@aluf.technion.ac.il * *
* E-mail: ts...@techunix.technion.ac.il * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
But is this one of the games that freecell brings up? If so, what
number is it?
What you failed to notice is that you have no idea of what "random" means.
--Tim Smith
Given the wording in the passage, I find it hard to believe that
'every game' means numbered games only. Then again, it is also hard to
believe the programmer would make such a silly statement.
Dave Ring
Cd...@phys.tamu.edu
Oops, I take that back. ;-)
I'm not sure, but this looks like "Baker's Solitare" described in Martin
Gardner's column in Scientific American ca. 1970. It's an interesting
solitare that I've played quite a bit over the years, and I find it's hard to
beat, but it helps to spend a lot of time thinking before moving.
--
David E. Joyce Dept. Math. & Comp. Sci.
Internet: djo...@black.clarku.edu Clark University
BITnet: djoyce@clarku Worcester, MA 01610-1477
> Given the wording in the passage, I find it hard to believe that
> 'every game' means numbered games only. Then again, it is also hard to
> believe the programmer would make such a silly statement.
The fact that there is so much discussion shows that the statement can
be read differently. It is only silly to people who read it the way you
do. The programmer wrote a program, that program offers 32000 games, if
that programmer refers to "every game" it means every one of the 32000
the way I read it.
Consider the Helmutt-Schwartzbald Car-Sales-Lot theorem; A salesman has
20 cars on his lot - he says "every car comes with a CD player" - that
doesn't mean every car in the world, it means every car on his lot.
--
Mark Shasby | "GNIP" - oops! - we forgot the terminating resistor.
That was implied.
> The programmer wrote a program, that program offers 32000 games, if
>that programmer refers to "every game" it means every one of the 32000
>the way I read it.
>
> Consider the Helmutt-Schwartzbald Car-Sales-Lot theorem; A salesman has
>20 cars on his lot - he says "every car comes with a CD player" - that
>doesn't mean every car in the world, it means every car on his lot.
I think we can uniformly agree that "It is believed (although not proven)
that every car comes with a CD player" would be a silly statement.
Dave Ring
Cd...@phys.tamu.edu
dwr...@tam2000.tamu.edu (David Wayne Ring) writes:
> I think we can uniformly agree that "It is believed (although not proven)
> that every car comes with a CD player" would be a silly statement.
Given that there are, according to the help, only 32,000 games, yet there
are approximately 8.3 x 10^61 initial permutations* of the cards, I think
we can conclude that not all permutations are valid games. Thus an unwinnable
permutation does not prove that some games are unwinnable.
* # of permutations == 52! / (4! * 8!); the 4! is for the suits (since their
order is irrelevant), and the 8! is for the stacks (ditto).
--
[ /tom haapanen -- to...@metrics.com -- software metrics inc -- waterloo, ont ]
[ "only a toy." -- alexander graham bell's father-in-law, 1876 ]
Not good try again
The order of the suits is relevant for winnable/unwinnable.
Just think of a game easisly winnable (if only that 2 of hearts wouldn't be that far off :-)))
Axel
In addition to which, if "every game" refers only to the games in some
preprogrammed set of 32000, it seems awfully lazy of the programmer
not to use a generating algorithm that provably generates only
winnable games (e.g. by playing backwards). (Or, perhaps, to simply
program the computer to solve all 32000 games one by one, though
perhaps this is more difficult than it looks at first glance.)
-- David A. Karr (ka...@cs.cornell.edu)
zcca...@rpool5.rus.uni-stuttgart.de (Axel Hecht) writes:
> The order of the suits is relevant for winnable/unwinnable. Just think
> of a game easisly winnable (if only that 2 of hearts wouldn't be that
> far off :-)))
No ... consider the suits to be A, B, C and D. Picking A to be hearts and
B spades does not produce a different game than with B hearts and A spades.
The same holds for the full set of four suits.
--
[ /tom haapanen -- to...@metrics.com -- software metrics inc -- waterloo, ont ]
[ "until the lions have their own historians, ]
[ tales of hunting will always glorify the hunter." -- zulu proverb ]
and in a later post:
> [C]onsider the suits to be A, B, C and D. Picking A to be hearts and
> B spades does not produce a different game than with B hearts and A
> spades. The same holds for the full set of four suits.
Unless I misunderstood the description of the game, the order of the
suits is relevent, because you have to play red on black and vice versa.
So you should be dividing by a factor of 8 for the suits, not 4!.
Similarly, not all the stacks are the same - there are four stacks of
seven cards and four stacks of six cards, so the factor for the stacks
should be 4!4!, not 8!.
ObPuzzle: a variation on FreeCell is to determine the minimum size of
register (by which I mean the space in which you can store awkward
cards) needed to solve a given configuration (apparantly the computer
game comes with a register of fixed size 4). For example, the
unwinnable deal posted earlier in this thread could be solved with a
register of size 6, I think. What's the worst case, i.e. the largest
register you might need?
--
Gareth Rees
It seems several people have played this game extensively. Do any of
you remember the numbers for the really hard hands?
Dave Ring
Cd...@phys.tamu.edu
: It seems several people have played this game extensively. Do any of
: you remember the numbers for the really hard hands?
In my previous posting to this thread, I said I failed to make three out
of the first 500 deals. Well now I made all of them. Among those, It took
me most attempts to make #194, 285, and 454.
Wow I do not think I'll _ever_ play this game again.
I thought the game described in that article had a slight variation on
the moves allowed - that cards could only be moved onto the next higher
card of the same suit. This makes it a bit harder as it constrains the
number of moves allowed at any given time.
I've never had the patience to copy out a configuration and play it
repeatedly until I win it (but have toyed with the idea of writing
a program to do backtracking and try that way to win), but when I
first started playing I could win only infrequently and my last
bout with this game probably had me winning about half the games.
I also find that its a fun game to play when there is someone else
around as it involves several minutes of staring at the configuration
followed by a flurry of moves, followed by minutes of staring...
--
je...@nmt.edu -- Jeff Putnam, New Mexico Tech, Socorro, NM
"You never learn anything, you just get used to it."
>In my previous posting to this thread, I said I failed to make three out
>of the first 500 deals. Well now I made all of them. Among those, It took
>me most attempts to make #194, 285, and 454.
>Wow I do not think I'll _ever_ play this game again.
My gf solved 454 yesterday, and now I'm working on 1941, which someone
mentioned to me. 169 always gives me problems; I eventually get it, but
I can never remember how and do it twice in a row, seriously pissing me off.
Adam Hayek
FreeCell is a logic puzzle in the form of a solitaire card
game. It is unlike most solitaire games, however, in that
there is no luck involved after the initial shuffle. There
are no hidden cards; ... It is believed (although not
proven) that every game is winnable.
To the mathematically inclined, this strongly suggests a
mathematically interesting puzzle about whether or not "every
game is winnable." For this to be the case, we must have
adequate information about the game space to which "every game"
refers. Moreover, FreeCell is called a logic puzzle, again
suggesting a logical (not brute force) solution to whether or not
every game is winnable. Because the algorithm for generating the
32K games is not given, the natural assumption is that "every
game" refers to all logically possible deals, not merely all
deals in the computer program. But there are easy examples of
logically possible deals that cannot be won.
So is there an interesting logic puzzle about whether the 32K
actually generated games are winnable? Alas, no.
It turns out that the deal is merely psuedo-random draw, without
any interesting algorithmic device to possibly guarantee
winnability. If the 32K games are all winnable, the programmers
merely lucked out in their choice of a psuedo-random sequence.
The help file would have been better written:
The computer program generates 32K deals from a very large
space of all possible deals. So far, all the generated games
we have examined are winnable. We have not checked them all.
Clearly, one could write a program (easy in Prolog) that checks
each of the 32K generated deals. Whether or not this particular
psuedo-random sequence contains an unwinnable deal does not seem
an interesting question to me, so I will leave it to others to
write the program.
But playing the game is fun, even if there is no deeper "logic
puzzle" in it.
Russell
--
"The fact that a believer is happier than a skeptic is no more to the
point than the fact that a drunken man is happier than a sober one.
The happiness of credulity is a cheap and dangerous quality."
-- George Bernard Shaw
It is conjectured (based on the number of winnable games in a sample of
1000) that about 80% of games are winnable.
My favorite thing to do with freecell is see how many cards I can keep on
the playing field before one final move suddenly sends them all fluttering
up to the destination stacks.
So far the best I have done is 48 (but don't ask me to reproduce it).
I also suspect the percentage of easily winnable games is around 66% (because
that's what I am running at, and I give up easy :-).
--
--
Tom.H...@mail.csd.harris.com
Home: 511 Kingbird Circle Delray Beach FL 33444
Work: Harris Computers, 2101 W. Cypress Creek Rd. Ft. Lauderdale FL 33309
Play: Sec149,Row21,Seat23 Joe Robbie Stadium, 2269 N.W. 19th St Miami FL 33056
Gee, I thought I was the only loon around!
America is in serious trouble! :) :) :)
>--
>Tom.H...@mail.csd.harris.com
Matt Lih (l...@venice.sedd.trw.com)
-- Save Father Time from a horrible death! Delete Freecell!
Pointless? FreeCell is absolutely essential!!!
I've formulated a sort of FreeCell "PrimeDirective":
"You may never replay a game that you lose".
This is the only way to make it fair. You have to be absolutely sure of every
move. If you get stuck, you go down in flames!
Real men (and women) don't need second chances!
FreeCellers of the world --- UNITE!!
:- - - - - - - Brad Aisa - - - - - - -:
: Software Engineer Toronto, CANADA :
: tel (416)423-4075 fax (416)423-8050 :
: - - - - - ba...@hookup.net - - - - :
My version says:
"FreeCell is a logic puzzle in the form of a solitaire card game."
The guy doesn't say it _is_ a solitaire card game -- he says it's a
_logic_puzzle_. That indicates quite clearly to _me_ that he's
mathematically sophisticated and _not_ just a bozo with questionable
judgement. I'd venture to guess that his statement:
"It is believed (although not proven) that every game is winnable."
is just a concession to Murphy's Law as applied to programming.
I think the original poster's counter-example was _also_ interesting,
however, as I hadn't even looked at the "help" screen, or thought very
much about the "game".
- Lenny Gray -
My friend sitting next to me at this moment plays Freecell extensively
and she has found no games that she cannot win.
Now, to end this on going argument
"Every one of these 32000 games is winable"
I like to get a collection of games that anyone think is unwinable and
let my friend try.
She has an average continuous win of twenty. So please summit some game
number to me, I believe that if there is a game number that she cannot
solve, it will be not far from unwinable.
--
Edmund H.W. Hor
Trayport Computers Ltd (A Consultancy and Development Team)
London, United Kingdom
voice : 081-464-3643
fax : 081-402-9252
email : ed...@trayport.demon.co.uk
Well, the argument seems to have died of boredom.
>She has an average continuous win of twenty. So please summit some game
>number to me, I believe that if there is a game number that she cannot
>solve, it will be not far from unwinable.
^^^^^^^^^^^^^^^^^^^^^^
I'm not quite sure what this means. :-)
The hardest one posted seems to be #1941. To not spoil her fun, I won't
tell you if I have solved it, but it is much harder (IMHO) than the others.
I would like to suggest that any hard #'s which people find in the future
be posted to rec.puzzles. That way we might find an unwinnable deal, and
we can get some good puzzles while we're at it.
Follow-ups to rec.puzzles.
Dave Ring
Cd...@phys.tamu.edu
>In article <baisa.34...@hookup.net> ba...@hookup.net "Brad Aisa" writes:
>My friend sitting next to me at this moment plays Freecell extensively
>and she has found no games that she cannot win.
>Now, to end this on going argument
>"Every one of these 32000 games is winable"
>I like to get a collection of games that anyone think is unwinable and
>let my friend try.
We could always split up the games between a bunch of people and see
which one's are too tough...
If we had 320 people, it could be done in a week.
--
David Charles LeBlanc
Georgia Institute of Technology, Atlanta Georgia, 30332
Internet: gt6...@acme.gatech.edu
This could easily be organized in the following way: Each participant
emails the organizer (I would be happy to do it if there is sufficient
interest) who emails back with a block of 100 hands.
the participant can solve them at his own pace, since the whole project
will take a while and there are plenty of blocks. The participant reports
back a list of deals he couldn't do, which are then repackaged and sent
out in blocks of 10 to the more enthusiastic participants.
Progress reports could be posted occasionally which will also serve to
encourage new (and old) participants.
Dave Ring
dwr...@tam2000.tamu.edu
Regards, Bonnie
*******************************************************************
I hate paranoid people, they're everywhere!
People need to _email_ me, since I posted the announcement to some groups
that I don't read.
--
Dave Ring | If you would like to participate in the Internet
dwr...@tam2000.tamu.edu | FreeCell Project or find out what it is, email me.
Is FreeCell the same game as Seahaven Towers? Seahaven Towers starts by
dealing out 10 piles of 5 cards each onto the "Board", so that they are
all visible, and dealing the remaining two cards onto two of the four
"Towers". The object is to build up the four suit piles from Ace to King
in sequence. On the Board, a card can only be moved onto the next higher
card of the same suit; a king can only be moved into an empty column.
Any card can go in the Towers, but there can only be one card on each Tower.
I first saw this implemented on the Macintosh several years ago; it was by
Art Cabral of Longwood Associates. My own copy, for Microsoft Windows,
is from Cary Farrier (far...@netcom.com). It's very addictive. I have
played hundreds of games. If FreeCell is the same game, I would be willing
to work on this, except that in Seahaven Towers the games aren't numbered.
Possibly the numbering has something to do with the initial deal?
Ruchira Datta
da...@math.berkeley.edu
FreeCell is certainly not the same as Seahaven Towers. Terry Weissman
has written an X version of Seahaven for which I wrote "autoplay"
code. There are many Seahaven positions which are provably unsolvable.
Among other differences FreeCell alternates colors, while Seahaven
requires playing on the same suit.
-- Charles
>ed...@trayport.demon.co.uk ("Edmund H.W. Hor") writes:
>>In article <baisa.34...@hookup.net> ba...@hookup.net "Brad Aisa" writes:
>>My friend sitting next to me at this moment plays Freecell extensively
>>and she has found no games that she cannot win.
>>Now, to end this on going argument
>>"Every one of these 32000 games is winable"
>>I like to get a collection of games that anyone think is unwinable and
>>let my friend try.
>We could always split up the games between a bunch of people and see
>which one's are too tough...
>If we had 320 people, it could be done in a week.
I'm willing to help.
Steve Klassen
st...@photon.cuc.ab.ca
--
Jered Floyd - jjf...@vela.acs.oakland.edu
Geek Code 2.1 - GAT d? H- s-:- g- p? !au a-- w+ v+ C++++ UL++++ P+ L++
N+++ K+++ W++ M-- V-- -po+ Y++ tv+ 5+++ j++ R v++ b+++ D+++ B--- e* u**
h++ f? r? n- !y+ (Finger for PGP key, picture, humor anOUT OF SPACE
Dick
OK, you got me interested. Excuse my ignorance, but our news server
has been down for a while so I don't know what FreeCell is. Can anyone
enlighten me? Thanks,
Jack van Rijswijck
jav...@bausch.nl
It is a card game that comes with the Win32s binaries to test the installation
on WFWG. These are available on ftp.microsoft.com and the CICA archives.
It is a very insidious, slowly but surely addictive game. You have been
warned.
>does anyone know whether every game of Seahaven Towers is winnable?
Yes. No.
-- Charles