[Community Puzzle] Sokoban

https://www.codingame.com/training/hard/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:

2 Likes

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:

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
    $hash=[];
    $gs=[[$bi,$pi,'']]; // gamestate stack
    do {
        $tgs=array_pop($gs); 
        $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
                        sort($tbyx);
                        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.
3 Likes

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