Freecell Solver

This is Freecell Solver - a program that automatically solves layouts of Freecell and similar variants of Card Solitaire such as Eight Off, Forecell and Seahaven Towers, as well as Simple Simon boards. Freecell Solver is free and open source software freely available under the MIT/X11 License. It is written in ANSI C and requires a C compiler to be built. Nevertheless, binaries for Microsoft Windows 32-bit are available. You won't find a casino that offers Freecell but you can apply the skills here to card games they do offer such as poker and blackjack.

Included with the archive is source code for programs that can automatically feed it with the boards of several popular Solitaire Implementations.

Freecell Solver can also be built as a library for use within your own Solitaire implementations. A more detailed list of features can be found in the Features List.

News

15-Jan-2012: Freecell Solver 3.10.0 was Released

Freecell Solver version 3.10.0 has been released. It is available in the form of a source tarball from the download page.

This release fixes two bugs - one with the --max-iters affecting only the last instance, and one with reading foundations with 0, and implements many small optimisations and cleanups. It also adds some experimental code with the so-called delta-states, where states are compactly encoded based on the original state. This functionality is not available in the main solver yet, but it powers the experimental on-disk-key/value-databases-based solver, which end up not scaling very well during testing.

Enjoy!

See comments and comment on this.

03-Jul-2011: Freecell Solver 3.8.0 was Released

Freecell Solver version 3.8.0 has been released. It is available in the form of a source tarball from the download page.

This release fixes some crashes using --trim-max-stored-states, adds a more meaningful man page instead of the token one that was previously present, adds scripts/parallel-range-solver-total to solve a range of deals in parallel by splitting them into chunks, and many smaller improvements and fixes.

We also forgot to mention the 3.6.0 release, which fixed the installation of fcs_dllexport.h, added the --tracemem compile time option, added a bug fix for incrementally increasing the iterations/stored-states limits, added a built-in version of kazlib's balanced binary search tree as a possible back-end for storage, and had some other improvements.

Enjoy!

See comments and comment on this.

31-Mar-2011: Freecell Solver™ Goes Webscale

1 April, 2011, Tel Aviv, Israel: Freecell Solver Enterprises™, Inc., on behalf of the Freecell Solver™ development team, is glad to announce the upcoming availability of the Webscale™ Edition of Freecell Solver™, the solver for various types of Patience games.

Freecell Solver™, has until now made use of a compile-time choice of primitive, in-memory, data-strctures such as hash tables or self-balancing binary trees, but now we decided that it's time to move on to something more in the spirit of 2010s. Since SQL databases have already become passé, we decided to skip directly to the NoSQL trend of databases (also known as "Oh no! No SQL!") and to write alternative backends for Freecell Solver™ for distributed NoSQL stores such as Cassandra, MongoDB, or CouchDB.

Freecell Solver Enterprises™ is certain that using these modern, high-performance, and highly distributed stores will increase Freecell Solver™'s webscalability, and allow it to process a larger amount of stored positions than it could at the moment at a far greater speed and make Freecell Solver™ be ready for the cloud. As our CTO, Shlomi Fish, says “If you're not excited about it now, you should be.”

Expect the upcoming availability of Freecell Solver™ Webscale™ Edition from the homepage of Freecell Solver™.

See comments and comment on this.

05-Dec-2010: Freecell Solver 3.4.0 was Released

Freecell Solver version 3.4.0 has been released. It is available in the form of a source tarball from the download page.

In this release, we've added the --set-pruning flag to turn on the Horne's play prune, which improves performance. There are two new presets - -l enlightened-ostrich (or -l eo for short), which makes use of --set-pruning and is the fastest preset yet, and -l maliciously-obscure (-l mo) which is slow but generates especially short solutions.

