Menu

Klotski Solvers

Dow Drake
2009-09-17
2018-01-27
  • Dow Drake

    Dow Drake - 2009-09-17

    I'm starting this thread with an email conversation between Klajok and myself, but feel free to join in.

     
  • Dow Drake

    Dow Drake - 2009-09-17

    Klajok wrote:

    Hi,

    Thanks. I have looked at your website. Your GUI seems very nice for an eye. Unfortunately I can't check how your program works because I have no Windows on my computer (my "wine" emulator doesn't have .NET 2). Maybe I will find some free time to take a look at your code to find out how it works. Probably it would be difficult for me as I don't know C#.

    Currently I have no UI in my program, only input files. My solver should works on several typical platforms. Probably you will be able to compile it on your machine. I have heard from Bob Henderson that there is also one reliable solver, "JimSlide":

    Some of my puzzle designs are included in the download of Rodolfo Valeiras' "Deslizzzp" program at http://www.rodoval.com/Deslizzzp/Deslizzzp.html.  You can also download the "JimSlide" slide puzzle solver by Jim Leonard, which Deslizzzp can use to find solutions to the simpler puzzles.

    Could You tell me, how high are upper limits of your program? In my case: board is limited to 127 fields (with border). Program can eat almost all what given machine has got :) On my Athlon X2 4200+ (dual core 2.0 GHz) Linux 64-bit machine program can effectively generate e.g. about 580,000,000 new configurations and 2,500,000,000 possible moves per hour for Minoru Climb 24 Pro (see: http://www.puzzleworld.org/SlidingBlockPuzzles/pro24-1.htm ).
    By the way, this board (and all others made by Minoru Abe) was present in older versions of Klotski, but was removed from Linux distributions due to patent issues. Up today it is no proven that 227 moves is the shortest possible solution. I have found this "227" solution but with manually enabled branch trimming. Maybe you will be able to prove this?

     
  • Dow Drake

    Dow Drake - 2009-09-17

    Thanks for the great information. 

    I'm sorry my program is not more portable - I'd be glad if you had some way to try it out.  Unfortunately it relies heavily on several features of .NET 2.0, such as generic lists.

    I also did some testing with your program and tried to use it to solve Daisy, but I don't think I used the right parameter settings.  I looked at the source code a bit, but unfortunately, the only Polish word I know besides 'Klotski' is Solidarność!

    The way your algorithm uses the hard drive probably makes it better for solving more complex puzzles than mine, which relies on system memory.

    I started with a 256x256 board, using (unsigned) bytes for rows and columns, but changed this to 32 bit integers to allow negative values so the goal piece can move slightly off the board.  This change did not seem to affect performance.  That being said, my current algorithm is not well suited to large boards and/or many different types of pieces.

    For example, it has so far been unable to solve these two reasonably simple puzzles on my laptop (Turion X2 798MHz, 1.87 GB RAM):
    Shark.xml and Pelopones.xml

    I just tried the elegant "Climb Pro 24" puzzle you mentioned and could not get beyond 70 steps (around 1.4 million states).  I tried some different heuristic settings but none were able to produce a solution.

    The actual solving is done in a BackgroundWorker process, I use generic lists to manage states and move sequences and a hashtable to check if newly generated states are unique. 

    I don't understand the details of how the runtime manages memory very well, but what I'm seeing in the Performance monitor is that once the physical memory reaches about 80-90% (even though there is plenty of virtual memory free - page file shows only using: 3000/9000M), the application becomes slow to respond, and eventually one of these occurs:

    (1) If running the installed app, the background process terminates unexpectedly without an exception being raised and the RunWorkerCompleted event is triggered. 

    (2) If debugging in Visual Studio, an Out of Memory exception is raised.

    I'm currently looking for a system with more physical memory for testing and trying to improve my understanding of runtime memory management.

    My program can solve these standard puzzles very quickly:

    Agatka.xml, Ambush.xml, BalticSea.xml, BigBlock14.xml, Bone.xml, Cleopatra.xml, Daisy.xml, Fool.xml, Fortune.xml, Only18Steps.xml, Pennant.xml, RedDonkey.xml (a.k.a. 'Forget Me Not'), Success.xml, Trail.xml, Violet.xml

    These five puzzles require some amount of heuristic branch trimming, but the program is able to reach an optimal solution.

    Solomon.xml, Traffic Jam.xml, Polonaise.xml, Lodzianka.xml, Rome.xml

     
  • Daniel Błażewicz

    ddrake wrote:

    I also did some testing with your program and tried to use it to solve Daisy, but I don't think I used the right parameter settings.  I looked at the source code a bit, but unfortunately, the only Polish word I know besides 'Klotski' is Solidarność!

    The way your algorithm uses the hard drive probably makes it better for solving more complex puzzles than mine, which relies on system memory.

    I started with a 256x256 board, using (unsigned) bytes for rows and columns, but changed this to 32 bit integers to allow negative values so the goal piece can move slightly off the board.  This change did not seem to affect performance.  That being said, my current algorithm is not well suited to large boards and/or many different types of pieces.

    For example, it has so far been unable to solve these two reasonably simple puzzles on my laptop (Turion X2 798MHz, 1.87 GB RAM):
    - Shark.xml
    - Pelopones.xml

    I just tried the elegant "Climb Pro 24" puzzle you mentioned and could not get beyond 70 steps (around 1.4 million states).  I tried some different heuristic settings but none were able to produce a solution.

    The actual solving is done in a BackgroundWorker process, I use generic lists to manage states and move sequences and a hashtable to check if newly generated states are unique. 

    I don't understand the details of how the runtime manages memory very well, but what I'm seeing in the Performance monitor is that once the physical memory reaches about 80-90% (even though there is plenty of virtual memory free - page file shows only using: 3000/9000M), the application becomes slow to respond, and eventually one of these occurs:

    1. If running the installed app, the background process terminates unexpectedly without an exception being raised and the RunWorkerCompleted event is triggered. 

    2. If debugging in Visual Studio, an Out of Memory exception is raised.

    I'm currently looking for a system with more physical memory for testing and trying to improve my understanding of runtime memory management.

    My program can solve these standard puzzles very quickly:

    - Agatka.xml
    - Ambush.xml
    - BalticSea.xml
    - BigBlock14.xml
    - Bone.xml
    - Cleopatra.xml
    - Daisy.xml
    - Fool.xml
    - Fortune.xml
    - Only18Steps.xml
    - Pennant.xml
    - RedDonkey.xml (a.k.a. 'Forget Me Not')
    - Success.xml
    - Trail.xml
    - Violet.xml

    These five puzzles require some amount of heuristic branch trimming, but the program is able to reach an optimal solution.

    - Solomon.xml
    - Traffic Jam.xml
    - Polonaise.xml
    - Lodzianka.xml
    - Rome.xml


    1. My program have only 127 fields for blocks and borders because of memory / space on disc is a bottleneck for big problems. For 300GB free disc space on my computer I was able to go 128 steps for Climb 24 Pro without any branch trimming. At this stage program had to consider over 2,500,000,000 new configurations per one step. All others Minoru Climb boards are much more easy and can be solved in at most a couple of hours (Climb 15 boards).

    2. Your swap is not fully in use and your program finishes itself unexpected because you are using probably 32-bit Windows and one program can address at most 4GB of RAM (or maybe some indexes are signed long int and after 2GB pointers become negative values).

    3. Could you write what were parameters of running my solver and how did input file look? Probably I can help without much effort.

     
  • Dow Drake

    Dow Drake - 2009-09-17

    Klajok,

    I see your point about limiting to 127.  It should reduce memory to roughly 1/4 of current requirements.  I had decided against using signed bytes for row/column position because sbyte is not CLS compliant, but in hindsight, CLS compliance is not a major issue for this program.

    I'll test again and note how much memory the process is using.  Hitting the 4GB limit might be possible.  I don't understand your second point about the indexes and pointers with negative values, but will google this…  Thanks for your help.

    I tried your program again using the same command line as before:

        solver17_w32.exe 270 1 31 0.38 25 Samples\daisy.txt > daisy.out.txt 2> daisy.err

    I used the daisy.txt input file that came with the program and all the defaults from the PDF except that I reduced max disk space to 1 GB. 

    This time there were no errors and it found a solution in about 12 minutes.  I think my problem the first time was that I was poking around in the temp directories while the program was running.

     
  • Daniel Błażewicz

    This problem with indexes and 2GB is not very probably, so don't waste time on googling it :)

    12 minutes for this execution looks very strange. It should last seconds… I have compiled it under Linux, so probably it wasn't good for performance under Windows. Maybe you should compile it under real Windows. For such small board I think 30-60MB of RAM and 10-15 baskets should be sufficient.

     
  • Dow Drake

    Dow Drake - 2009-09-18

    I ran your exe again with settings changed to 30MB RAM and 10 baskets.  Execution time dropped to 58 seconds.  I also recompiled under Windows XP, but this had no effect on the execution time.  The exe file was a bit smaller though (48 KB compared to 516 KB)

    Yesterday I tried to get my KlotskiSolver to solve (http://www.puzzleworld.org/SlidingBlockPuzzles/images/instruct/climb12.jpg), but ran out of memory.  I made some code changes since then (version 1.2.6) and was able to get the 58 step solution for the default configuration.  I haven't had a chance to try the Q-2, Q-3 an Q-4 configurations yet.  To handle the non-rectangular board of Climb 12, I added the ability to have non-movable game-pieces, which I've been meaning to do anyway.

     
  • Daniel Błażewicz

    I have run program under my system: total "wall" time was about 1s. Daisy is really small board, for `./solver17_linux64.x 2.3 1 1 0.38 5 daisy.txt > stdout.txt 2> stderr.txt` total time was under 0.18 s.

     
  • Daniel Błażewicz

    I think long execution in your case is caused by slow hard disc on laptop (maybe it doesn't have a cache memory) or windows enforcing flushing data on disc (but it is less probable) or… I don't know.

    For Climb 12 total time on my program with allocated 20MB of RAM was about 36s: `./solver17_linux64.x 20 1 2 0.38 15 wsp12.txt`
    There is a couple of solvers which for such small board are much faster - here we have 7699385 possible configurations, we can all of them store at once in memory.

    I don't know how your program manage configurations, maybe this "generic list" is a source of problem with RAM or maybe an algorithm is not optimized for memory. If you wish we can talk about your and mine ideas about how such algorithm should look.

     
  • Dow Drake

    Dow Drake - 2009-09-18

    Thanks.  So when I used the same options as you for Daisy, I also get very fast execution (< 1 sec).  Further reducing the baskets from 10 to 1 was the dominant factor.

    Yes, I think there are a lot of inefficiencies with memory management in my implementation.  Probably the generic lists are not so much the problem as that fact that I'm filling them with full-fledged objects instead of hashes or simple data structures. 

    Efficiency is really not really my main focus at this point, though.  My main goal is to create a graphical sandbox for building, testing and playing puzzles of moderate complexity and give users some insight into what's going on under the hood.  My priorities right now are to improve the drag-and-drop interface and let users to select a printable sequence of goal states to help learn to solve the more difficult puzzles and improve intuition.

    I also want to keep the code as straightforward as possible for now so  I can remember how things are supposed to work.

    I would like to discuss algorithm ideas with you more at some point though, and  in the mean time, I'll keep your program handy for testing any puzzles that are out of reach of mine!

     
  • Roger Bim

    Roger Bim - 2018-01-27

    Hi! I was wondering if you are still working with the klotski project? Are you going to add the feature for the user to create their own shapes?

     

Log in to post a comment.