Take the 2-minute tour ×
Board & Card Games Stack Exchange is a question and answer site for people who like playing board games, designing board games or modifying the rules of existing board games. It's 100% free, no registration required.

When I have free time in small durations, I often play Free Cell on my phone. The app that I use permits unlimited undos, and because of this I currently have a run of 603 wins, with 655 total wins and 10 total losses.

As is demonstrated by those statistics, my 10 losses occurred during my first 52 games. Prior to using this app, I had only played Free Cell very rarely.

As my statistics approach a 1% loss rate, I have to wonder: Given an unlimited ability to undo your moves, is there any initial deal of Free Cell that is impossible to solve?

A proof one way or another would be ideal (although I admit that I doubt I'd be able to comprehend such a proof), although an authoritative source would be a good alternative.

share|improve this question
1  
This site might be useful: solitairelaboratory.com/freecell.html –  Neal Tibrewala Apr 21 at 6:21

1 Answer 1

up vote 22 down vote accepted

It's not hard to prove that an unsolvable start exists. Just imagine a start where the only possible first moves would be moving cards to the extra cells. In some versions, -1 and -2 are examples of this though the only way to play them is to choose that seed. enter image description here

If you only count setups which can exist in normal play, seed 11982 in the Windows version is an example of this: enter image description here

Of the original 32000 games in Freecell, 11982 is the only one for which no legitimate solution was found. Since then, several computers and players have failed to find a solution- to the point where every possible combination of moves has been tried and has failed.

share|improve this answer
1  
As far as I've read, the 32,000 "deals" in the original Windows version are accidentally those produced when the MS C Compiler's random number generator is seeded with the values 1-32,000. In other words, they don't have any special status as such, and 32,000 is of course an infinitesimal fraction of the number of possible ways of shuffling a deck of cards (and a small fraction of the number of possible shuffles that even a modest random number generator could produce). –  Neil Coffey Apr 19 at 3:27
1  
Definitely accidental. The aforementioned random number generator has 15 bits of entropy, which means 2^15 possible orderings. That's 32,768. –  ikegami Apr 19 at 6:18
    
@ikegami: It has more bits of state, but it only hands out the higher-order bits (because low-order bits are crappy with LCGs). –  Joey Apr 27 at 19:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.