General Sokoban information

From Sokoban Wiki

Current revision as of 22:04, 23 January 2023

Moves parity

The parity of the number of moves of a solution depends on the position of the player when the level has been solved.

Example:

In this level the move parity is always even when the level has been solved, no matter how the player is moved, since the player must always end at the position left to the box.

The reason for this is that the player can only move up, down, left and right:

in the above picture, the squares are alternately colored. With every move the player moves to a square of the other color, no matter how the player moves.
This means all darker squares are reached with an odd number of moves and all brighter squares are reached with an even number of moves.
Since the player start position is fixed for every level the move parity only depends on the end position of the player.

This information is sometimes useful, since for certain levels it may be helpful to now where the player ended. For example Original level 12:

The best known move solution contains 601 moves. Since the player starts on a darker square, he must end on a lighter square so that the total number of moves is odd.
Since there is just one such square the player can end on when the level is solved, the last push of a solution having an odd number of moves is known.

Pushes parity

The number of pushes needed to solve a specific Sokoban level is always either odd or even.

This can be shown by alternately coloring the squares:

With every push the boxes reach a square of the other color, no matter in which direction the boxes are pushed.
Adding walls to the level woudn't change this.
A box on a darker colored square can reach a darker colored goal with an even number of pushes and a lighter colored square with an odd number of pushes.

In this level one of the boxes must be pushed to a goal having a different color than the start position of the box. Hence, the total number of pushes needed to solve the level must be odd.

This property of Sokoban solutions can be leveraged in a Sokoban solver.
A solver that searches for a solution having the least number of pushes can increase the search depth by 2 each time no solution has been found for the current search depth when the parity of the solution is calculated first.