Source

fc-solve / fc-solve / site / wml / src / faq.html.wml

Full commit
#include '../template.wml'
#include "xhtml/1.x/std/toc.wml"

<latemp_subject "The Freecell Solver Frequently Asked Questions (F.A.Q.) List" />

<h2* id="toc">Table of contents</h2*>

<toc />

<h2 id="questions">The Questions</h2>

<h3 id="a_move_seems_wrong">I think I found a wrong move in the solution? What can I do?</h3>

<p>
While it is not unthinkable that Freecell Solver will have a bug and will
make a wrong move, it is extremely unlikely that that is the case. Some people
have reported that several multi-card moves are impossible, but as I
demonstrated to them, they were in fact possible.
</p>

<p>
One can find the maximal number of cards that can be moved as a sequence
in Freecell using the formula
<tt>max_cards = (1 + num_vacant_freecells) * (2 ^ num_vacant_columns)</tt>
(where “*” is multiplication and “^” is exponentiation.). One can also try using
<a href="https://metacpan.org/module/expand-solitaire-multi-cards-moves">expand-solitaire-multi-cards-moves</a>
from the <a href="https://metacpan.org/release/Games-Solitaire-Verify">Games-Solitaire-Verify CPAN distribution</a> (by the same author of Freecell Solver),
in order to filter solutions and produce ones with multi-card moves
expanded into many single-card moves. If you are on Microsoft Windows, you can
install <a href="http://dwimperl.com/">DWIM Perl</a> and run it.
</p>

<h3 id="abuse_of_fc_solve">I think I found an abuse of Freecell Solver. What should I do?</h3>

<p>
We received a report or two about various people or companies distributing
Freecell Solver along with their products, and the answer is that it is:
1. Likely legal, 2. We don't mind, and 3. We encourage commercial and/or
proprietary use of the code or binaries.
</p>

<p>
Freecell Solver used to be distributed under the Public Domain, but was
relicensed to the permissive
<a href="http://en.wikipedia.org/wiki/MIT_License">MIT/X11 licence</a> due
to the problematic and not globally accepted nature of the Public Domain,
especially in software. (See
<a href="http://linuxmafia.com/faq/Licensing_and_Law/public-domain.html">the
page maintained by Rick Moen about it</a>.) As far as we know (and this is
not legal advice), the main legal and practical
difference between the public domain and the X11 licence, is that one should
keep attributing the original copyright holders as rightful holders (while
the licence of derivative works may be changed into any other). As far as
we are concerned, this is not something we want to enforce, but we still
recommend to follow this, to stay on the safe side of the law.
</p>

<p>
So unless someone sues us for damages for a problem caused by the program
or library (which violates the no warrany paragraph of the licence) everything
should be fine and the “abuse” of the program is acceptable.
</p>

<h3 id="what_are_the_uses_of_a_solver">What are the uses of a solver for Patience/Solitaire card games, such as Freecell Solver?</h3>

<p>
Freecell Solver is unlikely to help in curing cancer, or solve world hunger,
but it still has some uses. One use is determining whether an initial layout
of a game, or a layout in mid-play is solvable or not so a human player can
know whether he needs to return to an earlier position. The default
configuration of Freecell solver may still report a small number of solvable
positions as unsolved, but that can be mitigated by passing some command-line
flags.
</p>

<p>
Another use of a Solitaire solver is to find solutions for difficult deals,
or attempt to find shorter solutions. Yet another use is to collect statistics
from a large number of random deals (say, the Microsoft Windows Freecell deals
or PySolFC’s deals), which is part of what Freecell researchers do.
</p>

<p>
The Freecell implementation for Windows, Freecell 3D has also introduced a
“Race against the computer” mode of Freecell, which is an interesting challenge.
</p>

<p>
Finally, we have more recently started to investigate some “human/computer
collaborated” Freecell solving, where a human aided by a Solitaire suite with
good solver integration can attempt to solve some difficult deals (for both a
human and a computerised solver), by pruning dead ends, and by finding whether
reached states are solvable. This provides a combined solving power, that is
greater than the sum of both parts.
</p>

<h3 id="new_solver_is_too_slow">I started writing a solver for Freecell (of my own) but it is too slow. What can I do?</h3>

<p>
The problem with many naïve Freecell solving solutions is that, while they
can succeed in solving many Freecell deals, they may fail spectacularly in
the general case. Furthermore, Generalised Freecell (where there is an
arbitrary number of ranks) was shown to be
an <a href="http://en.wikipedia.org/wiki/NP-complete">NP-complete problem</a>
and as a result, it is likely that no efficient solution for solving that
in the general case can be found (but it is possible that some good heuristics
can be devised).
</p>

