The Freecell Solver Frequently Asked Questions (F.A.Q.) List

Table of contents

The Questions

What is Freecell Solver? What is a solver for Freecell in general?

Freecell (or “FreeCell”) is a single-player card game (which are generally known as “Patience” or “Solitaire”), where all the cards are played face-up at startup and where no talon is used. There is more information about it in the FreeCell FAQ which is maintained by Michael Keller.

An automated solver for Freecell is a computer program that attempts to solve layouts of Freecell: either initial deals, or often also mid-play states of the game, and emit a solution to completion, or conclude that the layout could not be solved by it. Freecell Solver is one such program, and it is open source under the permissive and common MIT/Expat licence, provided free-of-charge for download or use online, and sports a large number of features. (See its features list.)

One should note that Freecell Solver can solve several other variants of solitaire that are similar enough to Freecell for us to provide support for, but Freecell appears to be the most popular variant out of them, and the name is kept for historical reasons.

What is “Microsoft deal #NNN”? What is “MS deal #NNN”? What are the Microsoft Freecell deals?

Microsoft shipped several implementations of Freecell for its Windows operating systems called “Microsoft FreeCell” which contributed to popularising the game. They dealt cards with numbered deals using a shuffling algorithm based on inputting the number of the deal into the Microsoft C Run time library pseudorandom number generator. The algorithm for dealing cards was made available by Jim Horne, a Microsoft software developer who implemented Microsoft FreeCell.

While the original MS FreeCell only dealt deals in the range 1 to 32,000, these deals can be extended up to a 31-bit number and were later extended by Freecell Pro to 33-bits dealing.

The Microsoft deals are considered canonical among Freecell researchers in their studies of the game.

For more information, see:

  1. range_solvers_gen_ms_boards.h and gen_ms_boards__rand.h - from the Freecell Solver's source - implementations of the dealing algorithm in optimised C under the MIT/Expat licence.

  2. “Deal cards for FreeCell” on Rosetta Code - implementations in many programming languages, but under a problematic licence.

  3. The impossible 4-freecells and 5-freecells deals in Freecell Pro’s Range of Deals.

  4. The minimal number of freecells needed to win for each deal in the original Microsoft FreeCell 32,000 deals.

Can Freecell Solver solve all the Freecell layouts?

First of all, despite popular belief, a small percentage of the standard 8 columns+4 freecells Freecell layouts are impossible to solve, and even more deals are impossible with fewer than 4 freecells available. What Freecell Solver will do in this case is traverse the entire game graph (given enough time and computer memory) and then report “I could not solve this game.”

That put aside, some deals may be inaccurately reported as unsolvable with the default heuristic. See the link for more information and for a solution.