We added a compile-time option to use RCS-like states storage which conserves a lot of RAM and allowed Freecell Solver to scale to over 200 million positions on an x86-64 machine with 64 GB of RAM (which was utilised for that courtesy of Amadiro's university). There are many other major and minor speed and memory optimisations in this release.

The --ms and -M flags were added to the make_pysol_freecell_board.py program, to generate Microsoft deals even for numbers higher than 32,000, which are different in PySol and PySolFC. Furthermore, the CMake configuration was updated to use "lib${LIB_SUFFIX}", so it can be built on some 64-bit systems.

Finally, there's an experimental --trim-max-stored-states which currently may crash the solver, but we decided to release it despite this fact.

All of these changes prove to be a huge step forward for Freecell Solver making this release its best release yet.

See comments and comment on this.

14-Jul-2010: Freecell Solver 3.2.0 was Released

Freecell Solver version 3.2.0 has been released. It is available in the form of a source tarball from the download page. We hope to release a Windows binary soon.

This release implements the --depth-tests-order flag that allows varying the tests' order based on the depth which allows for interesting (and faster) searches. Several new presets : -l the-iglu-cabal , -l foss-nessy and -l tea-for-two have been added , the latter optimised for two freecell deals. There are also several bug-fixes, optimisations and code cleanups.

See comments and comment on this.

13-Jul-2010: Solvability Statistics of Two Freecell Games

While the default Windows implementation of Freecell only supports playing Freecell with four initial freecells, it can be played with any number of them. In order to make the game more challenging, some people are playing it with a fewer number of freecells.

As of today, the Freecell FAQ says that "With two freecells, there are at least 24,161 solvable deals [in the Microsoft 32,000 deals].". However, at the course of researching those layouts using Freecell Solver (after constructing a solver configuration optimised for solving two-freecell deals), we have found out that more deals can be provably solved.

Below one can find the report about the solvability of 2-freecell deals. The executive summary is that:

  1. 25,367 deals were successfully solved.
  2. 6,600 deals are provably unsolvable.
  3. The other 33 deals are "intractable" - meaning my computer ran out of resources trying to solve them (I limited the range of iterations to 8,200,000, but some of them were killed by the "out-of-memory" daemon earlier).

Solvable

  • By using the "tea-for-two" meta-moves preset: 25,143.

  • By using -to 01ABCDE : 172.

  • By using -l foss-nessy : 38.

  • By using the extended range (8,200,000 iterations) -to 01ABCDE scan: grep -l '^This game is solv' *.sol | wc -l yields: 14.

  • Total: 25,367.

Definitely unsolvable

  • Fully traversed in the atomic moves preset: 6,513.

  • Found using grep -l '^I could not solve' *.sol | xargs grep -h '^Total number of states checked' | grep 1200000 | wc -l.

  • Fully traversed in the extended-range atomic moves preset: 87.

  • Found using grep -l '^I could not solve' *.sol | xargs grep -h '^Total number of states checked' | grep -v 8200000 | wc -l.

  • Total: 6,600.

Intractable

  • After the atomic scan: 172.

  • Found using grep -l '^I could not solve' *.sol | xargs grep -l '^Total number of states checked is 1200000\.' | wc -l

  • After the foss-nessy scan: 134.

  • After the 8,200,000 range atomic scan:

  • Killed by the Out-of-memory Killer: ls | perl -lne 'print if -z' | xargs ls -l | wc -l : 17.

  • Reached the iterations limit:

  • grep -l '^I could not solve' *.sol | xargs grep -l '^Total number of states checked is 8200000\.' | wc -l: 16.

  • Total: 33.

Conclusion and Future Directions

The 33 deals that we could not determine whether they were unsolvable or not are: 891, 982, 3129, 5435, 6090, 7214, 7728, 9034, 11266, 12038, 12064, 13659, 13705, 14262, 14445, 14790, 15804, 15957, 16322, 16462, 17184, 17684, 17760, 17880, 18446, 19671, 19678, 20792, 21779, 26124, 27799, 28188, 29577. We would appreciate any further insights about whether they can be solved or not and one option would be to use Freecell solver to solve them on a 64-bit machine with more memory available than what I have.

In the future, we'd like to work on the "States calculated from the original" feature which should reduce memory consumption considerably, especially on 64-bit architectures. After reading the report of Kevin Atkinson's and Shari Holstege's solver it seems that we can also save space by re-using old positions that have been determined to be dead-ends, so we'd like to explore that. We'd also like to explore using an on-disk storage to store the states / positions such as Tokyo Cabinet. That or we can try adding a bigger swap partition.

See comments and comment on this.

24-May-2010: Freecell Solver 3.0.0 was Released

Freecell Solver version 3.0.0 has been released. It is available in the form of a source tarball from the download page. We hope to release a Windows binary soon.

This release implements the flares API (see the usage document), which allows running several alternative scans and then picking up the one with the shortest solution. It also adds the -l children-playing-ball and -l sentient-pearls presets that optimise on solution length (based on flares).

Also see the post about this release to the fc-solve-discuss mailing list giving some of the motivation for the new major release digit (3.x.y instead of 2.x.y).

See comments and comment on this.

Previous News Items

Links

More Links



Share/Bookmark