Chapter 8 Sokoban and Path Finding

In the previous chapter we discussed how breadth-first search can be used to traverse the nodes of a graph in the order of increasing distance from a particular starting node, and how a little bit of extra bookkeeping makes it easy to construct the shortest paths from the start to every reachable node. In this chapter, we apply these ideas to the significantly more difficult problem of finding optimal solutions in the game Sokoban.

Sokoban is a computer game invented by Hiroyuki Imabayashi and originally published in Japan in the early 1980s. The Japanese word “Soko-ban” means warehouse keeper: your job as the player is to clean up a warehouse by moving crates to a their designated positions. Figure 8.1 shows the first level of the original game, which we will refer to as “Level 1” in the following.² The worker starts in the bottom center and must move the six crates in the left part of the level to the six target positions, or goals, shown as blue diamonds in the right part. The worker can walk up, down, left, and right, and push (but not pull!) a single crate in the direction of movement. A level is solved once every crate is on one of the goal squares.

For most human players, Level 1 poses only a mild challenge. After a bit of trial and error, it becomes apparent that there is basically only one possible opening move: The worker must first enter to top room from the right, clear a way to the left room, and then move the first crate to the goal area, using a path similar to the one shown in Fig. 8.2. The remaining crates can then be transferred to the goal room one by one, by first moving them to the “hallway” that leads to the goal room and then pushing them to the right. With this strategy, Level 1 can be solved in approximately 250 steps — and with a little effort, you may even be able to find the optimal 230-step solution.

For computers, on the other hand, playing Sokoban is a serious challenge, for two main reasons. The first is that the number of potential solutions grows very quickly with the size of the level. In each step, the worker can move in up to four different directions, so the total number of possible paths tends to grow exponentially with the number of steps taken. This is especially problematic because even small Sokoban levels require several hundred steps to solve. For example, the shortest solution of Level 1 takes 230 steps, and generating all possible paths of length 230 is an almost impossible undertaking. Brute force alone is no match for Sokoban.

The second difficulty is that computers have a hard time distinguishing between good moves and bad moves. As human players, we constantly devise heuristics and strategies that allow us to limit the number of moves that we need consider at each step, which lets us disregard hundreds of moves (and consequently millions of game states) that are theoretically possible but don’t seem promising to us. Since computers lack the ability to form ad-hoc strategies, trying all possible solutions is often the best thing they can do — which leads us back to the first point.

With that being said, implementing a simple Sokoban solver is both instructive and a lot of fun — even if the resulting program is still pretty basic and struggles with the more difficult levels.

8.1 Boards and Levels¶

Every Sokoban level is defined on a square grid and consists of walls, goals, crates, and the current position of the worker. The walls and goals are at fixed locations, but the worker and the crates can be moved horizontally and vertically. For simplicity, we assume that every level is a rectangle of width \(w\) and height \(h\), which can always be achieved by extending the level with empty squares. In this way we can assign every square on the board a position between \((0,0)\) for the upper-left corner and \((w-1,h-1)\) for the lower-right corner. We put all the functionality for working with such rectangular boards in a class called Board, which is outlined in Listing 8.1.

// A rectangular board of fixed size.
public class Board {
    private final int width, height;

    public Board(int width, int height) {
        this.width = width;
        this.height = height;
    }

    // Is the given point inside the board?
    public boolean isInside(int x, int y) {
        return x >= 0 && x < width && y >= 0 && y < height;
    }

    // The size of the board.
    public int height() {return height;}
    public int width() {return width;}

    // ...
}

We will use two different conventions for referring to squares on the boards. The first is to use a pair of coordinates so that \((0,0)\) refers to the upper-left square and \((w-1, h-1)\) to the bottom-right square. The second is to assign each square a unique index between 0 for the top-left corner and \(w\cdot {}h-1\) for the bottom-right corner. The main advantage of using a single index instead of a pair of coordinates is that it lets us store individual positions in variables of type int and sets of positions in bit sets. We can convert between coordinate pairs of the form \((x,y)\) and integer indexes using the following formulas:

\begin{equation*} k = y\cdot w + x,\qquad y = \lfloor k / w\rfloor ,\qquad x = k \bmod w. \end{equation*}

The Board class provides three methods for translating between integer positions and \((x,y)\) coordinates: index() computes the index of a position from its coordinates, whereas getX() and getY() recover the coordinates from the index (Listing 8.2).

// Convert between coordinates and indexes.
public int index(int x, int y) {
    return x + y * width;
}
public int getX(int index) {
    return index % width;
}
public int getY(int index) {
    return index / width;
}

To represent the four main directions on a rectangular board (up, down, left, and right), we define a nested type Direction inside Board that holds the corresponding offsets in the x- and y-direction (xOff and yOff) as well as a character charCode that serves as a shorthand for a particular direction (Listing 8.3). Four directions are predefined: UP, DOWN, LEFT, and RIGHT with the corresponding character codes ‘u’, ‘d’, ‘l, and ‘r’. In addition, we define an array ALL_DIRECTIONS that contains all four directions.

public record Direction(int xOff, int yOff, char charCode) {
}

// Predefined directions.
public static final Direction
        UP = new Direction(0, -1, 'u'),
        DOWN = new Direction(0, 1, 'd'),
        LEFT = new Direction(-1, 0, 'l'),
        RIGHT = new Direction(+1, 0, 'r');

public static final Direction[]
        ALL_DIRECTIONS = {UP, DOWN, LEFT, RIGHT};

If we want to move a point with coordinates \((x,y)\) in a certain Direction, we simply add xOff to \(x\) and yOff to \(y\). We can define a similar operation that works with indexes instead of coordinates. The index of the square \((x,y)\) is \(y\cdot w+x\), so moving to the left or right corresponds to decrementing or incrementing the index by 1, and moving up or down corresponds to subtracting or adding the level’s width. The moveIndex() method in Listing 8.4 implements this operation; it returns \(-1\) if the index cannot moved in the desired direction.

// Move an index in the given direction.
public int moveIndex(int index, Direction dir) {
    return isInside(getX(index) + dir.xOff(),
            getY(index) + dir.yOff())
            ? index + dir.xOff() + width * dir.yOff()
            : -1;
}

// Return the direction that moves oldIndex to newIndex.
public Direction getDirection(int oldIndex, int newIndex) {
    if (newIndex == oldIndex - width)
        return UP;
    if (newIndex == oldIndex + width)
        return DOWN;
    if (newIndex == oldIndex - 1)
        return LEFT;
    if (newIndex == oldIndex + 1)
        return RIGHT;
    return null;
}

