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

[Levenglick Dov-RM07994]

Very nice - even though the most significant thing I'll be taking from
this email is Perl's vec function which somehow escaped my radar until
now. 

 
Best Regards,
Dov Levenglick
SmartDSP OS Development Leader

-----Original Message-----
From: perl-bounces at perl.org.il [mailto:perl-bounces at perl.org.il] On
Behalf Of Shlomi Fish
Sent: Sunday, January 10, 2010 22:32
To: Perl in Israel
Subject: [Israel.pm] New Solver for "Black Hole" Solitaire (in Perl)

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/ )
_______________________________________________
Perl mailing list
Perl at perl.org.il
http://mail.perl.org.il/mailman/listinfo/perl