There are three solvers provided, (1) The original solver which has previously been provided with FcPro, authored originally by Don Woods, and further developed by Wilson Callan and Adrian Ettlinger, (2) Freecell Solver by Shlomi Fish, and (3) Patsolve by Dr. Tom Holroyd. The following discussion represents some comments and opinions by Adrian Ettlinger on the general subject of Freecell solving software, plus specific information on each of the solvers.
The Woods-Callan-Ettlinger Solver (FcPro original)
Freecell Solver by Shlomi Fish
Patsolve by Dr. Tom Holroyd
General:-
This program is being made available in the hopes of encouraging more research and development in the area of Freecell solving software. This is an endeavor which, in the opinion of the author, is still very much on the cutting edge of puzzle-solving software, and much remains to be accomplished before an "ideal" Freecell solver comes into existence. The bane of the Freecell-solving software developer is the occasional deal which poses a difficult challenge for any software to deliver a verdict as to solvability vs. unsolvability. Such deals when playing with four freecells are very few and far between, there being only a handful discovered in the first 30 million deals under the M/S Freecell dealing algorithm. But when playing with only two or one freecells, such difficult deals are much more common. There has so far been very little research, of which the author is aware, concentrating specifically on the problem of the two or one-freecell game.
We believe that the three solvers now included in this edition of FcPro represent the three "best" solvers which have yet been developed and are being made available publicly. We'd be happy to hear from anyone who might dispute that contention. We are aware of at least one example of Freecell-solver software in development which shows promise of being far superior to any of these three, but it has not been thoroughly tested in the "marketplace", and its author is not presently prepared to place it in the hands of the general public. If there are any other solvers of which the authors would permit their inclusion here, we would be pleased to work toward the addition of any such to FcPro.
The source code for this program, under the terms of the GPL license, will be made available freely to any applicant who will fill out a questionaire, which will be supplied on application to the author by E-mail at aettlinger@worldnet.att.net
A new help file has not been prepared for this version of FcPro. Users who wish to access a general help file for FcPro should copy the help file distributed with the standard version of FcPro. (Available at Mike Keller's website). Supplemental help information is provided here for the two additional solvers.
To the best of our knowledge, from reactions from users of FcPro, the solver finds its most frequent use by players who wish to make occasional spot checks as they are playing a hand to determine whether an intermediate position they have reached is winnable or non-winnable. For this purpose, FcPro includes a "hot key", F7, for invoking the FcPro Solver to state whether the position is winnable or not. We receive occasional reports of false impossibles under this usage. Now, in this edition of FcPro, in addition to the F7 hot key, there have been added F8 and F9, which call, respectively, Solver 2 and Solver 3. As a last resort, we would say that any position which all three solvers agree is non-winnable, certainly is highly likely to be non-winnable.
Special considerations applying to Solver 2 and Solver 3 are covered in the sections on those two solvers below.
The Woods-Callan-Ettlinger Solver (FcPro original)
This solver is the result of the efforts of three people. Its basic solver algorithm was developed originally by Don Woods, as a DOS application. In its time it was by far the most advanced Freecell solver. Its major disadvantage was a tendency to bog down to a very slow pace when it required the generation of more than a few hundred thousand positions in search of a verdict. Consequently, a relatively high percentage of deals would be "Intractable". Also, in its initial form, it did not deliver move-by-move solutions in "standard notation."
The initial integration into FcPro was done by Wilson Callan, who introduced the output in standard notation. Then later, after Adrian Ettlinger had taken over FcPro development, a "double-hashing" system was introduced which greatly reduced the frequency of intractables. Unfortunately, the resulting product has a characteristic of, on very infrequent occasions, delivering a "false impossible" verdict. We have not been able to determine whether this characteristic is inherent in the original Woods design, or was introduced by the later extensive modifications introduced by Callan and Ettlinger.
No further development work on this solver is contemplated by the author. The source code will be made available to anyone who might be interested in investigating it.
Freecell Solver by Shlomi Fish (Solver 2)
Shlomi Fish's solver provided the initial impetus to incorporate more than one solver into FcPro. The version presently incorporated is 2.6.3.
The design of this solver originally emphasized maximizing the rate of generation of solutions, concentrating on positions which can be solved quickly. To this end, there had not been a high priority placed on providing reliable verdicts, and thus this solver had an inherent tendency toward a fairly high percentage of false impossible results. In the current version, which replaces in FcPro the former 2.4.3, there is an option available called "atomic moves", which, so far as current testing has indicated, eliminates false impossible verdicts, unfortunately at a considerable penalty in speed.
An important feature of Freecell Solver is its use of "presets". A preset is a series of arguments passed in the internal command line which specifies the method used by the solver, which includes the pattern by which it searches the move tree and also the sequence with which it tries various kinds of moves when working on any given position. This solver also has a "soft thread" feature which allows it to try a given method for a given number of iterations, then cycle through other methods as specified. This can greatly accelerate the reaching of a verdict and reduces the frequency of intractables.
The dialogue screen for this solver is similar to that for Solver 1, and contains options to limit the time spent on a solution attempt or the number of "iterations". The "Mode" field has a special meaning applicable only to this solver, related to its "preset" feature. If a single character is entered into this field, the user can select 31 different "hard-coded" presets, designated by digits "1" through "5", or upper case alphabetic characters from "A" to "Z". The letter-designated presets are all single-method ones, and the digits "1" through "5" each make use of soft-threading to cycle through a number of methods. These numbered presets were derived by Shlomi Fish using a meta-scan process to optimize the speed of solving the 32,000 deals of the original M/S Freecell. The first two were provided for former version 2.4.3, and do not take advantage of two advanced features of version 2.6.1. Presets 3 through 5 use a new "prelude" mode which speeds up operation by approximately 40%. Presets 4 and 5 make use, in addition, of the "atomic move" option to eliminate the false impossible tendency. Preset 5 is the most advanced, and works, on average, the fastest of the non-false-impossible-prone presets. Preset 3 is much faster, but is prone to false impossible verdicts.
Presets "A" through "Z" are single-line presets, and are, in succession, the lines used in presets 1, 2, 4, and 5 (reaches only through the first line of #5). Presets 1 and 3 are identical except for the addition of the "prelude" option in #3.
For more flexible experimentation with presets, the user may compose his/her own presets and store them in a text file. The name of the file must be of the form fcsprXX.txt or fcsprXXX.txt, where "XX" or "XXX" is the designator used in the mode field to select the file. A sample file fcsprAB.txt is included in the download to illustrate the format of the file. The files which Shlomi provides often include a command line to specify a range solve, which must be removed or commented out. Note that comment lines may be included at the head of the file, if preceded by a "#" character.
Another means is provided for the user to experiment with his/her own presets. If an invalid character (or blank) is specified as the Mode, the software will search for a file named "fcspres.txt", which can contain a user-generated preset. Included in the download are five files "fcspres1.txt" through "fcspres5.txt", and another copy of fcspres5.txt named "fcspres.txt . The first file is the content of the hard-coded preset "1", the second that of preset "2", etc. For further information on presets, see the Shlomi Fish website.
Hot key: The hot key "F8" causes Freecell solver to first look for a solution with preset #3, then with #5. If an "impossible" or "intractable" verdict results from #3, it continues to try #5, to insure against false impossible verdicts.
Patsolve by Dr. Tom Holroyd (Solver 3)
This solver is designed for a purpose more in line with usage in which most FcPro users are interested -- providing a reliable verdict in the shortest possible time on the winnableness of a specific position. Compared to the FcPro solver, it appears on the average to be slower, but so far as has been determined to date, it does not yield false impossible verdicts.
The dialogue screen for this solver is similar to that for Solver 1, and contains options to limit the time spent on a solution attempt or the amount of virtual memory space to be used. A default space limitation of 60mB. will apply if none is specified. The various modes which can be employed are:
Mode S: Generally will provide a solution in the shortest time, without regard to length.
Mode E: An alternate mode for speed -- sometimes will be faster than "S".
Mode F: An second alternate mode for speed -- sometimes will be faster than "S" or "E".
Mode B: For "Best". Generally provides a shorter solution.
Mode A: An alternate mode for a short solution. Sometimes will be shorter than "B".
Mode T: A mode under which the solver keeps searching for the shortest solution it can find.
Will run for as long as "Max. time" or "Max. space" will permit, and show the shortest solution it has been able to find. This mode will generally yield a much shorter solution than any of the other solvers will provide, and is an excellent tool for anyone who is curious to see a solution close to the shortest possible for any given deal.
Mode X: This is a special mode for range solving only. It provides a compound strategy
aimed at minimizing intractables.
More information about Patsolve can be obtained by downloading the software and supporting documentation from Dr. Tom's website
Hot key: The hot key "F9" invokes Patsolve, first under mode "S", and then, if intractable, under mode "E".