A related method called getDirection() is defined in the same listing. It’s the inverse of moveIndex() in the sense that it takes two adjacent positions on the board and computes the direction that takes us from the first to the second index. If oldIndex and newIndex aren’t adjacent, the method returns null.

Storing Levels

Sokoban levels are conventionally specified using a text-based format in which each row of the level is encoded as a string of characters. For instance, Level 1 is represented as shown in the left part of Fig. 8.3. The space character “␣” denotes an empty square, “#” a wall, “$” a crate, “.” a goal, and “@” is the worker’s initial position. Two additional characters, “+” and “*”, are used in levels where either the worker or one of the crates starts on top of a goal square. The full list of characters and their interpretation is summarized in the right part of Fig. 8.3. We will use this encoding for reading levels and printing them to the screen (Exercises 8.1 and 8.2 and ).

    #####
    #   #
    #$  #
  ###  $##
  #  $ $ #
### # ## #   ######
#   # ## #####  ..#
# $  $          ..#
##### ### #@##  ..#
    #     #########
    #######

Since solving a Sokoban level typically involves generating and evaluating a large number of game states, we will use a more efficient internal representation for levels that is similar to the bitboards we used in our discussion of peg solitaire in Chapter 6. The main idea is to store the level as three sets of integers: one set each for the walls, the goals, and the crates. Since every position is a small integer between 0 and \(w\cdot {}h\), we can represent each of these sets as an array of \(w\cdot {}h\) bits. For instance, the following small level

is represented using three bit sets of size \(6\times 4\):

The walls and goals are fixed, so the first two sets are constant, but the set of crates must be updated continuously as the game progresses. The position of the worker is stored separately.

Listing 8.5 shows the outline of a class called Level that we will use to represent Sokoban levels of a given width and height. (The BitSet class we use to represent bit sets is described in Exercise 5.16.) Initially, the bit sets walls, goals, crates are empty and the worker’s starting position workerStart is set to an invalid value. The constructor of Level takes the desired width and height as arguments and uses them to initialize the underlying Board.

// Representation of Sokoban levels.
public class Level extends Board {
    private final BitSet walls = new BitSet();
    private final BitSet goals = new BitSet();
    private final BitSet crates = new BitSet();
    private int workerStart = -1;

    private Level(int width, int height) {super(width, height);}

    public BitSet walls() {return walls;}
    public BitSet goals() {return goals;}
    public BitSet crates() {return crates;}
    public int workerStart() {return workerStart;}

    // ...
}

To populate the level with objects, we define a method setCode() that takes one of the characters codes defined in Fig. 8.3 and updates the fields of Level accordingly (Listing 8.6). Notice that changing a single square may require changes to all three bit sets and workerStart. To keep the number of special cases we have to consider to a minimum, we first clear all information associated with the square and then update the fields that are affected by the new character code. For instance, if charCode is ‘#’ we add a wall, and if it is ‘*’ we add both a goal and a crate.

public void setCode(int x, int y, Character charCode) {
    int index = index(x, y);
    walls.remove(index);
    goals.remove(index);
    crates.remove(index);
    if (workerStart == index)
        workerStart = -1;
    switch (charCode) {
        case ' ' -> {}
        case '@' -> workerStart = index;
        case '#' -> walls.add(index);
        case '.' -> goals.add(index);
        case '$' -> crates.add(index);
        case '+' -> {
            workerStart = index;
            goals.add(index);
        }
        case '*' -> {
            crates.add(index);
            goals.add(index);
        }
        default -> throw new IllegalArgumentException(
                "Invalid character: " + charCode);
    }
}

Exercises

[8.1]Use the text-based encoding for Sokoban levels described in Fig. 8.3 to implement a function Level.parse() that creates a new instance of Level from a list of Strings in this format.

8.2 Moving the Player¶

In addition to the Level class, which represents a level in its original state, we also need a data type GameState that stores the state of the level as the game progresses. Only two things can change: the worker’s current position, which we store as a single integer, and the positions of all crates, which we store as a bit set (Listing 8.7).

public record GameState(int workerPos, BitSet crates) {
    // Initialize using starting configuration of 'level'.
    public GameState(Level level) {
        this(level.workerStart(), level.crates());
    }

    // Is this state a solution of level?
    public boolean allCratesOnGoals(Level level) {
        return level.goals().containsAll(crates);
    }

    // ...
}

The allCratesOnGoals() method in Listing 8.7 determines whether a particular game state is a valid solution. This is the case if every crate is on a goal square, in other words, if the bit set level.goals() contains every element of the bit set crates.

For the moment, let’s assume that the crates are in fixed positions and start with the simpler problem of moving the worker alone. We can model this problem by defining a special graph in which nodes and edges represent locations and the possible moves between them. In our case, each location is a square in the level that doesn’t contain a wall or a crate, and it is possible to move between two locations if they are horizontally or vertically adjacent. Figure 8.4 shows the resulting graph, which we will call the move graph, for the initial state of Level 1.

Implementing the move graph is straightforward. Every position in the level, and therefore every node in the move graph, can be represented by its index, so we can define a class MoveGraph that implements the Graph interface and has nodes of type Integer (Listing 8.8). The arguments of the constructor MoveGraph() are the level and the positions of all crates. Since crates are considered immovable, we don’t need to distinguish between walls and crates and simply combine them into a single set of obstacles.

public class MoveGraph implements Graph<Integer> {
    private final Level level;
    private final BitSet obstacles;

    public MoveGraph(Level level, BitSet crates) {
        this.level = level;
        obstacles = new BitSet(level.walls());
        obstacles.addAll(crates);
    }

    // Return the empty positions adjacent to 'index'.
    @Override
    public BitSet neighbors(Integer index) {
        var result = new BitSet();
        for (var direction : Board.ALL_DIRECTIONS) {
            result.add(level.moveIndex(index, direction));
        }
        result.removeAll(obstacles);
        return result;
    }
}

The neighbors() method computes the list of nodes that can be reached from a given position, namely the adjacent positions that are not blocked by an obstacle. To compute the neighbors, we first add all adjacent positions to a bit set result and then remove the blocked squares in obstacles.

As a simple application of the move graph, let’s use it to find the worker’s shortest path between two positions in a level. For example, if level is an instance of Level that represents Level 1, we can use breadth-first search to find the path from the worker’s starting position \((11,8)\) to the right of the first box at \((8,4)\):

List<Integer> path = new MoveGraph(level, level.crates())
        .findPathTo(level.index(11, 8),
                pos -> pos == level.index(8, 4));

