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:
-
25,367 deals were successfully solved.
-
6,600 deals are provably unsolvable.
-
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.
