The Hungarian one has been modified a bit in order to be optimized in O(n^3). It is a long computation which uses the Hungarian algorithm in O(n^4) in time complexity. If you want to find optimal solutions, use a bidirectional search with A* algorithm in both side.Īll algorithms that require a heuristic use the bipartite matching. This is the quickest way to find a solution.

There is no check when the two searches overlap.īy default, Sokolution uses a bidirectional search with greedy algorithm in both side. A thread will perform the forward search and another thread will perform the backward search. The bidirectional mode is a combination of forward and backward modes. Note that the final player position should be able to reach its initial position. We start from the solution (all boxes are on goals) and we pull boxes in order to find the initial position. The backward mode is the opposite of the forward mode. This is the natural mode to solve Sokoban problems. The forward mode consists to start from the initial state and try to find a sequence of pushes to put all boxes on goals. Optimal algorithms : BFS, IDDFS, A* and IDAĮach algorithm can use the FORWARD mode or the BACKWARD mode and some special modes can be used.Sokolution can use several algorithms according to your needs : This is the main drawback of my solver but it seems nonetheless worthwhile. Because I use one byte to store the player position, the position can only vary from 0 to 255 included. All areas are 'binarized' which means that each square is represented as a bit in memory. I spent almost a year to profile and optimize all bottlenecks. Sokolution is the best solver because everything is really optimized in memory and speed. The plugin version is just a DLL file that we need to place into the 'Plugin' folder of the host program. Sokolution is compatible with host programs like Sokoban++ or YASC. It also allows all positions to be stored in only one byte which is great for the memory.

I choose this compromise because it is a limitation of bitsets, a binary structure in C++. Then, Sokolution can solve levels up to 100 for width and 100 for height. This implies that the maximum number of boxes is 255. Sokolution can solve *only* levels with less than 256 floor squares (walls do not count). The only limit of my solver is the number of floor squares for a given level. I chose C++ because it is a very fast low-level language really fast and we can have the full control of the memory thanks to the pointers. Sokolution is written in C++, uses STL library / C++14 concepts and is built with MinGW 5.1 under Windows 7 / 10.

11 Pre-calculated deadlock in the goal area.

5 Transposition table and hash function.

Sokoban solver online