The return value is the shortest path between the two positions as a list of integers. One way to print this path in human-readable form is to take pairs of adjacent positions and translate them into a string of move commands:

if (path != null) {
    for (int i = 0; i < path.size() - 1; i++) {
        Board.Direction dir = level.getDirection(
                path.get(i), path.get(i + 1));
        System.out.print(dir.charCode());
    }
    System.out.println();
} else {
    System.out.println("No solution");
}

For the path constructed above, this outputs “ullluuu”.

Exercises

[8.2]Implement a method for GameState that prints the current state using the text-based format described in Fig. 8.3.

[8.3]A Sokoban level is closed if there are no gaps in the walls through which the worker could escape. (Crates are ignored in this case.) Suggest an algorithm that determines whether a level is closed.

[8.4]The move graph shown in Fig. 8.4 consists of four disjoint groups of nodes that are all connected to each other, which are also known as the components of the graph. Explain how to compute the components of a given instance of MoveGraph.

8.3 Pushing Crates¶

We just saw how to model the movement of the worker using graphs — can we use the same idea to model the movement of crates as well? In theory, we could define a graph of game states in which the neighbors of each node are those states that can be reached either by moving the worker or by pushing a crate. Given this graph, we could then solve a level by searching for a path from the level’s initial state to the nearest game state in which every crate is located on a goal.

As appealing as this solution may appear, it has a serious problem: For all non-trivial Sokoban levels, the resulting graph is so large that we quickly run out of memory when we attempt to traverse it using breadth-first search. In the case of Level 1, for instance, the optimal solution requires 230 steps. Before breadth-first search reaches any node that is 230 steps away from the start, however, it has to visit every game state that is reachable in 229 steps or less, of which there are millions. And since breadth-first search guarantees that every node is visited exactly once, all those states must be kept in memory until a solution has been found. If we want to model this puzzle as a graph traversal problem, we therefore have to find a way to reduce the size of the graph significantly.

The first important insight is that the worker always alternates between two actions: moving to the next crate and then pushing it one step in the direction of movement. Moving toward a certain crate is easy: we already saw how to do this using the move graph in the previous section. We can therefore disregard all steps in which the worker doesn’t push a crate and remove the associated nodes and edges from the graph. We call the resulting graph the push graph: every node in this graph represents one configuration of crates, and every edge indicates one way to push a reachable crate to a neighboring square. We can solve a level by searching for a path through the push graph that leads from the starting state to a state in which all crates are on a goal.

Figure 8.5 shows a small Sokoban level and its direct neighbors in the push graph. In the starting state \(S\), there are six ways to push the level’s two crates: The left crate can be pushed up or down, and the right crate can be pushed in all four directions. The node therefore has six neighbors in the push graph. Notice that when following an edge in the push graph, the worker “jumps” to its new position, which is always the original position of the crate that was pushed.

In contrast to the move graph, most edges of the push graph are directed since pushing a crate is usually not a reversible operation. In Fig. 8.5, the only edge that goes in both directions is the one to the node labeled E. This node is reached by pushing the left crate down, and after pushing the crate back up we return to the starting configuration. In contrast, there are no edges from A or B back to the central node. Even though the right crate can be moved back to its original position, the worker ends up in a different location than in state S.

Listing 8.9 defines the push graph as a Graph with nodes of type GameState. Since the graph is typically enormous in size, we leave the nodes() method unimplemented. The implementation of neighbors() computes the list of game states that can be reached by pushing a single crate. We first iterate over all reachable positions in the level by creating an instance of MoveGraph and traversing it using visitNodes(). For every reachable position we then call tryPush() to check whether there is a movable crate in one of the adjacent squares; if there is, we add the resulting GameState to the list of neighbors.

// A graph of game states that are one push apart.
public class PushGraph implements Graph<GameState> {
    private final Level level;

    public PushGraph(Level level) {this.level = level;}

    // Computes game states reachable by pushing a single crate.
    public List<GameState> neighbors(GameState state) {
        var neighbors = new ArrayList<GameState>();
        var moveGraph = new MoveGraph(level, state.crates());
        moveGraph.visitNodes(state.workerPos(), index -> {
            for (var dir : Board.ALL_DIRECTIONS) {
                int crateIndex = level.moveIndex(index, dir);
                var newState = state.tryPush(level, crateIndex, dir);
                if (newState != null)
                    neighbors.add(newState);
            }
        });
        return neighbors;
    }
}

One notable detail is that the list of game states returned by this implementation of neighbors() is sorted by the distance of the crate being pushed from the worker’s position in state. This is because Graph.visitNodes() is a variation of breadth-first search and therefore visits the nodes of the move graph in the order of increasing distance from state.workerPos(). We will discuss in Exercise 8.6 how this ordering affects which path through the push graph is discovered first.

The tryPush() method used in the implementation of neighbors() attempts to push a crate in the specified direction and returns a new GameState if it is successful (Listing 8.10). Moving a crate is only possible if there actually is a crate at position cratePos and if the square next to the crate isn’t blocked by a wall or another crate. If this is the case, we compute a new set of crate positions newCrates by replacing the old crate with the new one. If there is no movable crate nearby, tryPush() returns null.

// Push the specified crate, return new game state if successful.
public GameState tryPush(Level level, int cratePos,
        Board.Direction direction) {
    var newCrate = level.moveIndex(cratePos, direction);
    if (newCrate == -1)  // outside of level?
        return null;
    if (crates.contains(cratePos) && !blocked(level, newCrate)) {
        var newCrates = new BitSet(crates);
        newCrates.remove(cratePos);
        newCrates.add(newCrate);
        // Create game state with worker at 'cratePos'.
        var newState = new GameState(cratePos, newCrates);
        if (!newState.hasDeadlockAt(level, newCrate))
            return newState;
    }
    return null;
}

public boolean blocked(Level level, int pos) {
    return crates.contains(pos) || level.walls().contains(pos);
}

As a simple but important optimization, tryPush() rejects moves that cause a deadlock, an unsolvable game state in which one or more crates are stuck and can no longer be moved to any of the goals. The simplest kind of deadlock occurs when a crate is pushed into a corner, in other words, if the crate completes a \(2\times 2\) block of walls or other crates. The implementation of causesDeadlock() in Listing 8.11 tests whether a game state has such a \(2\times 2\) block in the neighborhood of crateIndex. If crateIndex is a goal square, the method immediately returns false because deadlocks are only problematic for crates that still need to be moved. Otherwise, it checks whether crateIndex is the lower-right, lower-left, upper-right, or lower-right corner of a \(2\times 2\) block of walls or other crates. The two nested for loops iterate over these four directions, with the loop variables xOff and yOff forming the offset pairs \((-1, -1)\), \((-1, 1)\), \((1, -1)\), and \((1, 1)\). Each of these offsets is then used to test whether the three squares next to crateIndex in a certain direction are all blocked.

