From cbrown@cbrownsystems.com Sun Apr  3 23:31:44 CDT 2005
Article: 382133 of sci.math
Path: news!news.niu.edu!news.illinois.net!attcg1!attcg2!ip.att.net!news.binc.net!news-out.cwix.com!newsfeed.cwix.com!newscon02.news.prodigy.com!prodigy.net!news.glorb.com!postnews.google.com!o13g2000cwo.googlegroups.com!not-for-mail
From: cbrown@cbrownsystems.com
Newsgroups: sci.math
Subject: Re: A new PROBLEM
Date: 3 Apr 2005 14:47:06 -0700
Organization: http://groups.google.com
Lines: 50
Message-ID: <1112564825.954576.223210@o13g2000cwo.googlegroups.com>
References: <1112430496.530072.270240@f14g2000cwb.googlegroups.com>
   <3b8fjsF6clvu7U1@news.dfncis.de>
   <ee2a1ba0.0504022241.7cfd224@posting.google.com>
NNTP-Posting-Host: 24.4.225.98
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
X-Trace: posting.google.com 1112564830 26042 127.0.0.1 (3 Apr 2005 21:47:10 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sun, 3 Apr 2005 21:47:10 +0000 (UTC)
User-Agent: G2/0.2
Complaints-To: groups-abuse@google.com
Injection-Info: o13g2000cwo.googlegroups.com; posting-host=24.4.225.98;
   posting-account=GYng8QwAAAASJCdK-kCiIRtmF4RV4yrR
Xref: news sci.math:382133

john wrote:
> Dear all
> In the windows help menu regarding the solitaire game the windows
team
> say that it is assumed that at any stage the gam can be winned. The
> question is whether we can mathematically prove the fallacy of that
> statement.

I think the game you mean is not "Solitaire" but instead is "FreeCell".
The "Help" page says:

"* Note: It is believed (although not proven) that every game is
winnable."

This is strictly false. From the "File" Menu, choose "Select Game...",
and enter the number "-1" or "-2" (minus one or two). The games
selected cannot be won (rather obviously).

So the programmers already knew that there existed (potentially) a deal
that cannot be won. But based on the (original) algorithm used to
generate FreeCell shuffles, there were only 32000 different possible
deals, which is considerably less than the total number of _possible_
deals.

(ObProb: How many distinct deals are there in FreeCell?)

However, one of these 32000 deals (game #11982) has been shown to be
unsolvable; there was (for a while) a group of people on the net trying
to solve every possible shuffle (!!).

See:

http://www.solitairelaboratory.com/fcfaq.html

for a description, and more background/analysis.

FreeCell on WinXP now lets you select one of 1000000 games (3 times as
many as the original); so there may be a few more unsolvable ones
lurking in the fog...

For a mathematical analysis of an unsolvable game (not in the standard
set), see:

http://www.cs.uu.nl/~hansb/d.freecell/freecellhtml.html

Cheers - Chas

> thanks
> hysen