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?
This comment has been removed by the author.
DeleteSorry for the late reply, but I have proof that 384,243 is impossible with 2 freecells. The critical position the computer couldn't solve is after the following moves (384243, two freecells):
Delete13 78 63 52 6a 62 16 46 7b 76
74 16 76 14 16 a1 b1 7a 87 43
47 37 8b 87 57 57 b8 4b 47 46
17 27 21 24 14 28 21 23 23 b3
2b a2 5a 52 8h 68 61 a5 65 81
85 15 4a 4h b4 64 62 42 68 48
Note that in the fourth line, 21 24 14 is the supermove 24.
The only way out in the resulting position that computers couldn't solve is to put up the hearts and/or diamonds to the homecell, but Patsolve proved the resulting positions impossible. I checked alernatives earlier, but again Patsolve proved them impossible.
That proves 384,243 impossible with two freecells.
I had to delete two comments, because one comment had a typo, and the other comment was misplaced and had the same typo.
DeleteThis comment has been removed by the author.
ReplyDelete