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).
-------------------------------------
Here's the report followed by future directions:
[report]
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:* 25367.
"Provably" 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 OOM 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.
[/report]
Future directions:
------------------
I'd like to work on the
http://fc-solve.berlios.de/to-do.html#orig_calc_states which should reduce
memory consumption considerably, especially on 64-bit architectures. I'd also
like to see about using an on-disk storage to store the states / positions
such as Tokyo Cabinet (
http://1978th.net/tokyocabinet/ ). That or I can try
adding a bigger swap partition.
Note:
-----
I should note that hogging my laptop's resources with solving Freecell
reminded me of anexcerpt from the book "The Restaurant at the End of the
Universe" where the computer is jammed trying to make some tea.
Best regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
"The Human Hacking Field Guide" - http://shlom.in/hhfg
God considered inflicting XSLT as the tenth plague of Egypt, but then
decided against it because he thought it would be too evil.
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Sun Jul 11 2010 - 00:00:36 IDT