I was playing the solitaire game Klondike the other day - my excuse is I
was bored and waiting for a phone call. Having won a game, I glanced
idly at the number of moves I had made; to my surprise it was 150. I
suspect that that was a less than optimal number but it also made me
think about the greatest number of moves a solvable game would need.

The minimum number of moves is trivial to calculate - it's 60; but how
the hell do I calculate the maximum number necessary?  Remember, it's
the maximum number necessary; if a game can be solved in several ways,
the lowest number is the one to be used.

John
-- 
Protect the Earth
It was not given to you by your parents
You hold it in trust for your children

Post a reply to this message

> I was playing the solitaire game Klondike the other day - my excuse is I
> was bored and waiting for a phone call. Having won a game, I glanced
> idly at the number of moves I had made; to my surprise it was 150. I
> suspect that that was a less than optimal number but it also made me
> think about the greatest number of moves a solvable game would need.
>
> The minimum number of moves is trivial to calculate - it's 60;

Aren't there a few different rules on how to play Klondike? How do you 
get the 60 number, I haven't played it for ages (not since Win95).

> but how
> the hell do I calculate the maximum number necessary?  Remember, it's
> the maximum number necessary; if a game can be solved in several ways,
> the lowest number is the one to be used.

According to wikipedia there are 7000 trillion possible start 
configurations, and about 80% of them are theoretically winnable (if you 
don't make any wrong moves). I suspect it would be quite complex (or 
perhaps impossible without brute force) to find the maximum of the 
minimum numbers of moves needed to win from each start configuration. 
Just a guess, but that 7000 trillion number is going to rule out any 
brute force algorithms.

Post a reply to this message

On 15/12/14 13:12, scott wrote:
>> The minimum number of moves is trivial to calculate - it's 60;
> 
> Aren't there a few different rules on how to play Klondike? How do you
> get the 60 number, I haven't played it for ages (not since Win95).
> 

Assuming you're using the 'draw three' rules:
1. Moving the cards from the playing piles to the foundation: 28 moves
2. Since there are 24 cards in the talon, to expose them all: 8 moves
3. Move these cards from the waste pile to the foundation: 24 moves

28+8+24=60 Simples!

Note: if you're using 'draw one' rules, you need a total of 76 moves

28+24+24

> According to wikipedia there are 7000 trillion possible start
> configurations, and about 80% of them are theoretically winnable (if you
> don't make any wrong moves). I suspect it would be quite complex (or
> perhaps impossible without brute force) to find the maximum of the
> minimum numbers of moves needed to win from each start configuration.
> Just a guess, but that 7000 trillion number is going to rule out any
> brute force algorithms.
> 

I suspected as much, but I live in hope of finding an elegant way of
calculating the answer - otherwise, I'll have wait for an affordable
quantum computer :-)

BTW Your prediction about The Saints performance seems to be coming
true. How about predicting that they'll return to form for the Everton game.

John
-- 
Protect the Earth
It was not given to you by your parents
You hold it in trust for your children

Post a reply to this message

On 15/12/2014 03:49 PM, Doctor John wrote:
> I suspected as much, but I live in hope of finding an elegant way of
> calculating the answer - otherwise, I'll have wait for an affordable
> quantum computer :-)

We already have those; it's called THE REAL WORLD. ;-)

Post a reply to this message

On 15/12/14 17:52, Orchid Win7 v1 wrote:
> On 15/12/2014 03:49 PM, Doctor John wrote:
>> I suspected as much, but I live in hope of finding an elegant way of
>> calculating the answer - otherwise, I'll have wait for an affordable
>> quantum computer :-)
> 
> We already have those; it's called THE REAL WORLD. ;-)

Unfortunately, I don't seem to be able to master its programming
language :-(

John
-- 
Protect the Earth
It was not given to you by your parents
You hold it in trust for your children

Post a reply to this message

On 15/12/2014 18:30, Doctor John wrote:
> Unfortunately, I don't seem to be able to master its programming
> language:-(

Well, you've had enough time to try. :-P

-- 

Regards
     Stephen

Post a reply to this message

On 15/12/14 20:14, Stephen wrote:
> On 15/12/2014 18:30, Doctor John wrote:
>> Unfortunately, I don't seem to be able to master its programming
>> language:-(
> 
> Well, you've had enough time to try. :-P
> 

... and that from a man who still confuses SDL with LSD :-D

John (wanders off singing Lucy In The Sky With Diamonds)


PS I've just noticed that my spell-checker flags SDL but not LSD.
-- 
Protect the Earth
It was not given to you by your parents
You hold it in trust for your children

Post a reply to this message

On 16/12/2014 03:44, Doctor John wrote:
> On 15/12/14 20:14, Stephen wrote:
>> On 15/12/2014 18:30, Doctor John wrote:
>>> Unfortunately, I don't seem to be able to master its programming
>>> language:-(
>>
>> Well, you've had enough time to try. :-P
>>
>
> .... and that from a man who still confuses SDL with LSD :-D
>

No, you are confusing me with someone who gives a damn. ;-)

> John (wanders off singing Lucy In The Sky With Diamonds)
>
>
Ah! Those were the days (my friend). :-D

> PS I've just noticed that my spell-checker flags SDL but not LSD.
>

  Libra Solidus Denarius?

Windoze spell checker could not spell its way out of a wet paper bag. 
Google is much better.

-- 

Regards
     Stephen

Post a reply to this message

> Assuming you're using the 'draw three' rules:
> 1. Moving the cards from the playing piles to the foundation: 28 moves
> 2. Since there are 24 cards in the talon, to expose them all: 8 moves
> 3. Move these cards from the waste pile to the foundation: 24 moves
>
> 28+8+24=60 Simples!

OK it's clear I've either forgotten the rules or was always doing it 
wrong! I would have said 52 moves...

> BTW Your prediction about The Saints performance seems to be coming
> true. How about predicting that they'll return to form for the Everton game.

After the loss with Burnley then I don't know what to expect next!

Post a reply to this message

This reminded me of a question I asked in another forum:

There's a video out there of a Texas Hold'em showdown between
two players where one of the players has four aces and the other
has a royal flush. What is the probability of this happening?
(Express the answer in the form "1 in x".)

-- 
                                                          - Warp

Post a reply to this message