// Check if the crate at 'crateIndex' is part of a 2x2 deadlock.
private boolean hasDeadlockAt(Level level, int crateIndex) {
    if (level.goals().contains(crateIndex))
        return false;
    int x = level.getX(crateIndex);
    int y = level.getY(crateIndex);
    for (int yOff = -1; yOff <= 1; yOff += 2) {
        for (int xOff = -1; xOff <= 1; xOff += 2) {
            if (blocked(level, level.index(x + xOff, y))
                    && blocked(level, level.index(x, y + yOff))
                    && blocked(level,
                    level.index(x + xOff, y + yOff)))
                return true;
        }
    }
    return false;
}

This simple deadlock test is surprisingly effective: When solving Level 1, it reduces the size of the push graph and the number of nodes that must visited by a factor of almost 6, from 23 755 405 to 4 095 995! Even though there are more complex deadlock patterns, using more sophisticated deadlock tests quickly hits a point of diminishing returns: Since the test must be performed for every game state that is examined, an accurate but time-consuming test can be slower overall than a cheap test that misses a few deadlocks.

8.4 Solving Sokoban¶

We are almost there: Solving a given Sokoban level is now a matter of finding a path in the push graph that starts at the initial state of the level and ends at any game state that solves it:

List<GameState> path = new PushGraph(level)
        .findPathTo(new GameState(level),
                gameState -> gameState.allCratesOnGoals(level));

For Level 1, the resulting path is a list of 98 GameState objects that starts like this:

GameState[workerPos=163, crates=BitSet[43,64,81,83,135,138]]
GameState[workerPos=83, crates=BitSet[43,64,81,82,135,138]]
GameState[workerPos=64, crates=BitSet[43,45,81,82,135,138]]
GameState[workerPos=81, crates=BitSet[43,45,82,100,135,138]]
GameState[workerPos=100, crates=BitSet[43,45,82,119,135,138]]
GameState[workerPos=45, crates=BitSet[43,64,82,119,135,138]]

Let’s take a look at the same solution in a more legible format that describes the worker’s movement from the starting position:

ullluuuLUllDDuuruurDldldlldddrRRRRRRRRRRRRurD
llllllllllllllulldRRRRRRRRRRRRRRR
llllllllllllluuurrdDuuuruulDDDDulldddrRRRRRRRRRRRurD
llllllllllllluuurrdDuulldddrRRRRRRRRRRR
llllllluuulLulDDDuuuurrDlldlldddrRRRRRRRRRRdrUluRR
lldlllllluuuLLulDDDuulldddrRRRRRRRRRRdrUluR

There is one letter for each step taken by the worker. The lower-case letters u, d, l, and r indicate that the worker moves up, down, left, or right, and upper-case letters highlight those steps that involve pushing a crate. For better readability, we have broken the solution into multiple lines, one for each of the six crates. (See Exercise 8.5 for a compressed version of this format.) The number of letters in this example is 262, so the worker has to take 262 steps, 97 of which involve pushing a crate.

Retracing the Worker’s Steps

Let’s conclude this section by considering how we can compute the worker’s step-by-step movement from the path of GameStates through the push graph. The computeSteps() method in Listing 8.12 shows the general idea. We iterate over all pairs of game states on the path and determine the worker’s optimal path that leads from the before to the after state. This is done by the planMovement() method, which appends the necessary movement commands to steps. The complete sequence of movement commands is returned at the end of the function.

public static String computeSteps(
        Level level, List<GameState> pushes) {
    if (pushes.isEmpty())
        return "--no solution--";
    var steps = new StringBuilder();
    for (int i = 1; i < pushes.size(); i++) {
        GameState before = pushes.get(i - 1);
        GameState after = pushes.get(i);
        planMovement(level, before, after, steps);
    }
    return steps.toString();
}

In general, the string of movement commands for a given pair of GameStates consists of zero or more lower-case letters that move the worker toward the next crate and a single upper-case letter that pushes the crate to its new position. For example, the first two game states in the solution we constructed at the start of this section are

GameState[workerPos=163, crates=BitSet[43,64,81,83,135,138]]
GameState[workerPos=83, crates=BitSet[43,64,81,82,135,138]]

The first state is the level’s starting configuration, whereas the second state is reached by moving the worker toward the upper room and pushing the blocking crate one place to the left. The sequence of steps that leads from the first to the second state can be written as “ullluuuL”; this is the first part of the path shown in Fig. 8.2.

For each pair of game states before and after, the planMovement() method in Listing 8.13 computes the shortest path that leads from before.workerPos to after.workerPos. We first compute the path from before.workerPos to the crate that is about to be pushed. This position is computed using the workerBeforePush() method discussed below, and the path is obtained by traversing the move graph of the before state. For each step along this path we output a lower-case letter. Afterwards we output a single upper-case letter that pushes the crate and moves the worker to its position in after.

private static void planMovement(Level level, GameState before,
        GameState after, StringBuilder out) {
    int beforePush = workerBeforePush(level, before, after);
    var workerPath = new MoveGraph(level, before.crates())
            .findPathTo(before.workerPos(),
                    pos -> pos == beforePush);
    if (workerPath.isEmpty())
        throw new RuntimeException("Invalid solution");
    for (int j = 1; j < workerPath.size(); j++) {
        var moveDirection = level.getDirection(
                workerPath.get(j - 1), workerPath.get(j));
        out.append(moveDirection.charCode());
    }
    var pushDirection = level.getDirection(beforePush,
            after.workerPos());
    out.append(Character.toUpperCase(pushDirection.charCode()));
}

The final problem is to determine the worker’s position immediately before pushing the crate in the last step. The following image illustrates the situation:

We want to compute the position marked with an X, which the last position of the worker before pushing the crate to its current position. The workerBeforePush() method in Listing 8.14 computes this position by moving the worker one step back from its position in after. The direction reverseDir that moves the worker back is determined by comparing the before and after states. We first compute the index of the crate was moved (movedCrate) by computing the set difference of the crates in before and after and extracting the only element of the result. We then use getDirection() to find the direction that leads from movedCrate to the worker’s current position in after; another step in this direction moves after.workerPos() to the position marked X.

