Indian Computing Olympiad

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

This is clearly a shortest path problem in a graph. What is the graph?

  • Vertices are (Sx,Sy,Bx,By)
  • For each outgoing vertex, there are four possible outgoing edges of which at most one is a push. The rest are walks.

    Note that this is a directed graph — if we go from (Sx,Sy,Bx,By) to (S'x,S'y,B'x,B'y), we may not be able to reverse this move, in particular if the move was a push.

    Note that all our earlier algorithms like BFS, DFS, shortest paths work for directed graphs as well, in essentially the same way as for undirected graphs.
  • Target node is any vertex (Sx,Sy,Bx,By) where (Bx,By) = (Tx,Ty). If we assume that the initial box position is not the target, we have only four possibilities for (Sx,Sy).
  • Maintain the cost of a path as a pair (P,W) where P is the number of push move and W is the number walks. So, a push move adds cost (1,1) while a walk move adds (0,1). Costs are ordered lexicographically: (P,W)<(P',W') if P<P' or P = P' and W<W'.

    We can also map (P,W) to a single integer. Between each pair of push moves, the Sokoban can make at most N^2 moves.

    So we can map, say, (P,W) to a single integer P*160000 + W. With each push move, we add 160000 and with each walk move we add 1 to the cost.

How do we find the shortest path?

  1. Do BFS, but maintain unexplored configurations with cost in a priority queue (heap), based on cost, rather than in a queue. At each step, the next configuration to be explored is the minimum cost unexplored configuration in the priority queue.
  2. We can label edges between configurations with the cost added by this edge. We can then use Dijkstra's algorithm to calculate shortest path in M log M time, where M is the number of edges, using a heap to store burning times of unburnt edges. Note that the number of edges is small — each vertex has degree at most 4, so the total number of edges is about 2N.

    Notice that if we use a naive implementation of Dijkstra using an adjacency matrix, we have to store N*N entries which is too large. However, the edges are defined implicitly so we don't need to construct an explicit representation.

    As a further optimization, we can use an incremental version of Dijkstra's algorithm where we maintain edges in the heap as we visit them.

Problems related to