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

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky