Suggestions on how to play Sokoban

Notation

The following terms will be used throughout this guide:

• move: one step of the worker whether pushing or not pushing a box.
• path: a sequence of moves.
• position: the whole problem with the worker and all boxes being at a certain place.
• solution: a position where each box is sitting on a dot.
• solution path: the sequence of moves from the original position to the solution.
• dead position: a position from which the solution can not be reached.

General Strategy

The shortest solution might contain 100, 300 or even 1000 moves (our simplest game 1 already needs 73 moves, game 8 needs 126 moves). If there are on average, say, 2 possibilities for each move and the solution takes 100 moves then a brute force search would require to search 2¹⁰⁰ paths to find the solution. Even for computers this is not possible. We therefore need to:

1. recognize early if a position is dead,
2. break down the overall goal into sub tasks. If a solution path of 100 moves can be broken down into, say, 10 sub tasks then the complexity of the problem is drastically reduced. Furthermore it might be possible to deduce the order in which the sub tasks need to be completed and then the whole problem becomes easy to solve,
3. find restrictions on the solution path,
4. think about other heuristics.

About 1) Recognizing dead positions early

1.1) Sometimes it is easy to decide whether a position is dead, one only has to look at the neighbourhood of one single box. All it takes is a 'local' inspection. If a box does not stand on a dot and can not be moved horizontally and not vertically, then the position is dead. The box may be blocked by the wall or by other boxes which also can not be moved.

1.2) It is slightly harder to see that a position is dead if the box is next to a wall and it can be pushed but only along the wall on the same side and none of the places it can reach is a dot.

1.3) In this generalization the box is next to a wall and can be moved to a place where it has not the wall on its side (place A below), but that free neighbouring place A can not be reached by the worker after pushing the box next to A.

These three cases can be decided locally and without moving the worker. Thus they can be checked out in the initial position and one can mark places as forbidden, say, with ! so that a box may never be pushed on such a place.

1.4) In a further generalization the place A can be reached by the worker but only at the price of putting another box at a forbidden place.

This explanation is recursive^[1], i.e. it characterizes a dead position by using the words 'dead position'. Such dead positions are harder to recognize because they can not be detected by local inspection and might need test moves.

About 2) Formulating Sub Tasks

Examples of sub tasks are:

1. Move the worker from A to B,
2. Move a certain box from A to B

where each of these tasks is to be accomplished without creating a dead position.

Example for (a): How the worker can pass a box to get to A:

All the empty space is needed as the worker has to walk around the box. If there is less empty space then the worker can not pass the box without generating a dead position.

If one knows many such subtasks with their shapes of the corridor by heart then one saves much time by not needing to think about it, here this 9-move-path. More importantly one will not give up because one thinks this sub task is impossible.

A question related to subtasks is how to find them. Subtasks come up, for example, when solving the problem reversely. Suppose a certain dot can only be reached from one side and only by one box. This box consequently needs to be pushed in a particular direction. In order to do so the worker needs to get to the other side of it. A task could be to bring the box and worker in the right position.

Another typical example of coming up with a sub task is the following. It is safe to assume that all interior space in a position is needed for the solution. That means, if the original position has bulky inner spaces, like the 2 times 3 empty area in the above example, then one can ask what is the purpose for that space. It could be that it is needed by the worker to pass a box or it is used to park temporarily a box to free space somewhere else intermediately. So if the bulky space is capable of storing a box temporarily then which box could that be? How can one get this box to this intermediate parking spot?

About 3) Formulating Restrictions on the Solution Path

There are many restrictions on the solution path possible just by looking at the position without trying out moves. Examples are:

3.1) There is a corridor that can be entered by a box but the box can never move through the whole corridor and therefore the space at the end of the corridor can never be reached from the side where the corridor ends.

3.2) A certain dot can be reached only from one side even though there is free space on different sides.

3.3) A certain box can never be moved in a certain direction and therefore can only reach one specific dot.

3.4) Because dots can be reached by boxes only from some side it determines the order in which dots must be occupied.

3.5) It may be clear which point needs to be covered last because the space is needed for the worker to push a box in a certain direction.

About 4) Other Heuristics

4.1) Any sequence of pushes that can be reversed can and should be tried out, even if it means that the worker has to go a long way in order to push from another side to reverse these pushes. Even if such an exercise looks pointless, the new position may open new possibilities of how to proceed.

4.2) If there is a straight line that separates all dots from at least one box, then this box must cross that line. If this is not possible then the position is dead. If there exists only one way for the box to cross that line then this is a strong restriction for the solution path.

Example of a Complete Solution (Game 8)

We introduce coordinates to label points. For example, the worker is initially at point G1.

Initially the worker has only the 2 options: a) to go through hole G3, or b) to go through hole E3. Going through G3 does only allow the worker to push the box at B3 to B1 → death. So the worker goes through the hole E3 to B2:

The only pushes we can make is a) box B3 up to B4 (not to B5 which means death) or box C2 to the right.

We realize that boxes can not be moved to dots on a route through G3 because they could never be moved to the left afterwards (see 1.2).

But in order to move them through the hole B3,C3 we need space in this area, so we need to park one or two boxes on the right and have to get them back afterwards.

We also realize that box B3 can only be moved on the B line and therefore will finally have to end on dot B4.

To move later boxes on C4 and then to push them to the right, the worker must be able to move to A4 but to get there from below, box B3 must be at B2 and spaces B3, C3, C2 must be free, so two boxes must get out of the way and be parked in the lower right.

u

but pushing down boxes A3 or B3 does not work. The only other option we had in position (2) is to push box B3 up to B4 first and then to do the moves leading to position (3). We get

Now we can make progress by pushing box C3 down to C2 and move with the worker around to push box F2 to G2 and G3:

As discussed above, we need spaces B3,C3,C2 free and get box B4 down to B2 so we need to park box C2 temporarily on G2. We get:

Now we can follow our earlier plan and push box G2 to C4 in order to push it further to the right:

The question is how far right do we have to push that box C4. Because we still need to push box G3 through the same path we need to get the worker to G4 and to do that we need to push box C4 as far as F4 and move the worker to G4 to push G4 to G3:

To move box G2 to the left the worker needs to go all the way back counter clockwise to H2.

The rest is simple: box G2 is pushed to C2, C4, D4

then box B2 is pushed to B4 and then the worker moves to G4 to finally push box F4 on dot E4.

DONE.