Klotski Puzzle - new problem
Back to General discussions forum
Hello Friends!
Happy New Year to everyone - and Merry Christmas to those who celebrate it (and have celebrated already - while in our country we have it few days later).
Long ago :) there was a problem idea suggested by our colleague Radovan. I couldn't at first invent something suitable based on this, then thought about "sokoban", learnt it is from class of "sliding blocks puzzles" and at last have come to this one - "Klotski" puzzle. Then I thought some time about how to solve it. And it take time for me to write the working solution, sorry :) At last, here is the task:
Klotski
It seems to work all right and is not quite difficult, though not pretty straightforward. Perhaps here is some secret heuristic - I don't know. My solution works for minutes for some test-cases, so may be some care is needed for speed / memory.
Good luck with it and please feel free to write back if anything is wrong!
That was faster than I expected!
Hello Quandray, and thanks!
I am curious to study your solution - it looks like my approach was the same - and so I've tried one of inputs for which mine works about 15 minutes even on 16gb ram machine. However I either didn't compile that correctly or missing something about formatting - but I got "stray B found". Though hopefully I'll find and fix the cause later:
1
field 5 by 6 ; move B to 1 : 4
ABBBC
DDBEC
FGGEH
FIIJJ
K...L
MM.NL
UPD. Nevermind, just found that the comments above the code are added on this exactly purpose. I'll try some other "hard" variant with rectangular blocks.
As you've seen, I took some short cuts, so it's not a comprehensive solution. I improved it, and tried it on that layout, but it stopped after making 29 moves when it reached 2 gig of memory.
UPD: I tried again in 64bit mode and it gave the answer 30 after about 2 minutes. Is that the correct answer?
Yes, I think I got the same 30, but much slower, as you see. I've written it in Go (trying to learn it) so it is compiled to the same native code... Thus either I've missed some easy algorithm optimization, or some optimization on the language level (e.g. immutable strings leading to more operations and garbage collections), I'll try to figure it out... It takes between 5 and 7 Gb of memory, though I think I can save at least third of this... My congratulations! :)
With that layout, my code uses about 3 Gb. When it gets the answer it has looked at 20529811 positions and has 2737830 positions queued.
Does that match with yours?
The code I've submitted is now much better.