Training Material

## Heaps→Sokoban

Given a square grid with some blocked positions in which there is a Sokoban player (S) and a block (B). The player S has to move the block B to a target square T. Assume that the grid is at most 20×20.

Here is an example maze

```           ###########         S -- You
#T##......#         B -- Box
#.#.#..####         # -- Blocked square
#....B....#         T -- Target
#.######..#         . -- Empty cell
#.....S...#
###########
```

The only way to move the block is to push it. So, there are two types of moves for S:

• Walk east/west/north/south without pushing : Represent as e/w/n/s
• Push east/west/north/south: Represent as E/W/N/S

To push, S must be oriented correctly with respect to B. Thus, to push B west, S must be one square to the east of B. A push moves both S and B one step in the direction of the push.

Find a way to move B to T that minimizes the number of pushes. If two solutions have the same number of pushes, find the one with the minimum number of walks.

For example, here is a solution for the grid above:

```	eennwwWWWWeeeeeesswwwwwwwnnNN
```

Solution