Part of the confusion may have stemmed from the phrasing in the Microsoft Freecell help file which read “It is believed (though not proven) that every [Freecell] game is winnable.” which referred only to the 32,000 built-in deals and proved to be false as well (because deal #11,982 turned out to be impossible).

Some of the most famous impossible deals are:

  1. Microsoft Deal #11,982.

  2. Recent versions of Microsoft Freecell contain two impossible deals numbered -1 and -2 as a joke.

  3. Theodore Pringle has constructed a deal which is impossible to win with 8 freecells or fewer.

I think I found a wrong move in the solution? What can I do?

While it is not unthinkable that Freecell Solver will have a bug and will make a wrong move, it is extremely unlikely that that is the case. Some people have reported that several multi-card moves are impossible, but as I demonstrated to them, they were in fact possible.

One can find the maximal number of cards that can be moved as a sequence in Freecell using the formula max_cards = (1 + num_vacant_freecells) * (2 ^ num_vacant_columns) (where “*” is multiplication and “^” is exponentiation.). One can also try using expand-solitaire-multi-cards-moves from the Games-Solitaire-Verify CPAN distribution (by the same author of Freecell Solver), in order to filter solutions and produce ones with multi-card moves expanded into many single-card moves. If you are on Microsoft Windows, you can install Strawberry Perl and run it.

Note that the web-based solver also has an option to expand such moves and one can use it in most modern JavaScript-enabled browsers without having to install any additional software on your computer.

I think I found an abuse of Freecell Solver. What should I do?

We received a report or two about various people or companies distributing Freecell Solver along with their products, and the answer is that it is: 1. Likely legal, 2. We don't mind, and 3. We encourage commercial and/or proprietary use of the code or binaries.

Freecell Solver used to be distributed under the Public Domain, but was relicensed to the permissive MIT/Expat licence due to the problematic and not globally accepted nature of the Public Domain, especially in software. (See the page maintained by Rick Moen about it.) As far as we know (and this is not legal advice), the main legal and practical difference between the public domain and the Expat licence, is that one should keep attributing the original copyright holders as rightful holders (while the licence of derivative works may be changed into any other). As far as we are concerned, this is not something we want to enforce, but we still recommend to follow this, to stay on the safe side of the law.

So unless someone sues us for damages for a problem caused by the program or library (which violates the no warranty paragraph of the licence) everything should be fine and the “abuse” of the program is acceptable.

What are the uses of a solver for Patience/Solitaire card games, such as Freecell Solver?

Freecell Solver is unlikely to help in curing cancer, or solve world hunger, but it still has some uses. One use is determining whether an initial layout of a game, or a layout in mid-play is solvable or not so a human player can know whether he needs to return to an earlier position. The default configuration of Freecell solver may still report a small number of solvable positions as unsolved, but that can be mitigated by passing some command-line flags.

Another use of a Solitaire solver is to find solutions for difficult deals, or attempt to find shorter solutions. Yet another use is to collect statistics from a large number of random deals (say, the Microsoft Windows Freecell deals or PySolFC’s deals), which is part of what Freecell researchers do.

Freecell 3D, a Freecell implementation for Windows, has also introduced a “Race against the computer” mode of Freecell, which is an interesting challenge.

Finally, we have more recently started to investigate some “human/computer collaboration”-based Freecell solving, where a human aided by a Solitaire suite with a good solver integration can attempt to solve some difficult deals (for both a human and a computerised solver), by pruning dead ends, and by finding whether reached states are solvable. This provides a combined solving technique, that is greater than the sum of both parts.

Does anyone care about this project? I think no one cares about it except you.

The short answer is that: yes, some people care. As of November 2016, I received over 900 E-mails about the project to my private inbox and my fc-solve-discuss group’s folder also contains over 900 E-mails. Furthermore, some people to whom I mentioned my solver in real life, expressed interest in it, in part due to the fact that in Israel, where I live, many people played it on the Israeli military’s computers during their draft/etc. service. An internal survey conducted in 2004 found that it was the preferable game of 29% of the surveyed soldiers - thanks to the Hebrew wikipedia page about Freecell for the link. One should note that Israel has instated a draft for girls as well as boys, so some of the people who were impressed were attractive females.

I have written a section in a three-part essay titled “How to achieve world domination” about that and niche software in general.

Freecell may have been declining in popularity lately, but I expect interest in it to continue for a while.

I started writing a solver for Freecell (of my own) but it is too slow. What can I do?

The problem with many naïve Freecell solving programs is that, while they can succeed in solving many Freecell deals, they may fail spectacularly in the general case. Furthermore, Generalised Freecell (where there is an arbitrary number of ranks) was shown to be an NP-complete problem and as a result, it is likely that no efficient solution for solving that in the general case can be found (but it is possible that some good heuristics can be devised).

You can try inspecting the code of Freecell Solver or one of the other solvers for insights, but note that their code (and especially Freecell Solver’s) may be somewhat complex and hard to understand for people with relatively little experience. You can also pursue some of the Freecell Solver documentation as well as the archives of the fc-solve-discuss mailing list for some insights and ideas.

Here are some general tips:

  • Make sure that the positions in the graph of the game are represented as a single segment of memory (normally a C struct) and can be compared for equivalence easily (using memcmp() or a similar function).

  • Use an efficient data structure to hold the states in the collection such as a hash table or a self-balancing binary search tree. There are libraries implementing them for most popular languages.

  • Often randomising the solution (see Freecell Solver's Random-DFS scan which was inspired by a different solver called “Freecell Tool”) can help a lot.

  • Freecell Solver makes heavy use of switch tasking: having several different searches operate on the same board, until the first search yields a solution. This normally yields a solution quicker than a singular scan.

  • Consider implementing moves as meta-moves: sequences of several single-card and/or sequence moves that implement a certain ends. This can yield a solution faster than using single-card moves (also known as atomic moves).

Finally, note that we could use a helping hand with Freecell Solver, and the authors of other open-source solvers may be happy for help as well, so if you want to help to improve something more mature, then contact us.

May I integrate Freecell Solver into my program? If so - how?

Yes, you can, as long as you accept the MIT/Expat licence. We also would appreciate an acknowledgement and a link to the Freecell Solver home page, in the About Dialogue, and in other places.

Now regarding how to integrate: please either use the freecell_solver_user_* API, or alternatively parse the output of fc-solve with the -p -t -sam -sel flags. The freecell_solver_user_* API is not documented at the moment, but should be self-explanatory, and there are some examples of using it in the various solvers in the distribution. One useful way to configure a solver handle is to use “fcs_cl.h” which provides an API based on the Freecell Solver command-line and is more convenient than issuing multiple lower-level API calls.

You can opt to put the solver on a separate thread, on a separate process, or alternatively limit the iterations and increase it constantly, in a pre-emptive multi-tasking fashion.

Good luck and please let us know if you run into any trouble, or, alternatively, if you are successful.

The Solutions I got are too long. What can I do?

You can try using a flares-based preset such as “video-editing” and optionally add --flares-choice fcpro and -fif 10, where 10 can be replaced by a larger (or smaller) number. So the complete command would be:

pi-make-microsoft-freecell-board -t 24 | fc-solve -l ve --flares-choice fcpro -fif 10 -

If this still does not work to your satisfaction, you can try constructing a specialised heuristic from the many command line options of Freecell Solver that will yield something. There are some examples for those in the individual flares and soft threads under the “Presets/presets” directory.

Which programming language (or programming languages) is Freecell Solver written in?

The core Freecell Solver source is written in the GNU11 version of the C11 standard of the C programming language (-std=gnu11), which is supported by the GCC and clang compilers and compatible compilers. This includes the libfreecell-solver library, most of the user-facing executables using it, and some other related code. Aside from that, there's quite a lot of support code for testing (a.k.a: “quality-assurance”), automation, building, results analysis, and other tasks, written in Perl 5, CMake, Python 3.x, the GNU Bash shell, Ruby, and possibly some other languages. The git repository also contains code and markup in other languages such as JavaScript.

Here are the estimated lines-of-codes-per-language statistics of running SLOCCount by David Wheeler on the “fc-solve/source” sub-directory of the git repository (as of 9 December 2016)

Totals grouped by language (dominant language first):
ansic:        27360 (68.34%)
perl:         10165 (25.39%)
python:        1262 (3.15%)
sh:             970 (2.42%)
cpp:            277 (0.69%)

Why is Freecell Solver written in C? Why not in another language?

Part of the reason why Freecell Solver is written in C, is because the first released version (version 0.2) was written in C, and it continued to be maintained in this language. Other reasons are:

  • C is fast and memory efficient.

  • C is portable.

  • The bit-handling operators of C are utilised extensively in the Freecell Solver source.

  • As opposed to C++, C is easier to get right, is more of a “no-nonsense language”, is less hyped, and does not encourage crazy or pointless practices. Also see what I’ve written about it previously.

Here are a few other links I collected which speak against C++:

Nevertheless, I cannot guarantee that Freecell Solver’s code will remain written in C forever, and that I won’t gradually convert it to C++ or a different language. My main issue with using C++ right now is that I (rationally) fear it will give me too much rope to hang myself, and be too tempting to go wild with advanced features, as well as potentially bring too many unexpected and hard-to-debug problems.

One final note is that the Freecell Solver C source has been compiled to browser-side-compatible JavaScript using Emscripten, so it can be used inside a JavaScript-compatible browser. This was done for making it easy to be tested and used, at the (usually not show-stopping) trade-off of being slower than compiled-to-native-binary-code. Nevertheless, the C code is still maintained directly, and the generated JavaScript code is not idiomatic JavaScript.

I found a solvable deal that Freecell Solver reports as unsolvable - should I report it to you?

The default Freecell Solver heuristic may have a small number of deals that are reported as unsolvable despite being solvable. However, you can use scans based on atomic moves to rectify that. See fc-solve --help-configs and the USAGE.html file for more information.

Have you completed/finished the work on Freecell Solver? Is it done yet?

I am getting asked that a lot, and I find it a strange notion. It is similar to asking if the KDE developers are done working on KDE, or if the developers of the Linux kernel have completed the Linux kernel, or if the Firefox browser is done. Freecell Solver is a fairly large and complex project and there is still a lot of room for improvement, and while I sometimes take a break from working on it, it does not mean I planned to have permanently stopped.

Sometimes, I complete one task and call it a day, but it does not mean that I plan to ever stop working on it. Perhaps when I tell people that “I’m working on Freecell Solver” they assume that this work is temporary, but it has been developed since the year 2000, while taking some breaks.

All that put aside, one should not conclude that Freecell Solver is an immature project or is unusable, just like KDE, the Linux kernel, and Firefox are not immature or unusable. Freecell Solver is not perfect (and will probably never be) but it is still usable in its current state.

Also see an earlier blog post about “Finished Projects, Maintained Projects and Those that are Up For Adoption”.

“‘Freecell Solver’? Hasn’t Freecell been solved yet?”

This question shows a basic misunderstanding of what Freecell is, and the purpose of a solver for it. Just to clarify the matters, Freecell is a single-player card game, with some rules about what constitutes a legal move, and since there are 52 cards (Ace-to-King in the four suits), which are usually placed in 8 columns (although a different number is possible), there are about 1.75 × 1064 distinct initial layout (according to the Wikipedia page), and many more if we consider mid-play layouts.

The primary purpose of solvers such as this one is to attempt to solve any arbitrary layouts, while optionally giving the moves to completion. Note that due to the nature of the game, it may be impossible and/or time consuming for some layouts, but hopefully the chance of this risk can be minimised with the more advanced searches.

Is Freecell Solver written in Perl?

For some reason, some people assume that I (= Shlomi Fish) wrote Freecell Solver in Perl. That may stem from the fact that I've written a lot of Perl 5 code (see my “Perl Résumé” over at perlresume.org), but it is not, in essence, the case for Freecell Solver.

In fact, the core C libfreecell-solver library, some of the command line executables, and some other code, is written in the GNU11 version of the C programming language, and does not require the Perl runtime to be used.

It is true that the preliminary version of Freecell Solver (that was written before the first “0.2” release and that can be found in the “nostalgia” directory of the version control system) was written in Perl, but that was quickly rewritten in C. The original reason for the rewrite was that the Perl version ran too slowly, but part of the problem was the fact that it was poorly coded, rather than Perl’s fault.

I've kept the code written in C after version 0.2 which was written in C, and have preferred to keep it in C, for performance reasons. Porting a different solver I wrote - for Black Hole Solitaire - from its initial Perl version to C - made it roughly 24 times faster and I naturally find a 24 factor performance decrease unacceptable.

How does Freecell Solver solve Freecell? Which algorithm does it use?

The exact algorithm used by “fc-solve” can be configured using the various command line arguments it accepts which are documented in the README and USAGE files. Furthermore, the “-l” flag can load some predefined configurations, which are essentially a sequence of command line arguments loaded from a file.

Some of the highlights of the methods supported by Freecell Solver are:

  1. Switch-tasking in which different scans are interrupted, swapped with another scan, and then resumed.

  2. Randomised and/or prioritised depth-first-search (DFS) scans, and Best-First-Search (BeFS) scans.

  3. Different types of moves, with configurable order and grouping.

  4. One can instantiate different instances of the solver, that will each solve different deals in different threads or processes.

How does Freecell Solver reads the cards and board layout? What kind of input does it accept?

The API of the solver accepts a textual representation in a certain well-formed format of the starting layout of the game's board (which may be a mid-play layout), parses it, and starts the processing from it. This allows Freecell Solver to accept any arbitrary layout, not just the initial layouts of Microsoft Freecell or a different Solitaire implementation.

We did not bother with graphically extracting the cards, because it is harder to do, and would have limited the utility and generality of the solver. Nevertheless, the solver can be input with a text layout based on that which seems to be the approach taken by the iPhone Freecell Bot demo.

Note that Freecell Solver also ships with some programs that generate the initial deals of some popular Solitaire implementations, and some implementations of Solitaire provide integration with Freecell Solver, that provides it with automated input, and also uses its moves output to display the solution.