Report: Solving the Remaining Freecell Pro 4 Freecells Intractable Deals
Note to Freecell Solver’s Users
Shlomi Fish - the core developer of Freecell Solver, and the webmaster of this website - has been experiencing reliability problems with incoming and outgoing E-mail (such as legitimate messages being dropped or classified as spam). They also affect his GMail-dot-com account.
Therefore, one should preferably contact him using other electronic means.
Table of Contents
Introduction
Publishing Date: 21 November 2016.
Theodore Pringle had posted an announcement to the "fc-solve-discuss" group, where he said that he ran a Freecell solver over all the deals in the 8 milliard (1 to 8,589,934,591) Freecell Pro deals range which are based on the original Microsoft FreeCell dealing. He ended up discovering that there are 102,032 impossible deals and 46 intractable deals. Further analysis reduced the number of intractable deals down to 9 - see the updated list.
I (= Shlomi Fish) set out to determine the solvability of these intractable deals while using Freecell Solver's depth_dbm_fc_solver, which is a solver which occupies relatively little RAM, and aims to completely scan all positions in a board and conclusively determine whether it is solvable or not. That solver was ran on an Amazon Web Services (“AWS”) EC2 node with 256 GB of RAM. (Thanks to Jonathan Ringstad for the suggestion to use AWS.)
Conclusions
Deals 219837216, 1252215044, 2255988055, 2901685480, 2902413565, 4260084873, 6687921694, and 7489392343 were shown to be impossible by the solver. Deal 6825625742 ran out of hard disk space (we were given only 8 GB of disk space by default, which turned out to not be enough), and appears to be impossible as well, but not yet provably so.
Some Reflections
This space will be filled with the contemporary statistics of the total number and percentage of impossible and solvable deals out of the 8.5 milliard deals.
Otherwise note that one surprising fact is that solving 4-freecells deals was much easier for us to do programatically than solving the same 2-freecells deals. An earlier report about their statistics, ran into more difficulties solving the first 400,000 2-freecells deals, which is a deals’ space smaller by over 4 orders of magnitude. Perhaps this can be explained by the fact that many more deals are winnable using 4 freecells.
Charts
Queue Items Per Iterations for Each of the Deals
Note: the depth_dbm_fc_solver uses a variation on breadth-first search where we keep a queue of items to check and check an iterations count of states. The x-axis - "Iterations" roughly corresponds to time while the y-axis, corresponds to the number of states in the queue.
Iterations Summary Table
| Deal No. | Iterations Reached |
|---|---|
| 219,837,216 | 977,634,853 |
| 1,252,215,044 | 358,506,418 |
| 2,255,988,055 | 566,936,438 |
| 2,901,685,480 | 330,747,308 |
| 2,902,413,565 | 348,126,072 |
| 4,260,084,873 | 1,144,307,654 |
| 6,687,921,694 | 354,953,970 |
| 6,825,625,742 | 3,915,800,000 |
| 7,489,392,343 | 507,133,501 |
Deal 219,837,216
Deal 1,252,215,044
Deal 2,255,988,055
Deal 2,901,685,480
Deal 2,902,413,565
Deal 4,260,084,873
Deal 6,687,921,694
Deal 6,825,625,742
Deal 7,489,392,343
Links and References
