[Community Puzzle] Sokoban


Send your feedback or ask for help here!

Created by @eulerscheZahl,validated by @Westicles,@Nazdhun and @Kr4unos.
If you have any issues, feel free to ping them.

I’ve struggled with solving this puzzle in 1s. I have few small tips for anyone who would like to try:

  • deadlocks detection is probably not required.
  • you might want to use a faster language (I couldn’t find a way to solve it in python with simple solution).
  • if you’re able to solve all puzzles but you’re a bit too slow you can use additional turns for computing the answer.

Thank you very much for this puzzle! I’ve had a blast solving it and mostly failing :smiley:


I agree with @Gabbek.

Even with Swift, which I don’t think is in the “slow languages” category, I had to significantly uglify the code to pass in 1s.

Also, I’m not sure it doesn’t belong in the “Very Hard” section, as is often the case when you need to find heuristics to tackle a NP-hard problem with inputs that are only small (and not very small).

I don’t see it as very hard. My code isn’t more than a BFS, admittedly in one of the faster languages (C#).
As a compromise I increased the time for the first turn from 1 to 10 seconds (and had to reduce the maximum number of turns from 600 to 400 which is still more than twice of what you need).
cc @Nazdhun as I see a 76% solved state here.

I think hard is a very good place for this puzzle. Test cases could be much harder and it would force you to implement a lot more to manage it - as I’ve mentioned in my first post not being required to implement deadlocks solution and still passing all of them in 1s means it’s in good place, I think.

:sweat_smile: 10 seconds pushed me to 96% ^^.
But my code is still way unoptimized, i am new to Rust and as far as i read other forum posts, Rust is only compiled in Release mode fur multiplayer submits…

But as I said: Still optimizing, my code does produce a solution fpr Scoria 3 - Level 4 in 2,6 seconds with 87 pushes, but then i need > 400 steps and it fails.
So definitely my faulty code…

Did you put a heuristic in your BFS ? Some tests like Scoria 3-5 require more than 500k iterations with a basic version.

Edit : nvm I found my problem. I was considering each permutation of boxes to be different cases even though they were occupying the same spots. Down to 100ms on Scoria 3-5 :upside_down_face:

1 Like

I am still experiencing timeouts for Scoria 3-5, 3-7 and 3-10.
When solving them offline, the running times are 11-15 secs for these for me in php.

I tried already some micro-optimizations, but I can decrease it only by fractions of second, not 40%.
I am already using a single int as the state representation, using bitwise operators heavily, no objects, big work arrays preallocated… But I see there is 100% solution in Python, so it is not just about having a slow language.

So maybe more pruning of the search tree is needed?
(I have simple BFS, but already avoiding pushing a box to the border when no target is on the same border, I am not revisiting same state twice, etc.)
My node count for Scoria 3-5 is 572,660.
But I already DO consider each permutation of the boxes to be the same.

What is the node count of the search tree in your 100ms solution?

It’s been a while so I don’t remember what I did very well. But I just reran Scoria 3-5 with some counters, my code found the solution with 9489 BFS iterations in 75ms.

I can dig some more if you want, but those 572k need to be trimmed heavily.

1 Like

In the end, I gave up trying to be clever: Just rewrote my php code in C++.
Exactly same algorithm (a line-by-line conversion), but now for the hardest test case it runs 1.4sec and passes all validators easily.
If treating as a benchmark: speedup (php => C++) is ~10x for this particular code.
(EDIT: when I added #pragma GCC optimize "O3,omit-frame-pointer,inline, the speedup became 30x instead of 10x. Oh my, maybe I should change club?

It’s a shame, my first puzzle that I have no 100% solution in php, but have it in another language.

1 Like

By checking magaiti’s solution, now I see what single search-tree pruning idea I missed.
With this added, PHP code also passes hardest test in 4.5sec.

Bottomline: Having a fast language is nice. But being not dumb is (would have been) even nicer… :slight_smile: