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.