Source

shlomi-fish-homepage / t2 / open-source / projects / black-hole-solitaire-solver / index.html.wml

Full commit
#include '../template.wml'
#include "cpan_dists.wml"

<latemp_subject "Black Hole Solitaire Solver" />

<latemp_meta_desc "Solver for Black Hole Solitaire as well as All in a Row Solitaire" />

<p>
This is a solver, written in C, to solve
<a href="http://en.wikipedia.org/wiki/Black_Hole_%28solitaire%29">the
Solitaire variant called “Black Hole”</a>
and the one called
<a href="http://en.wikipedia.org/wiki/All_in_a_Row_%28Solitaire%29">“All in
a Row”</a>. It provides a portable C library,
and a command line application that after being fed with a layout will emit
the cards to move.
</p>

<h2 id="download">Download</h2>

<set-var ver="0.8.0" />
<set-var arc="black-hole-solver-<get-var ver />.tar.xz" />
<set-var sqlite_dump_arc="black_hole_solver.dump.xz" />
<set-var sqlite_dump_url="http://fc-solve.shlomifish.org/downloads/fc-solve/<get-var sqlite_dump_arc />" />

<ul>

<li>
<a href="http://fc-solve.shlomifish.org/downloads/fc-solve/<get-var arc />"><get-var arc /></a> - requires <a href="http://www.cmake.org/">CMake</a> to be built.
</li>

<li>
<a href="http://metacpan.org/release/Games-Solitaire-BlackHole-Solver">The Games-Solitaire-BlackHole-Solver CPAN Distribution</a> - an older version of the
solver written as a proof-of-concept, which produces identical results, but
is much slower and consumes more memory.
</li>

<li>
<a href="<get-var sqlite_dump_url />"><get-var sqlite_dump_arc /></a> - results
from running the solver on the first 1 million PySolFC deals - inside the dump
of an <a href="http://www.sqlite.org/">SQLite</a> database.
</li>

</ul>

<h3 id="download-solving-data">Solving Data</h3>

<p>
We’ve ran the solver on the first 1 million
<a href="http://pysolfc.sourceforge.net/">PySolFC</a> Black Hole Solitaire
deals and one can
<a href="http://fc-solve.shlomifish.org/downloads/fc-solve/black_hole_solver.dump.xz"><b>download</b>
the data from that</a> as a compressed textual dump of an
<a href="http://www.sqlite.org/">SQLite database</a>.
</p>

<p>
Here’s a description of the tables of the database:
</p>

<ol>

<li>
<p>
<b>bhs_runs</b> - this table contains the results and statistics of running
the solver on the boards. Its columns are:
</p>
<ol>
<li>
<b>idx</b> - the index of the PySolFC deal.
</li>
<li>
<b>status</b> - a character representing the verdict - ‘U’ for unsolved,
‘S’ for solved.
</li>
<li>
<b>num_checked</b> - the number of iterations that were checked (“num_times”).
If the game was unsolved, then it will be equal to num_generated (see below).
</li>
<li>
<b>num_generated</b> - the number of states generated (and not necessarily
checked). May only be different if the deal was solved.
</li>
</ol>

</li>

<li>

<p>
<b>bhs_solutions</b> - this table contains the compacted solutions for the
solved boards. Its columns are:
</p>

<ol>

<li>
<b>idx</b> - the index of the deal (that must be ‘S’ on “bhs_runs”).
</li>

<li>
<b>solution</b> - this is the compacted solution. The 0,2,4 etc. characters are
the indices of the stacks moved in the range 1-17. The 1,3,5 etc. characters are
the corresponding moved cards after calculating
<tt>chr(1 + $suits_to_n{$s} * 13 + $ranks_to_n{$r})</tt> where the suits
are ordered <tt>H,C,D,S</tt>. It will total 51*2 characters. Here’s
<a href="http://fc-solve.googlecode.com/svn/black-hole-solitaire/trunk/black-hole-solitaire/range-solving/populate-summary-database.pl">the script
that was used to generate them from the more verbose solution files</a>.
</li>

</ol>

</li>

</ol>


<h2 id="project-links">Project Links</h2>

<bitbucket_cpan_dist_links
    dist="Games-Solitaire-BlackHole-Solver"
    bitbucket_url="http://bitbucket.org/shlomif/black-hole-solitaire"
    freecode_url="http://freecode.com/projects/black-hole-solitaire-solver">
</bitbucket_cpan_dist_links >

<h2 id="similar-projects">Similar Projects</h2>

<ul>

<li>
<a href="http://fc-solve.shlomifish.org/">Freecell Solver</a> and
<a href="http://fc-solve.shlomifish.org/links.html#other_solvers">other Solitaire
solvers</a>.
</li>
</ul>

<x11_licence name="The Black Hole Solitaire Solver" />

<h2 id="news">News</h2>

<h3 id="news_version_0_8_0">Version 0.8.0</h3>

<p>
Version 0.8.0 of Black Hole Solitaire Solver was released. The highlights of
this release are the new <tt>--version</tt> flag, and the
<tt>--rank-reach-prune</tt> flag, which can improve performance.
</p>

<h3 id="news_version_0_6_0">Version 0.6.0</h3>

<p>
Version 0.6.0 of Black Hole Solitaire Solver was released. The highlights of
this release are the inclusion of the NEWS file, the <tt>--help</tt>
flag and most importantly the <tt>--display-boards</tt> flag that displays
the intermediate board layouts after every move.
</p>

<h3 id="news_version_0_4_0">Version 0.4.0</h3>

<p>
Version 0.4.0 of Black Hole Solitaire Solver was released. The highlight of
this release is the fact that it can now also solve
<a href="http://en.wikipedia.org/wiki/All_in_a_Row_%28Solitaire%29">All in
a Row solitaire</a>. As a result of this effort,
we have run the solver on the first 1 million PySolFC deals of All in
a Row Solitaire and have drawn some conclusions:
</p>

<ul>

<li>
<a href="http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1229">Statistics from the First 1,000,000 PySolFC All in A Row Deals</a>
</li>

</ul>


<h3 id="news_version_0_2_0">Version 0.2.0</h3>

<p>
Version 0.2.0 of Black Hole Solitaire Solver was released. The highlight of
this release is the porting of the solver from Perl to C which yields a very
dramatic gain in speed and memory consumption. As a result of this effort,
we have run the solver on the first 1 million PySolFC deals of Black
Hole Solitaire and have drawn some conclusions:
</p>

<ul>

<li>
<a href="http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1068">Solving Statistics for the First 1 Million PySolFC Black Hole Solitaire Deals</a>
</li>

<li>
<a href="http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1071">Follow-up with number of unsolved deals with positions span below a certain threshold</a>
</li>

</ul>

<define-tag camila_ron>
;;; Sponsored by Camila Ron
;;; Remove at 2013-10-24
<hr />

#include "camila_ron.wml"

</define-tag>

<camila_ron />