Hi all,
I'm sending a better version of this report for posterity.
I've written a report about attempting to solve the 2-freecell-based Windows Freecell deals
using Freecell Solver here:
http://fc-solve.blogspot.com/2010/07/solvability-statistics-of-two-freecell.html
As Michael Keller (of Freecell FAQ / Solitaire Laboratory Fame) told me in
a private E-mail, I didn't quote the right part of the Freecell FAQ, and Danny
A. Jones's solver had been more conclusive on more deals than mine. Quoting
from the E-mail, out of the deals I reported as intractable:
<<<
In 2005, Danny A. Jones ran the first 50,000 deals for standard FreeCell with two freecells.
Out of the first 32,000 deals, his solver found 25,381 solvable 2-fc deals (reported in the
FAQ section "How often can I win?"), with 6,608 impossible and only 11 intractable.
See the attached file.
Of the 33 you have listed, he [= Danny A. Jones] reported:
8 impossible (891, 7214, 14445, 15957, 16462, 17184, 19678, 27799),
11 intractable (982, 3129, 11266, 12038, 12064, 14790, 15804, 20792, 21779, 26124,
29577),
14 solved (5435, 6090, 7728, 9034, 13659, 13705, 14262, 16322, 17684, 17760, 17880,
18446, 19671, 28188)
>>>
I took determining the solvability of the other deals that my solver had
determined as intractable (including those that Jones's solver did) as a
challenge. I eventually was aided by Amadiro (an Internet
friend of mine (who is BCCed to this message)), and he has given me access to
two of his university's (= the University of Oslo -
http://www.uio.no/english/ )
high-performance-machines - the first one with 64 GB of RAM and more recently
one with 128 GB of RAM. This allowed my solvers to scale to large
counts of graph positions (~ 1.6 milliard positions) before either crashing
from lack of memory (thus declaring the initial position intractable), or
better yet finding a solution or proving it to be unsolvable (barring bugs in
the code and other issues).
This is the final report of solving 2-Freecell deals using the "DBM" based
Freecell Solver. This does not include the elusive deal # 982, which is
intractable both by Danny A. Jones' solver and by ours (and which we hope that
the Fully-connected-components (FCC)-based solver would be able to shed light
on after some necessary modifications).
It was generated using a Ruby script using the data provided by Amadiro
using one of his university's high-performance machines. So thanks are extended
to him and to his university. I'll upload everything to the Freecell Solver
homepage soon.
Regards,
Shlomi Fish
3129: Impossible (DAJ: Intractable) ; Reached: ~16700000/16736777 \
Time: 461.755650997162
5435: Solved (DAJ: Solved) ; Reached: ~317200000/402953588 \
Time: 18934.7835159302
6090: Solved (DAJ: Solved) ; Reached: ~159100000/199278081 \
Time: 7538.81079888344
7728: Solved (DAJ: Solved) ; Reached: ~581100000/709981356 \
Time: 29172.0320699215
9034: Solved (DAJ: Solved) ; Reached: ~382300000/450245763 \
Time: 21436.9379889965
11266: Impossible (DAJ: Intractable) ; Reached: ~167200000/167225796 \
Time: 6174.17578792572
12038: Impossible (DAJ: Intractable) ; Reached: ~12000000/12019785 \
Time: 293.612964868546
12064: Impossible (DAJ: Intractable) ; Reached: ~11600000/11617536 \
Time: 325.979027032852
13705: Solved (DAJ: Solved) ; Reached: ~6400000/7254365 \
Time: 153.31712603569
14790: Impossible (DAJ: Intractable) ; Reached: ~84600000/84606316 \
Time: 2914.06726980209
15804: Impossible (DAJ: Intractable) ; Reached: ~17500000/17511302 \
Time: 480.840923070908
17760: Intractable (DAJ: Solved) ; Reached: ~1468200000/1671598732 \
Time: 97809.3720080853
17880: Intractable (DAJ: Solved) ; Reached: ~1278800000/1616737805 \
Time: 79754.6362040043
18446: Solved (DAJ: Solved) ; Reached: ~70800000/99037155 \
Time: 2694.79851603508
19671: Solved (DAJ: Solved) ; Reached: ~505700000/547458213 \
Time: 29875.1219639778
20792: Impossible (DAJ: Intractable) ; Reached: ~30700000/30718221 \
Time: 861.529717922211
21779: Impossible (DAJ: Intractable) ; Reached: ~14200000/14215839 \
Time: 405.994553089142
26124: Impossible (DAJ: Intractable) ; Reached: ~13400000/13402138 \
Time: 341.230257034302
28188: Solved (DAJ: Solved) ; Reached: ~45400000/62734089 \
Time: 2745.98109912872
29577: Impossible (DAJ: Intractable) ; Reached: ~29400000/29400313 \
Time: 794.414890050888
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Escape from GNU Autohell - http://www.shlomifish.org/open-source/anti/autohell/
Whitespace in Python is not a problem: just lay out all the whitespace first,
then add the code around it.
— sizz on Freenode's #perl
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Sat Feb 11 2012 - 11:53:12 IST