> 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