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.

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.

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.

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).

Announcing Freecell Solver™ Enterprise Edition

01-April-2010: Freecell Solver Enterprises™, Inc., on behalf of the Freecell Solver™ development team, is glad to announce the upcoming availability of Freecell Solver™ Enterprise Edition. In its Enterprise Edition, Freecell Solver™ will be enhanced to solve generalised Freecell, in which there can be an arbitrary number of card ranks. Since generalised Freecell is NP-complete. This will allow us to use Freecell Solver™'s ingenious, cutting-edge algorithms to solve the previously hard, provably NP-Complete problems of the Travelling Salesman problem, Subset sum, Sudoku and Enterprise content management.

Since we expect some of our customers to wish to solve NP-complete problems with data sets of an order larger than the standard computer word (32-bit or 64-bit), we are going to start using the "GNU MP Bignum Library" (GMP). As our CTO, Ron Johnson, says By making use of Freecell Solver™ Enterprise Edition's sophisticated algorithms, we expect a cluster of 2,000 32-way high-performance supercomputers to solve a 17,179,869,184 (2 to the power of 34) problem, a short time before the heat death of the universe.

That's not the only change expected in Freecell Solver™ Enterprise Edition. Until now Freecell Solver™ was written in ANSI C and was dependent only on the standard C library. To make it more enterprise ready, we decided to convert to such enterprise-ready languages as C++ and Java, and to utilise such enterprise-ready Cross-Platform Abstraction Libraries such as Boost, Qt, glib, Apache's Portable Runtime (APR), or ACE. Our CTO continues: Phil Greenspun said that “Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.”. Well, now Freecell Solver™ will contain an ad hoc, informally-specified, bug-ridden and slow, but enterprise ready, implementation of half of Common Lisp. This is really very exciting. We don't know yet which of these libraries we are going to use, but we are likely to use more than one based on the enterprise-readiness of their individual components.

Naturally, as the company behind Freecell Solver™ Enterprise Edition, Freecell Solver Enterprises™ does not expect to keep Freecell Solver™'s original permissive licence, the MIT/X11 License, because code which is licensed under it is easy to abuse, misuse, and generally use. Instead, the core Freecell Solver™ Enterprise Edition functionality would be available under the Affero General Public License (AGPL) version 3, while making some extended functionality available only under own own custom, proprietary licence - exclusively for paying customers. We are really excited about this change which will allow use to protect our intellectual property from people and enterprises who will abuse, misuse or generally just use it.

Here is what others say about that:

• Don Knuth: Freecell Solver™ Enterprise Edition really excites me. I didn't think I'll see the day to see an Enterprise-ready NP-complete solver, but Freecell Solver™ EE made it happen. I can't wait to play with it.

• Larry Wall: Freecell Solver™ Enterprise Edition is the epitome of Laziness and Hubris, but unfortunately requires a lot of Patience.

• Bill and Ted: Enterprise Content Management! Yeah!!! Star Trek is Excellent, bro. Excellent!!! So where's Captain Kirk?

• Shlomi Fish (the original creator of Freecell Solver): Eh, what the hell?

As you can see, everybody are united in their opinion that Freecell Solver™ Enterprise Edition is the best thing since Enterprise bread came sliced by and for enterprises.

One can download the Freecell Solver™ Enterprise Edition version 1.0.0 source tarball, and after resolving all the essential dependencies and building it (as documented in the INSTALL file), type ./fc-solve --help-enterprise to get help for the enterprise features.

Freecell Solver 2.42.0 was Released

Freecell Solver version 2.42.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 finally adds a -o/--output flag to the "fc-solve" executable, and installs the newly created executables ( freecell-solver-fc-pro-range-solve , freecell-solver-multi-thread-solve , freecell-solver-range-parallel-solve , etc.) by default. There are also several bug-fixes and one can now input "const char *" instead of "char *" (with a compile-time flag that typedefs the strings to their old interface).

There has been some internals cleanups and optimisations. Finally, the file pqueue.h was converted to the MIT/X11 license, with permission of its originator, Justin Heyes Jones making Freecell Solver fully licensed under MIT/X11.

We hope you have fun with this new release.

Freecell Solver 2.40.0 was Released

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

This release contains a fix to a string overflow with processing the command line arguments, and an optimised command-line preset that can be invoked as -l blue-yonder (or -l by for short) that solves the Microsoft 32,000 deals in under 100 seconds on a Pentium 4 2.4GHz machine. It also contains some more minor changes: there is now a Scan: header with the name of the current soft thread, when debugging under -s -i, an off-by-1 iterations count was fixed and the iteration handling callback is now applied globally to all the instances. Finally, make_pysol_freecell_board.py has support for generating PySol's and PySolFC's "Black Hole" Solitaire deals, intended for my newly released Black Hole Solitaire Solver.

Enjoy!