With some help from some people on the fcsolvediscuss 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 ; Statesincollection: 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 ; Statesincollection: 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.
This comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteI found 384,243 to be IMPOSSIBLE with 2 freecells.
ReplyDeleteHi Alex!
DeleteSorry for the late reply, but  how did you conclude that? Which solver did you use and with which resources?