[Israel.pm] New Solver for "Black Hole" Solitaire (in Perl)

Shlomi Fish shlomif at iglu.org.il
Sun Jan 10 12:32:23 PST 2010


Hi all!

I wrote a new solver for the solitaire "Black Hole", and it can be found here:

http://svn.berlios.de/svnroot/repos/fc-solve/black-hole-solitaire/

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:

http://en.wikipedia.org/wiki/Penguin_%28solitaire%29

There I saw that it was invented by David Parlett:

http://en.wikipedia.org/wiki/David_Parlett

and there I saw he also invented a solitaire called "Black Hole":

http://en.wikipedia.org/wiki/Black_Hole_%28solitaire%29

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 
possible. 

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.

Regards,

	Shlomi Fish

-- 
-----------------------------------------------------------------
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 mailing list