[Israel.pm] New Solver for "Black Hole" Solitaire (in Perl)
shlomif at iglu.org.il
Sun Jan 10 12:32:23 PST 2010
I wrote a new solver for the solitaire "Black Hole", and it can be found here:
Here's the complete story:
today I was going to play a game on http://www.brainbashers.com/ when I
remembered the Penguin Solitaire variant, which is similar to Freecell and
which I wanted to cover on the Cards Wikia. So I did a Google search for
"penguin solitaire" and saw it had a page on the wikipedia:
There I saw that it was invented by David Parlett:
and there I saw he also invented a solitaire called "Black Hole":
So I looked for it in PySolFC, read the instructions there and started to
play. The game involves putting a card that is one above or below the
foundation (wrapping from kings to aces). I noticed that there wasn't any
over-populated talon or something like that there, which meant that I could
probably build a DFS-based solver for it. So I set out to see if it was
The first thing I did was to adapt my PySol/PySolFC game generator to generate
the initial board of the PySolFC deals. This turned out to be a very
complicated and frustrating task for me, because I had to understand what's
going on with the code. But after a lot of playing with it, I was able to get
it to generate the initial deals. The changes for that are in the Freecell
Solver trunk now.
Then I started working on the solver. I decided to write it in Perl 5 because
it's a good prototyping language and I know it well. When writing it, I
heavily optimised for speed and low memory consumption by using bit fields (
see http://perldoc.perl.org/functions/vec.html ) and a gigantic hash lookup.
Then, after it was written, came the moment of truth: I ran it on the board
and it reported success. Great! But what's the solution? So I added some
solution tracing logic, to output the cards that should be moved. Then I was
able to play it and the game was solved. Yay!
I tried it on another game and it also worked. Then I ran it on the first few
games. Game #1 was reported as unsolvable, Game #2 was solved after a while,
and Game #3 consumed over 15% of my RAM and then was solved.
So it seems to be working nicely. The solver's code is made available under
the permissive MIT/X11 licence - share and enjoy.
Shlomi Fish http://www.shlomifish.org/
"Humanity" - Parody of Modern Life - http://shlom.in/humanity
Bzr is slower than Subversion in combination with Sourceforge.
( By: http://dazjorz.com/ )
More information about the Perl