<p>
You can try inspecting the code of Freecell Solver or one of the
<a href="$(ROOT)/links.html#other_solvers">other solvers</a> for insights, but
note that their code (and especially Freecell Solver's) may be somewhat
complex, and hard to understand for people with relatively little experience.
You can also pursue some of the
<a href="$(ROOT)/docs/">Freecell Solver documentation</a> as well as the
<a href="http://tech.groups.yahoo.com/group/fc-solve-discuss/">archives of
the fc-solve-discuss mailing list</a> for some insights and ideas.
</p>

<p>
Here is some general tips:
</p>

<ul>

<li>
<p>
Make sure that the positions in the graph of the game are represented as a
single segment of memory (normally a C struct) and can be compared for
equivalence easily (using memcmp() or a similar function).
</p>
</li>

<li>
<p>
Use an efficient data structure to hold the states in the collection such as
a hash table or a self-balancing binary tree.
</p>
</li>

<li>
<p>
Often randomising the solution (see Freecell Solver's Random-DFS scan
which was inspired by a different solver called Freecell Tool can help
a lot).
</p>
</li>

<li>
<p>
Freecell Solver makes heavy use of switch tasking: having several different
searches operate on the same board, until the first search yields a solution.
This normally yields a solution quicker than a singular scan.
</p>
</li>

<li>
<p>
Consider implementing moves as meta-moves: sequences of several single-card
and/or sequence moves that implement a certain ends. This can yield a solution
faster than using single-card moves (also known as atomic moves).
</p>
</li>

</ul>

<p>
Finally, note that we could use a helping hand with Freecell Solver, and the
authors of other open-source solvers may be happy for help as well, so if
you want to help to improve something more mature, then contact us.
</p>

<h3 id="integrate_fcs_into_program">May I integrate Freecell Solver into my
program? If so - how?</h3>

<p>
Yes, you can, as long as you accept the
<a href="http://en.wikipedia.org/wiki/MIT_License">MIT/X11 licence</a> . We
also would appreciate an acknowledgement and a link to the Freecell Solver
home page, in the About Dialogue, and in other places.
</p>

<p>
Now regarding how to integrate: please either use the
<tt>freecell_solver_user_*</tt>
API, or alternatively parse the output of <tt>fc-solve</tt>
with the <tt>-p -t -sam -sel</tt> flags. The <tt>freecell_solver_user_*</tt>
API is not documented at the moment, but should be self-explanatory, and there
are some examples of using it in the various solvers in the distribution.
One useful way to configure a solver handle is to use <tt>fcs_cl.h</tt>
which provides an API based on the Freecell Solver command-line and is more
convenient than issuing multiple lower-level API calls.
</p>

<p>
You can opt to put the solver on a separate thread, on a separate process,
or alternatively limit the iterations and increase it constantly, in a
pre-emptive multi-tasking fashion.
</p>

<p>
Good luck and let us know if you run into any trouble, or, alternatively,
if you are successful.
</p>

<h3 id="solutions_are_too_long">The Solutions I got are too long. What can I do?</h3>

<p>
You can try using a flares-based preset such as <tt>qualified-seed</tt> and
optionally add <tt>--flares-choice fcpro</tt> and <tt>-fif 10</tt>, where 10
can be replaced by a larger (or smaller) number. So the complete command would
be:
</p>

<pre>
pi-make-microsoft-freecell-board -t 24 | \
    fc-solve -l qs --flares-choice fcpro -fif 10 -
</pre>

<p>
If this still does not work to your satisfaction, you can try constructing
a specialised heuristic from the many command line options of Freecell Solver
that will yield something. There are some examples for those in the individual
flares and soft threads under the <tt>Presets/presets</tt> directory.
</p>

<h3 id="why_in_c">Why is Freecell Solver written in C? Why not in another language?</h3>

<p>
Part of the reason why Freecell Solver is written in C, is because the first
released version (version 0.2) was written in C, and it continued to be
maintained in this language. Other reasons are:
</p>

<ul>

<li>
<p>
C is fast and memory efficient.
</p>
</li>

<li>
<p>
C is portable.
</p>
</li>

<li>
<p>
The bit-handling operators of C are utilised extensively in the Freecell
Solver source.
</p>
</li>

<li>
<p>
As opposed to C++, C is easier to get right, is more of a “no-nonsense
language”, is less hyped, and does not encourage crazy or pointless
practices. Also see
<a href="http://www.shlomifish.org/lecture/Freecell-Solver/slides/why_not_cpp.html">what
I’ve written about it previously</a>.
</p>
</li>

</ul>

<h3 id="unsolvable_solution">I found a solvable deal that Freecell Solver reports as unsolvable - should I report it to you?</h3>

<p>
The default Freecell Solver heuristic may have a small number of deals that
are reported as unsolvable despite being solvable. However, you can use scans
based on atomic moves to rectify that. See <tt>fc-solve --help-configs<tt>
and the <a href="$(ROOT)/docs/distro/USAGE.html">USAGE.html</a> file for
more information.
</p>