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
