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 
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.
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 
3 Likes
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.
2 Likes
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ā¦ 
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
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.
2 Likes
If you think about it, youāll notice that there arenāt that many states
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