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: [email protected] [mailto:[email protected]] 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 [email protected] http://mail.perl.org.il/mailman/listinfo/perl _______________________________________________ Perl mailing list [email protected] http://mail.perl.org.il/mailman/listinfo/perl