private static int workerBeforePush(
        Level level, GameState before, GameState after) {
    BitSet crate = new BitSet(after.crates());
    crate.removeAll(before.crates());
    int movedCrate = crate.iterator().next();
    Board.Direction reverseDir =
            level.getDirection(movedCrate, after.workerPos());
    return level.moveIndex(after.workerPos(), reverseDir);
}

Exercises

[8.5]Representing the worker’s movement as a string of upper- and lower-case letters has one disadvantage: It can be difficult to see at a glance how many steps you have to take when the string contains long runs of identical letters. A simple solution is to add an optional numerical prefix to each character that indicates how often it should be repeated. With this convention, the string

ullluuuLUllDDuuruurDldldlldddrRRRRRRRRRRRRurD

can be abbreviated as

u3l3uLUllDDuuruurDldldll3dr12RurD

which is shorter and easier to read. Write a program that takes a regular movement string and outputs a compressed version as shown above.

[8.6]The order in which breadth-first search visits the nodes of a graph depends on the order in which it inspects the neighbors of each node. As we mentioned in Section 8.3, our implementation of the neighbors() method in PushGraph returns a list of nodes that is sorted by the distance from the worker to the crate being pushed. What solution to Level 1 is discovered first if you modify PushGraph.neighbors() to reverse the list of neighbors before returning it?

8.5 Minimizing the Number of Steps¶

The Sokoban solver we implemented in the previous section is able to find optimal solutions — optimal in the sense that they require the fewest pushes. Alternatively, the quality of a solution can also be measured by the total number of steps the worker has to take. In the following, we will refer to these two criteria as “push-optimal” and “step-optimal.”

To appreciate the difference between these two measures, let’s compare the first steps of the push-optimal solution for Level 1 we constructed the previous section to the step-optimal solution:

The first 12 steps are identical and are necessary to reach the upper room of Level 1, but once inside this room, the solutions diverge: In the step-optimal solution, the worker proceeds directly to the left room and starts to push the first crate to the goal area, but in the push-optimal solution, the worker briefly stays inside the upper room and pushes two of the crates downwards. In principle, these two additional pushes are a good idea: Since the two crates have to be moved downward eventually, we might as well move them at the earliest opportunity. But if you also take the worker’s total number of steps into account, moving the crates later — when the worker passes through the upper room a second and a third time — turns out to be more efficient.

How do we find a step-optimal solution? We already discarded the obvious idea — constructing a graph of all the worker’s possible moves — as impracticable when we discussed the push graph in the Section 8.3. It is therefore a better idea to start with the push graph and augment it with information about the cost of pushing a crate. One way to do this is to label every edge with a the number of steps required to reach the crate being pushed. A graph in which edges are labeled with a numeric weight are called weighted graphs, so what we are looking for is the weighted push graph of a Sokoban level.

Figure 8.6 shows an extended version of the push graph from Fig. 8.5, in which each edge is now labeled with the number of steps that are required to reach the target node. For example, the edge from S to F is labeled with 1 because the worker simply has to move one square up to push the crate; similarly, the label on the edge from S to A is \(4\) because the worker has to take a total of four steps: one step down, two steps to the right, and one step up (drrU).

In a weighted graph, the weighted length of a path between two nodes is defined as the sum of all edge weights along the path. In Fig. 8.6, for example, the weighted length of the path \(E\to {}S\to {}D\to {}D1\) is obtained by adding the weights of \(E\to {}S, S\to {}D\), and \(D\to {}D1\), which is \(5+4+3=12\). In this case, \(12\) steps are needed to obtain rearrange state E into state \(D1\). The shortest path between two nodes in a weighted graph is the path with the smallest possible weight. The problem of finding the step-optimal solution of a Sokoban level is therefore equivalent to finding the shortest path in the weighted push graph that leads from the starting configuration to any configuration in which all crates are on a goal.

Before we consider the problem of finding shortest paths in a weighted graph, let’s first see how to represent and compute the weighted push graph itself. Similar to the way we handled regular graphs, we represent weighted graphs by an interface called WeightedGraph that computes parts of the graph as needed (Listing 8.15). The main difference compared to the Graph interface is that we have replaced the neighbors() method with an edges() method that returns the collection of edges that originate at a given node. Each edge of a weighted graph is represented by the nested type Edge that stores an integer weight and the target node to which the edge leads.

// Basic interface for representing weighted graphs.
public interface WeightedGraph<N> {
    record Edge<N>(N target, int weight) {
    }

    Iterable<Edge<N>> edges(N node);

    default Iterable<N> nodes() {
        throw new UnsupportedOperationException();
    }
}

The weighted push graph can now be implemented as a WeightedGraph with nodes of type GameState (Listing 8.16). For a given node in the graph, edges() returns a list of Edges that point to game states that can be reached by pushing a single crate. The weight of each edge is the number of steps that are required to reach that crate and push it to an adjacent square. In Listing 8.16, we first use scanLayers() to traverse the move graph of the current game state. Every layer we find corresponds to the set of positions that are at a certain distance from state.workerPos(). If, for any of these positions, there is a movable crate on an adjacent square, we create a new edge to the resulting game state. The weight of the edge is the distance of the current layer plus 1, since an additional step is necessary to push the crate.

public class WeightedPushGraph
        implements WeightedGraph<GameState> {
    final Level level;

    public WeightedPushGraph(Level level) {
        this.level = level;
    }

    public List<Edge<GameState>> edges(GameState state) {
        var edges = new ArrayList<Edge<GameState>>();
        var graph = new MoveGraph(level, state.crates());
        graph.visitLayers(state.workerPos(), layer -> {
            for (int pos : layer.nodes()) {
                for (var dir : Board.ALL_DIRECTIONS) {
                    int crate = level.moveIndex(pos, dir);
                    var newState = state.tryPush(level, crate, dir);
                    if (newState != null) {
                        edges.add(new Edge<>(
                                newState, layer.distance() + 1));
                    }
                }
            }
        });
        return edges;
    }
}

Exercises

[8.7]Describe the game states that are adjacent to node E in the weighted push graph of Fig. 8.6.

8.6 Dijkstra’s Algorithm¶

To find the shortest path in a weighted graph, we can use an algorithm known as Dijkstra’s algorithm, named after the Dutch computer scientist Edsger W. Dijkstra. Dijkstra’s algorithm works similar to breadth-first search: starting at a particular node \(S\) of a weighted graph, it visits all reachable nodes in the order of increasing distance from \(S\).

