Two Freecell Solvability Report for the First 400,000 Deals

With some help from some people on the fc-solve-discuss list and off the list (namely Amadiro from the University of Oslo and someone else that I met on IRC , I ran my solvers on the first 400,000 Windows Freecell deals with only two available freecells to see how many of them can be solved.

Here is the report:

Start Index	End Index	Solved	Impossible	Intractable
1	32,000	25,381	6,619	0
32,001	50,000	14,302	3,698	0
50,001	100,000	39,775	10,225	0
100,001	400,000	238,415	61,584	1 (No. 384243)
Total		317,873	82,126	1

So about 79.47% of the deals can be solved and the rest are impossible. The only intractable deal that none of my solvers could yield a verdict for is No. 384,243, and it spans a very large number of states:

• The dbm_fc_solver got into Reached 12,821,000,000 ; States-in-collection: 13,620,999,440 before it failed to produce more results due to a limitation of the hardware where it was deployed on.

• The depth_dbm_fc_solver yielded this:

  Reached 13,763,700,000 ; States-in-collection: 16,226,294,490 ; Time: 1345126456.520408 Queue Stats: inserted=16,226,294,490 items_in_queue=2,462,594,490 extracted=13,763,700,000

  with a curr_depth of 38. However, that solver may have some yet undiscovered bugs.

So what's next? I’d like to investigate some ways to scale to a larger number of states, perhaps by creating a distributed solver. A Google search for distributed breadth first search yields some results:

I hope you enjoy the statistics for the time being.

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.