average number of moves needed to complete a game of FreeCell
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)
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:
Danny A. Jones solvers (one of them fast and somewhat sub-optimal, and one of them slow being run on the first 1,500 deals).
Results from my sub-optimal (but open-source) solver
Close to optimal solutions for the first 1,000,000 deals on freecellgamesolutions.com - but with a very user-unfriendly interface that requires enabling JavaScript, filling in Captchas and other sorts of nastiness.
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