Hi Gary,
On Tue, 2 Oct 2012 06:21:57 -0700
"Gary Campbell" <gary_at_numin8r.us> wrote:
> Just to address one minor point of Shlomi’s last posting (I’ll cut
> out the rest).
>
> I don’t know of anybody (or any FreeCell solver) that has addressed
> more than the 13 ranks of the natural deck of cards, so the NP
> complete version “generalised Freecell” hasn’t caught anyone’s
> attention (as a problem to be solved) as far as I know. Given more
> than 4 free cells, the game becomes rapidly less interesting. Given
> the 13 ranks (a standard 52-card deck), 8 columns, and and 0 to 4
> free cells, you pretty much have what we have, and it is clearly not
> an NP complete problem. I’m not sure why this issue keeps cropping
> up.
>
Well, I may argue that a Freecell problem with 100 levels of ranks is not
NP-complete either, because the number is still limited. However, it would
be significantly harder than the 13 ranks of the French deck, which in
turn is harder than that of decks with a smaller number of cards.
My complete quote was:
[QUOTE]
OK. There has been some research which showed that generalised Freecell
is NP-complete (as a function of the number of ranks), see:
http://en.wikipedia.org/wiki/FreeCell#Complexity
This may set a hard limit to the number of minimal moves.
[/QUOTE]
What I meant by that is that there may be some implications on the depth of
the moves graph until reaching the shortest solution, which would be implied
by the fact that generalised Freecell was found to be NP-complete. I'm not much
of a computer scientist, so I it's just a speculation, but it prove to
be insightful.
Regards,
Shlomi Fish
> -Gary Campbell
>
> From: Shlomi Fish
> Sent: Tuesday, October 02, 2012 1:53 AM
> To: fc-solve-discuss_at_yahoogroups.com
> Cc: dannyjones183_at_yahoo.com
> Subject: Re: Status of 8x4 FreeCell Deals
>
> OK. There has been some research which showed that generalised
> Freecell is NP-complete (as a function of the number of ranks), see:
>
> http://en.wikipedia.org/wiki/FreeCell#Complexity
>
>
>
> Switch to: Text-Only, Daily Digest • Unsubscribe • Terms of Use •
> Send us Feedback .
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Free (Creative Commons) Music Downloads, Reviews and more - http://jamendo.com/
Real men don’t listen to sentences that start with “Real men don’t”.
— http://whatsup.org.il/article/6023
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Tue Oct 02 2012 - 06:46:07 IST