[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:


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.


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:

I need a clue. I’m at 93%, testcases 25&26 are always timing out on me in php. No recursion, just a dfs stack with a hash and an endstate array and a map precomputed for ‘dead zones’. there’s no target cell in a deadzone in those two testcases. I time tested testcase 27, because it seems to be the longest of the successful ones. 27 ends with 190,832 hash table elements. I time the solver code and it varies from 7.71s to >10s. I’ve tried trimming everything I can and changing variables to statics instead of globals. I’ve run out of ideas except running it locally to see where the two testcases may be hanging, but i don’t think they are hanging, i think they are just running out of time. I guess i could BFS, but with a depth of 159 for case 27, I’m reluctant. I haven’t tried using spl_object_hash, but from what i’ve read using hash as a simple array using keys of states comprised of the linear string of indexs of the boxes.’ '.player index, there wouldn’t be a performance increase. So i need a clue, I’ll post my code and maybe someone can point me in the right direction, tx.

static function solve($bi,$pi) { // bi=array of box indexes, pi=index of player
    $gs=[[$bi,$pi,'']]; // gamestate stack
    do {
        $hash[($fts=($ts=join(' ',$tgs[0])).' '.$tgs[1])]=1; // set hash
        if (in_array($fts,con::$lends)) return $tgs[2]; // good endstate found
        foreach(LDIRK as $k=>$d) { // check each direction
            if (con::$lmap[($npi=$tgs[1]+$d)]) { // player can move to new cell
                if (($bk=array_search($npi,$tgs[0]))===false) { // box in cell?
                    if (!isset($hash[$ts.' '.$npi]))            // have we been here before?
                        array_unshift($gs,[$tgs[0],$npi,$tgs[2].$k]); // put on front of stack because it's just a simple move
                } else { // there is a box in cell
                    if ((con::$ldmap[($nbi=$npi+$d)]==1)&&(array_search($nbi,$tgs[0])===false)) { // can it be pushed?
                        $tbyx=$tgs[0]; $tbyx[$bk]=$nbi; // redo box list
                        if (!isset($hash[join(' ',$tbyx).' '.$npi])) // have we been here before?
                            $gs[]=[$tbyx,$npi,$tgs[2].$k]; // prioritize box push for next iteration
    } while (!empty($gs));
    return ''; // never reaches

I checked test case #27 offline, my node count is 195,465, so your tree pruning (calculation of ‘no return’ cells) seems to be correct. My runtime is 2.9sec though which is already enough.
I see some notable differences:

  • my state representation is a single int. Thus deciding if target is reached is a single == instead of in_array(). Thus move generation and ‘can it be pushed’ code is a bit more complex, involving bitwise operators, but not using any array_search().
  • for the BFS queue of states I don’t use array_unshift(). I have a separate ‘pointer’ (array index) for write and read positions. I never delete anything from the queue, just move the ‘next_to_read’ index. Memory consumption is suboptimal with this approach, but still OK, 163 MB for test case #27.
  • Also, I preallocate the big arrays to store the tree with array_fill() to avoid multiple resizing as the arrays grow. The tree nodes are stored not as objects but separate arrays of ints for state, previous state and previous move. (I build the full sequence of moves for the solution only after I found the target state.)
  • I don’t prioritize push operation over single moves in the BFS, order is fixed URDL. Not sure if it changes anything, my recon ‘no’, the valid solution has pushes and moves intermixed.

I’m at 90344 visited nodes until I find a solution. And 535 leaf nodes that I would have to expand further. I’m using a plain BFS.
Took my C# solver 264ms so there’s plenty of room to pass with PHP. Not even using bitboards.

1 Like

okay! Took me a bit, but I changed from DFS to BFS and preloaded a large gamestate array instead of the stack approach and it solved w/o any timeouts. I timed the solving routine and total game time for each testcase. One testcase took on more than 200k states, but solved in under 200k. Testcase 27 took 194,701 iterations out of a total of 195,544. BFS time was only .61seconds, but total time (probably due to preloading 300k elements) averaged 3.08 seconds (max of 3.26). This is without bit twiddling and using just over half of the available memory. I did use a 2d array for the hash[player loc][string of box locations], i don’t know if it made a difference. The BFS did find the optimal solutions, but they weren’t much different than the first solution the DFS found (although 3x slower). The direction order made a small difference in solving time and nodes counts, but the biggest impact was shown in the DFS when order was changed. I guess my idea of prioritizing box pushes over simple moves wasn’t optimal. I may apply some of what I learned here with another puzzle of euler’s, who seems to be testing our boundaries. heh. Ok, I am thankful for the extra time on this puzzle, it definitely helped. The only array_search i ended up with is an in_array for testing for good endstate, And I didn’t use a sort function for box ordering, I replaced with a very simple array insertion with zero built-in functions. After cleaning up the code it should be well under 200 lines. I over-complicate things, however, the experience is invaluable. Good puzzle.


If you think about it, you’ll notice that there aren’t that many states :slight_smile:

If there are, say, 40 empty cells and 5 blocks, there’s C(40,5) ways of placing those blocks. Also, your character can be in 35 (40-5) different locations. that makes C(40,5)*35 = 23,030,280 states. Not only that, but you can represent each one of those states with a single number running from 0 to 23,030,279, using the combinatorial number system, or combinadic, for short: Combinatorial number system - Wikipedia. That means that you can create in advance a table with 23,030,280 booleans for registering the visited states. You don’t even need to store the states and compare! It’s a perfect minimal hash. So it’s possible to check for previously visited states super-fast, without having to copy states around, just doing a quick calculation.

I haven’t solved the puzzle yet, but I bet something like this can cut hundreds of milliseconds and, who knows, make the problem feasible in languages like Python.

If you look at the solution tab, two people already solved it using python so it is possible.

I didn’t solved it yet but a way to save time is to only consider the boxes positions, and the position from where your character pushed the last box.
The exact moves that your character will do to go from a “pushing emplacement” to another can be computed afterward, once the “pushing order” is found.

I suppose you’re suggesting some sort of hierarchical planning in which you plan first how the boxes should be pushed, and afterward you care about the character’s movement. Something like that can be done in Space Maze because you can move anywhere inside an island, so you don’t have to plan every single move of the car.

However, you can see that this does not work in Sokoban (at least not without backtracking), as the crates can block your character and prevent it from reaching other pushing emplacements for which you may have planned ahead. In my opinion, you’d be creating more trouble for yourself going that route for a problem that, as Euler says, can be solved with plain and simple BFS.

I’m guessing those solutions were feasible only after the increase from 1s to 10s. I was talking about solving them within the original time constraint of 1s :slight_smile: