loprare.blogg.se - Puzzledom sokoban solutions

#PUZZLEDOM SOKOBAN SOLUTIONS FULL#
#PUZZLEDOM SOKOBAN SOLUTIONS WINDOWS 7#

If a F-cost is defined, sort by minimum F-cost.The tie-breaking for the priority queue is : The memory is fully controlled in order to set a memory limit for this solver without the risk of having an overflow memory.Īfter having implemented plenty of hash functions, I finally use the default hash function for bitset and I do a XOR with the player normalized position.ĭepending of the algorithm chosen, the open queue can be : It is an open-addressing hashtable with linear probing. It helps a lot when we have no goal ordering available.Ī custom transposition table is created especially for the solver. With this enhancement, just computing the heuristic score can lead to detect new deadlocks due to a goal that is no more accessible. It is a long computation and we have to be smart to optimize this computation. To solve this problem, I recompute the heuristic after finding a frozen area. Sometimes, these areas may change the heuristic score and affect the reachability of unfilled goals. The basic heuristic is defined as the heuristic that does not take into account any other boxes.ĭuring the main search, we will find new frozen boxes on goals (otherwise it is a deadlock). Even if we use a really accurate method to find a perfect bipartite matching between boxes and goals, there are lots of situations where the basic heuristic is not sufficient. To solve sublevels, the heuristic uses the nearest goal for each box which is really fast.Īssuming that the basic heuristic is sufficient to solve a Sokoban level is an error.

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.

#PUZZLEDOM SOKOBAN SOLUTIONS FULL#

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.

#PUZZLEDOM SOKOBAN SOLUTIONS WINDOWS 7#

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.