To illustrate how Dijkstra’s algorithm works, consider the simple weighted graph shown in Fig. 8.7. It’s easy to determine the shortest paths from S to all the other nodes by hand: The shortest path to B is \(\text {S}\to \text {B}\) (length 1), the one to C is \(\text {S}\to \text {B}\to \text {C}\) (length 4), the one to A is \(\text {S}\to \text {B}\to \text {A}\) (length 5), and the one to D is \(\text {S}\to \text {B}\to \text {D}\) (length 6). When traversing this graph starting at S, Dijkstra’s algorithm visits the nodes in this order: S, B, C, A, D.

The main idea behind Dijkstra’s algorithm is to maintain a list of nodes that have already been discovered but still need to be explored in more detail. You will recall that this is the same idea that underlies breadth-first search, but in the absence of edge weights we could simply visit the nodes in the order they were discovered and store the list of unexplored nodes in a queue. This is no longer possible when the edges are weighted because the order in which we discover nodes doesn’t always match the order in which we need to visit them. For example, in Fig. 8.7 node A is discovered immediately since it is a direct neighbor of the starting node S, but it is visited after B and C because it is farther away from S.

We can solve this problem by replacing the queue used in breadth-first search with a list of nodes that we keep sorted by their distance from the start. Figure 8.8 illustrates how we can use such a data structure to traverse the graph from Fig. 8.7. Initially, the list of unexplored nodes contains just the starting node S whose distance is obviously 0. In the first step, we visit S and add its two neighbors to the unexplored list, sorted by their distance from S. In each of the following steps, unexplored is updated by removing the first node and adding all or some of its neighbors. In Step 2 we reach node B, which tells us that that B’s distance from S is 1. Three other nodes are reachable from B: node A at total distance 9, node C at total distance 4, and node D at total distance 6. We discard the new path to A since we already discovered a shorter route in the first step, but we add the new nodes C and D to unexplored. In Step 3 we visit C and discover yet another path that leads to A. This path has a total weight of \(5\) and is therefore shorter than the existing path to A, so we update unexplored with the new distance. The last two steps visit A and D and add no new nodes to unexplored.

The performance of Dijkstra’s algorithm depends on the data structure that is used to store the list of unexplored nodes. The data structure that is most commonly used for this purpose is the priority queue, which associates a numeric priority with every element of the queue. Priority queues provide the following operations:

• • \(\attribir {pq}{isEmpty}()\): Return true if there are no elements in the queue.

• • \(\attribir {pq}{insert}(u, p)\): Add a new element \(u\) with associated priority \(p\) to the queue.

• • \(\attribir {pq}{extractMin}()\): Remove the element with the smallest associated priority from pq and return it.

• • \(\attribir {pq}{decreaseKey}(u, p)\): For an element \(u\) that is already in the queue, reduce its priority to \(p\) and adjust its position in the queue.

Using such a priority queue, we can describe Dijkstra’s algorithm as shown in Algorithm 8.1. We assume that every node has two fields that can be used to store the algorithm’s output: \(n.\Id {dist}\) for the shortest distance from the start \(S\) to \(n\) and \(n.\Id {pred}\) for the predecessor along the shortest path.

At the start of the algorithm, we reset the dist and pred fields of all nodes and then initialize the algorithm by adding \(S\) to the priority queue and setting its dist field to 0. We then repeatedly remove the nearest unexplored node from pq and inspect all its neighbors. For each neighbor \(v\) we distinguish between two conditions. If we haven’t encountered \(v\) before (its dist field is \(\infty \)) we use \(\mathrm {insert}()\) to add it to pq. Otherwise, if the new path to \(v\) via \(u\) is shorter than the one we have found before, we update its dist and pred fields and use \(\mathrm {decreaseKey}()\) to move \(v\) closer to the front of pq.

After the algorithm has finished, we can examine the dist and pred fields to find the shortest path from \(S\) to each node in the graph. If \(n.\Id {dist}\) is \(\infty \), the node hasn’t been reached and no shortest path exists. Otherwise, \(n.\Id {dist}\) is the length of the shortest path, and we can find the nodes on this path by following the pred nodes back to the start.

Implementing Dijkstra’s Algorithm

Let’s now turn to the problem of implementing Dijkstra’s algorithm. Similar to the version of breadth-first search we discussed in Section 7.3, we will store the shortest paths from the starting node as a tree of path segments that link to their predecessors. As before, we define a record that implements the BasicPath interface, but since we are now dealing with paths in a weighted graph, we add a new integer field totalWeight that stores the path’s weighted length from the start. The resulting WeightedPath type is shown in Listing 8.17.

// Data type for representing paths through weighted graphs.
public record WeightedPath<N>(
        N node, WeightedPath<N> predecessor, int totalWeight)
        implements BasicPath<N> {
}

We implement Dijkstra’s algorithm not as a static function but as a class that stores the algorithm’s state in a handful of fields (Listing 8.18):

• • The graph field is the graph that is being traversed.

• • The dist field corresponds to the dist attribute in Algorithm 8.1 and holds the weighted distance of every visited node from the start.

• • The unexplored field replaces the pq data structure in Algorithm 8.1 and maintains a priority queue of incomplete paths that still need to be explored.

• • The result field stores the shortest path to every visited node.

// Implementation of Dijkstra's algorithm for weighted graphs.
public class Dijkstra<N> {
    private final WeightedGraph<N> graph;
    private final Map<N, Integer> dist = new HashMap<>();
    private final PriorityQueue<WeightedPath<N>> unexplored;
    private final Map<N, WeightedPath<N>> result = new HashMap<>();

    // ...
}

The constructor Dijkstra() in Listing 8.19 takes a graph and a starting node as arguments and initializes the algorithm’s data structures. The priority queue for unexplored is initialized using a comparator object that determines how the elements are sorted. Here, the expression

Comparator.comparingInt(WeightedPath::totalWeight)

returns a function that compares two WeightedPath objects by their totalWeight fields, which ensures that the path segment at the front of unexplored is the one with the smallest value of totalWeight. In Algorithm 8.1 we used a loop to reset the dist and pred fields of all nodes before the start of the algorithm; this isn’t necessary here because dist and result are initialized to empty hash tables.

private Dijkstra(WeightedGraph<N> graph, N start) {
    this.graph = graph;
    unexplored = new PriorityQueue<>(
            Comparator.comparingInt(WeightedPath::totalWeight));
    dist.put(start, 0);
    unexplored.add(new WeightedPath<>(start, null, 0));
}

The main part of Dijkstra’s algorithm repeats the following three steps as long as there are entries in unexplored:

• 1. Extract the nearest unexplored node from the queue.

• 2. Check whether it has any undiscovered neighbors or neighbors that can now be reached more quickly.

• 3. Update the priority queue if that’s the case.

