Deadlocks

Due to the limitation of just being able to push a box but never to pull it a level can become "deadlocked". That means the level isn't solvable anymore, no matter what the user does. The only way to solve the level is to undo some moves or to restart the level. Here is a description of some common deadlock types. The player is represented by an arrow, a box is shown as sphere and a goal is shown as little hole.

Dead square deadlocks

Dead square deadlocks are squares in a level that immediately create a deadlock situation when pushing a box to them. See this example level:

The player can push the box to every direction. But pushing the box to a darker shaded square results in a deadlock. If the player pushed the box one square up, the box would still be pushable (to the left and right), but no matter what the player does, it won't be possible to push the box to the goal anymore. This type of deadlock is "simple", because it just needs one box to create it. Even if the level contained more boxes they all would be irrelevant regarding the deadlock situation. Furthermore simple deadlocks are static - that means the squares creating a simple deadlock are there at level start and during the whole game play. No matter how the boxes are pushed, a box on one of these squares will always result in a "dead square" deadlock.

Freeze deadlocks

Sometimes boxes become immoveable. If a box becomes immoveable while not being located on a goal the whole level becomes unsolveable. The box is "frozen" on that square and can never be pushed again.

Pushing the box above the player one square up results in a freeze deadlock. The box becomes immoveable without being located on a goal => deadlock. Every time a box gets immoveable on a square that isn't a goal square this type of deadlock occurs. Note: It needn't to be the pushed box that isn't located on a goal:

Corral deadlocks

A corral is an area the player can't reach.

The right area (marked with little blue quadrats) isn't reachable for the player. Pushing the lower box to the right results in a situation that is deadlock. Even though both boxes are still pushable none of them can reach a goal anymore. Programs like JSoko can recognize some of these corral deadlocks by checking if a box can be pushed out of the corral area (that is the area marked by the blue quadrats) or all boxes can be pushed to goals. Corral deadlocks may include all other types of deadlocks. In fact the corral area (the area the player can't reach) can be seen as an own little sublevel.

In this level the player has just pushed the box one square down. This results in an area the player can't reach. Although it's possible to push one box out of the marked area this can only be done by creating another corral deadlock! Hence, the current situation is a deadlock.

Bipartite deadlocks

I call this type "bipartite deadlocks" because of the algorithm needed to detect them. Sometimes not every box can be pushed to every goal. Then it is important which box is pushed to which goal.

Example level:

Pushing the box to the right results in a bipartite deadlock. Although every box can be pushed to a goal after this push, it will be impossible to push all boxes to a goal at the same time.

Deadlocks due to frozen boxes

Frozen boxes don't create a Freeze deadlock when being located on a goal. Nevertheless, they may influence the reachable area of other boxes.

Pushing the box next to the player to the right results in a deadlock because the box gets frozen and therefore the other box can't be pushed to a goal anymore.

Closed diagonal deadlocks

A "closed diagonal deadlock" occurs if a closed diagonal cannot be opened and it's impossible to push all boxes to a goal.

Example level:

Pushing the box one square down results in a closed diagonal which can't be opened neither can all boxes be pushed to goals: a closed diagonal deadlock has occured.

Deadlocks in general

There are a lot more types of deadlocks in the game of Sokoban. Often deadlocks are a combination of more than one deadlock type. Detecting a deadlock is an important task for humans as well as for computers in order to be able to solve a level. Programs like JSoko can help the user to avoid some of the described deadlocks. However, most of the deadlocks remain undetected.