6 Sep 2012 shlomif   » (Master)

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.

Syndicated 2012-09-02 09:19:00 from shlomif

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!