Sunday, September 2, 2012

Two Freecell Solvability Report for the First 400,000 Deals

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.

9 comments:

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. This comment has been removed by a blog administrator.

    ReplyDelete
  3. This comment has been removed by a blog administrator.

    ReplyDelete
  4. I found 384,243 to be IMPOSSIBLE with 2 freecells.

    ReplyDelete
    Replies
    1. Hi Alex!

      Sorry for the late reply, but - how did you conclude that? Which solver did you use and with which resources?

      Delete
    2. This comment has been removed by the author.

      Delete
    3. Sorry 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):
      13 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.

      Delete
    4. I had to delete two comments, because one comment had a typo, and the other comment was misplaced and had the same typo.

      Delete
  5. This comment has been removed by the author.

    ReplyDelete