These steps are performed by the nextNode() method shown in Listing 8.20. The implementation differs from the description in Algorithm 8.1 in one crucial respect: If a shorter path to a previously discovered node is found (newDist < oldDist), we don’t update the priority of the existing entry in unexplored but instead add a new entry. This change is necessary because the PriorityQueue class doesn’t support the decreaseKey() operation.

// Process and return the nearest unexplored node.
private N nextNode() {
    while (!unexplored.isEmpty()) {
        WeightedPath<N> path = unexplored.remove();
        N node = path.node();
        if (result.putIfAbsent(node, path) != null)
            continue;  // skip nodes that were reached before
        for (var edge : graph.edges(node)) {
            int newDist = path.totalWeight() + edge.weight();
            int oldDist = dist.getOrDefault(edge.target(), -1);
            if (oldDist == -1 || newDist < oldDist) {
                dist.put(edge.target(), newDist);
                unexplored.add(
                        new WeightedPath<>(edge.target(), path,
                                newDist));
            }
        }
        return node;
    }
    return null;
}

As a result, unexplored can now contain multiple paths to the same node. The following if statement at the start of the loop ensures that no node is visited more than once:

if (result.putIfAbsent(node, path) != null)
    continue;  // skip nodes that were reached before

The call to putIfAbsent() stores the shortest path to the current node in result, but only the first time this node is encountered. If result already contains an entry for node, we know that the current path must be longer than the one discovered earlier and ignore it.

Finally, we implement two variations of Dijkstra’s algorithm using nextNode() (Listing 8.21). The first is traverse(), which visits every node that is reachable from start and returns a map that contains the shortest path to each of them. The second method shortestPath() works similarly but uses an additional Predicate to stop at the first node that satisfies a certain condition. The method returns either the path to this node or null if no suitable node was found.

// Visit all nodes reachable from 'start' and return the
// shortest paths.
public static <N> Map<N, WeightedPath<N>> traverse(
        WeightedGraph<N> graph, N start) {
    var dijkstra = new Dijkstra<>(graph, start);
    while (dijkstra.nextNode() != null) {
    }
    return dijkstra.result;
}

// Find the shortest path from 'start' to the nearest node
// that satisfies 'condition'.
public static <N> WeightedPath<N> shortestPath(
        WeightedGraph<N> graph, N start, Predicate<N> condition) {
    var dijkstra = new Dijkstra<>(graph, start);
    while (true) {
        N node = dijkstra.nextNode();
        if (node == null)
            return null;
        if (condition.test(node))
            return dijkstra.result.get(node);
    }
}

Solving Sokoban using the Fewest Steps

With Dijkstra’s algorithm in hand, we can now finally solve our original problem of finding the solution of a given Sokoban level that requires the fewest number of steps. To do this, we first construct the weighted push graph and then search for the shortest path from the starting configuration to any game state that solves the level:

WeightedPath<GameState> path = Dijkstra.shortestPath(
        new WeightedPushGraph(level),
        new GameState(level),
        gameState -> gameState.allCratesOnGoals(level));
System.out.printf("Pushes: %d%n", path.length());
System.out.printf("Steps: %d%n", path.totalWeight());
System.out.println(SokobanSolver.compressMoves(
        SokobanSolver.computeSteps(level, path.toNodeList())));

This outputs the following solution, which requires 230 steps and again 97 pushes — that’s 32 fewer steps than in the solution we found in Section 8.4:

Pushes: 97
Steps: 230
u3l3uLUllDll3dr12R
13lulld14R
7l3ululldDDuull3dr10RurD
7l3ulL3urDDll3Duull3dr10RdRRlU
7l3uL3ull5Duull3dr10RuRRlD
7l3ulLul3Duull3dr10RdRUluR

As before, we have added line breaks to the output to indicate when a crate has reached the goal area. It’s worth trying this solution yourself: Even though most steps are obvious and either move the worker (or a crate) from one side of the level to the other, the final steps on each line, which arrange the crates in the goal area, are surprisingly elegant.

Exercises

[8.8]A square in a Sokoban level is called dead if there is no way to push a crate from this square to any of the goals.

• a) Consider the level shown in Fig. 8.9, which has two goals in the upper right corner. Which squares in this level are dead?

  Figure 8.9. A small level with two goals

• b) Develop an algorithm that computes all dead positions in a Sokoban level.

8.7 Problems¶

Word Ladders

[8.9]A word ladder is a sequence of words of the same length in which each word differs from the last in exactly one letter. For example, the sequence ROCK, SOCK, SICK, SILK, SILD, SOLD, GOLD is a word ladder that connects the words ROCK and GOLD.

To be able to construct word ladders algorithmically, we need access to a dictionary from which we can choose the individual words. We will use the “The UK Advanced Cryptics Dictionary” (UKACD), a list of words compiled by Ross Beresford specifically for crossword puzzles and other word games. The word list can be found in the data/UKACD17 folder at

• a) Write a function that reads all \(n\)-letter words from the UKACD and returns a list of Strings. Dictionary entries that consist of multiple words or contain non-alphabetic and foreign characters should be filtered out.

For a given set of words \(W\), we can construct a graph by interpreting each word as a node and connecting two words with an edge if they differ in exactly one letter. We call the result the word-ladder graph for \(W\); for obvious reasons, every path in this graph is a word ladder. The main problem when working with word-ladder graphs is computing the neighbors of a given node \(n\). The naive solution is to it iterate over all words in \(W\) and select those that differ from \(n\) in a single letter, but having to do this repeatedly while traversing the graph is painfully slow.

A better alternative is to construct an auxiliary data structure that helps us find words that are similar to each other. To see how this can be done, let’s consider a simplified example first. We know that all neighbors of ROCK differ in exactly one letter so they must have the form *OCK, R*CK, RO*K, or ROC*. We can therefore prepare four “buckets” labeled OCK, RCK, ROK, and ROC and place all four-letter words that contain those three letters in the same order into the corresponding bucket:

Each bucket contains potential neighbors, and the four buckets together are guaranteed to contain every neighbor of ROCK. Finding all neighbors of ROCK is a simple matter of iterating over the words in those four buckets and collecting those that that differ from ROCK in exactly one letter.

• b) Which buckets do you have to check to find all neighbors of HAPPY and HARPY?

Now consider the outline of a class for finding similar words shown in Listing 8.22. The field buckets maps keys of type String to sets of words. Each entry of buckets represent a bucket as described above. The constructor takes a list of words and adds them to the data structure. To complete this class, we need to implement two methods. The first method addWord() takes a single word and adds it to all buckets it belongs to. The second method findSimilarWords() takes a word and returns all entries in the data structure that differ from word in a single letter.

