Sokoban Game

Sokoban is a seemingly simple board game where a player has to push all stones (also called crates/boxes)
available on the board to final/goal positions on a board that is a maze. An example game is shown below
in figure 1. The game rules are:
1. The player can move one square at a time in the four directions N,E,W,S.
2. The player can only push (no pulling) one stone one square at a time in the four directions N,E,W,S
(no diagonal push).
3. No stone or the player can go through a wall or other stones in a move.
4. To push a stone in the relevant direction the player has to be in the appropriate immediately neighbouring square.
5. The game ends when all stones are in goal positions. A stone can occupy any goal position.
The objective of the game is to push all the stones to their final positions. A solver may choose to optimize
i) the total number of moves or ii) the number of push moves. A push-move is one where a stone is moved.
Certain board positions are deadlocks - that is the puzzle cannot be solved from that position. For example,
if a stone is pushed into a non-goal corner square we have a deadlock state.
The game has been proved to be PSPACE-complete so no simple strategies are likely to be available.
A good solver will require search, planning, learning and using knowledge.
Multiple sets of puzzle instances (often called levels) are available online. (see the references).