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|
|100,001||400,000||238,415||61,584||1 (No. 384243)|
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,440before 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.