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 |
|---|---|---|---|---|
| 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 ; States-in-collection: 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 ; 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.
