Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sometimes finishing a game of FreeCell takes me 10 minutes, other times just one minute.

I know that all but one of the FreeCell deals in windows can be won, but I'm not sure if they are random or not [yet that is irreverent].

Assume: ALL GAMES POSSIBLE. Random deal. NO Automation.

IE. The minimum number of clicks is 52, not 0.

What is the average minimum number of moves necessary to complete a game of Freecell?

share|improve this question
    
What do you mean? Layout all the rules of FreeCell? Explain exactly what I mean by automation...? –  wizlog Jul 26 '11 at 21:02
2  
I mean you should ask a concrete question. I have added what I surmise is your true question on the subject. If I misinterpreted your question, please edit it accordingly. –  JavaMan Jul 26 '11 at 21:07
    
See en.wikipedia.org/wiki/Free_cell#Solving. The games in Windows are not random; Windows XP contains 8 unsolvable deals out of a million, so there are probably very many unsolvable ones overall. You'd have to specify how to treat these; i.e. not include them in the average. Also, note that it says that the problem is NP-complete in the number of cards; since it seems unlikely that it will be possible to determine the minimal number of moves without actually finding them, you're unlikely to get an answer to this question in the foreseeable future. –  joriki Jul 27 '11 at 2:08
    
I will still remain hopeful on the getting an answer. Just remove all non solvable deals. –  wizlog Jul 27 '11 at 3:21

2 Answers 2

up vote 7 down vote accepted

Astoundingly enough, this has already been studied. And I'm almost embarrassed to say that I'm familiar with the result. I used to freecell a lot. And FYI, 11982 is the impossible Frecell game. But I recommend entering in games -1, -2, -3, etc too.

So here are some stats from some studies of freecell. Firstly, the depth of the aces, i.e. how many cards cover the aces, is not a good measure of difficulty. On average, 11.077 cards cover the aces (counting aces). Analyzing the dozens of thousands of deals, it takes an average of somewhere between 42.12 (from a solver that ran 1.5 million deals) and 46.33 (from a solver on 32000 deals, the original 32000) moves to solve. This is a hard measure, as this is based on the quality of the solver - and it is unknown whether these solvers were optimal.

An interesting player-based study showed that about 79% of deals are solved by a person on their first try. It also turns out that some people examine how many freecells (the four in the top left) are actually necessary to solve a game. The impossible 11982 can be solved with 5 freecells. Almost every game can be solved with 3. Over half can be solved with 2. And almost 100 can be solved without any freecells at all. Take that, freecell!

One of the big problems is that freecell games are not at all randomly assorted, and so pencil and paper solutions aren't around. But lots of people have (surprisingly) cared about these questions, and so these results are all upper bounds. In short, about 45 moves is the average minimum.

References:

[1] http://solitairelaboratory.com/fcfaq.html

[2] http://scscompa.com/MainWebPage/freeceln.htm (which was done by hand, astoundingly)

share|improve this answer
    
"An interesting player-based study showed that about 79% of deals are solved by a person on their first try." Are they allowed to take back moves? –  wizlog Jul 27 '11 at 14:47
    
I believe the "first try" part is basically most players (whatever this means, maybe somebody who plays often?) don't look that far into the future and don't anticipate all the consequences of all their moves. If they get another shot they may see some moves they did were not very wise and could revise them on later tries. –  dinoboy Dec 6 '12 at 15:39

It is interesting to see this discussion here which I discovered after the solutions' length has been discussed in recent (as of 6-December-2012) threads in the fc-solve-discuss mailing list (which I administrate), as well as some configurations that improved the solution length performance of Freecell Solver, a solver for Freecell and other solitaire deals (which I maintain).

Like other people note here, Generalised Freecell (where the number of ranks increase beyond the 13th rank (King)) is NP-complete, but regular Ace-to-King-based Freecell is not (although 13 is still a significant value for NP-complexity to handle) .

One issue that we found hard to resolve is how to measure the number of moves, because there are some variations for the "automatic-moves-of-cards-to-foundations" prune (also see Danny A. Jones' message about it with some pseudocode). This prompted me to phrase a specification of sorts for commonly agreed upon representation of a solution.

Well, back to the issue at hand, here are some results from the solvers:

If you want a mathematical analysis of the average solution length upon all the set of possible deals, then I'm not aware of any, and I'm not sure I have the mathematical skills to do that.

Best regards,

— Shlomi Fish

share|improve this answer

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.