public class SimilarWords {
    private final Map<String, Set<String>> buckets = new HashMap<>();

    public SimilarWords(Collection<String> words) {
        for (String w : words)
            addWord(w);
    }

    public void addWord(String word) {
        // ...
    }

    public List<String> findSimilarWords(String word) {
        // ...
    }
}

• c) Implement addWord() and findSimilarWords().

• d) Write a class for representing word-ladder graphs. The nodes of the graph are strings of a certain length, and two nodes are mututal neighbors if their strings differ in exactly one character.

• e) What is the shortest word ladder that transforms ROCK into GOLD? Are there any four-letter words that cannot be transformed into GOLD? Which word is hardest to transform into GOLD?

• f) What is the longest word ladder between a pair of four-letter words? What seven-letter words can be transformed into their reverse?

Lasers and Mirrrors

[8.10]A popular type of puzzle that can be found in many computer games asks the player to manipulate one or more light rays, either by blocking them with obstacles or by redirecting them with mirrors. In this exercise, we will simulate the propagation of light rays on a board consisting of \(w\times h\) squares. A square on the board is either empty or it contains an object that emits a beam of light or interacts with incoming light. There are four kinds of objects, and each interacts differently with incoming light:

• • Obstacles () block all incoming light.

• • Emitters () block incoming light but emit light in a fixed direction.

• • Opaque mirrors () reflect or block incoming light, depending on the mirror’s orientation relative to the light ray.

• • Semi-transparent mirrors () reflect, block, or transmit incoming light, depending on the mirror’s orientation relative to the light ray.

Mirrors can have four different orientations. The following diagram shows how diagonal and horizontal mirrors reflect light:

In the diagonal orientation, the mirror reflects incoming light at a 90 degree angle, and in the horizontal orientation, it reflects only light that hits the mirror itself but not its side. Semi-transparent mirrors behave similarly but also transmit the incoming light:

Diagrams for the remaining two orientations can be obtained by rotating the pictures by 90 degrees.

Figure 8.10 shows a simple scene that consists of a single emitter pointing downwards, four mirrors in different orientations, and one obstacle that blocks all incoming light. All squares outside the scene are considered obstacles, so only the propagation of light inside the rectangle must be considered. Starting at the emitter in the upper-left corner, the beam first moves downward until it hits the semi-transparent mirror, where it is refracted into two beams: one beam that continues downward until it is stopped by the outer wall of the scene, and one that advances to the right, where it is reflected upward.

• a) Sketch the final distribution of light for the scene in Fig. 8.10.

• b) Design classes for modeling individual objects and their behavior, most importantly the way they emit and reflect light.

• c) Write a program that simulates the propagation of light rays through the scene.

Path Finding

[8.11]Finding the shortest path between two locations is a common problem in many computer games. In this exercise, we will consider the problem of planning the movement of units in strategy games such as Civilization.

Figure 8.11 illustrates the kind of map that is used in such games. Units can traverse the board by moving between adjacent tiles, but the cost of movement depends on the underlying terrain. For instance, it is easier (and cheaper) to traverse grasslands than woods, mountains are impassable, and there is a special penalty for entering water tiles. More specifically, we model the cost of movement using the following rules:

• • Mountain tiles are impassable.

• • Entering forest tiles costs 2 movement points.

• • Entering grassland tiles costs 1 movement point.

• • Entering water tiles from land costs 3 movement points.

• • Moving between water tiles costs 1 movement point.

The goal is to find the path between two tiles with the lowest overall cost.

• a) Explain how to construct a weighted graph that can be used to model and solve this problem.

• b) Use Dijkstra’s algorithm to compute the length of the shortest path from G2 to every position on the board in Fig. 8.11. What is the shortest route to M7?

8.8 Chapter Notes¶

Dijkstra’s algorithm was invented by the Dutch computer scientist Edsger W. Dijkstra [30]; it is discussed in many books on algorithms and data structures [86, 25]. The performance of Dijkstra’s algorithm is strongly influenced by the data structure that is used to maintain the list of unexplored nodes. In many practical applications, binary heaps offer a good trade-off between performance and simplicity; this is also the data structure that underlies Java’s PriorityQueue class. Other data structures such as Fibonacci heaps offer better performance in certain situations [64].

The A* algorithm is an important generalization of Dijkstra’s algorithm that is widely used for path finding in robotics, video games, and navigation systems [47]. Its main improvement is to use geometric information to prioritize paths that move towards the destination. A visual guide to the A* algorithm can be found at https://www.redblobgames.com/pathfinding/a-star/introduction.html.

Sokoban is not an easy problem for computers to solve; in fact, it can be shown that it belongs to a class of computational problems that are notoriously difficult. This result belongs to the field of complexity theory, a branch of theoretical computer science that studies the difficulty of solving certain problems algorithmically and why some problems seem to be much more difficult than others [89]. The problems are usually stated as decision problems, that is, as questions that can be answered with a simple yes or no. “Is this integer even?” and “is this array of numbers in sorted order?” are two examples of relatively simple decision problems. Many games and puzzles can also be stated as decision problems: “does the die-hard problem have a solution” or “can a given Sokoban level be solved in at most \(k\) moves” are two examples.

All decision problems for which efficient algorithms are known are grouped into a complexity class called P. The “P” stands for polynomial time and indicates that the number of computational steps required by these algorithms grows slowly — like a polynomial — with the size of the problem. Problems for which no polynomial-time algorithms are known are grouped into several other complexity classes such as NP, PSPACE, or EXPTIME, depending on their difficulty. It turns out that many games and puzzles, including Sokoban and chess, belong to these classes — in other words, many puzzles that humans find challenging are challenging for computers as well [49]. In the case of Sokoban, it can be shown that it belongs to the hardest problems in the PSPACE class, the so-called PSPACE-complete problems [27]. To this day, no efficient algorithms for PSPACE-complete problems have been found, and most computer scientists believe they simply do not exist.

This result must be taken with a grain of salt, however. Computational complexity only tells us how difficult a problem is (a) in the worst case and (b) for large instances of the problem. In practice, the fact that Sokoban is PSPACE-complete means that there are some levels that any Sokoban solver will struggle with, regardless of how smart or advanced it is, but it doesn’t mean that all levels are difficult. In fact, most human-designed Sokoban levels can be solved with reasonable efficiency, even though the algorithms required are significantly more sophisticated than the ones we discussed in this chapter. Some of these algorithms are discussed in the thesis by Junghanns [56]; another great resource is the Sokoban Wiki [91].