next up previous
Next: The Turing Machine Emulator Up: Sokoban is PSPACE-complete Previous: Introduction

Basic Forbidden Configurations and Elementary Devices

As with most such arguments, the emulator constructed in this paper will rely on a number of devices with special properties.

First is the notion of an unrecoverable configuration. A set of boxes in certain locations is said to be an unrecoverable configuration if no possible move sequence exists to move all the boxes in the set to storage locations. Note in general that we will use this term to discuss small subsets of the puzzle construction.

 figure207
Figure 1: Unrecoverable Configurations, (a), (b) and (c) 

For example, in figure 1(a) it is not possible to restore the box to its only possible storage location indicated by the shaded area just above it.

Similarly, in figure 1(b) and (c) we see two configurations of two boxes that cannot be moved, and are not in their final destinations. These and similar configurations will be used frequently to limit the possible moves of the pusher in our construction.

Clearly, if at some time a puzzle contains an unrecoverable subset, then the puzzle has no solution from that configuration. In our arguments, we make frequent claims such as ``the pusher can only traverse the device in one direction''. More formally, this means that doing forbidden moves is either impossible, or would leave the boxes in the device in an unrecoverable configuration. We will refer to move sequences that leave a subset of the puzzle in an unrecoverable configuration as infeasible.

The first device we consider is the one-way, or directed passage device. This device was used by Steven Sabey[4] to show that it is NP-hard to minimize the number of pushes required to solve (a version of) this problem.

 figure222
Figure 2: One Way Device 

As its name suggests, the one-way device shown in figure 2 has the property that the pusher can move from A to B as often as the device is reached, always leaving the box in the same storage location. However, it is not possible to move from B to A without pushing the box into a location such that it is not recoverable. It is also not possible to remove the box from the device. This device is quite simple and we leave the reader to convince herself of these properties.

 figure230
Figure 3: Reverser 

The reverser shown in figure 3 in its solved state on the left (i.e. when the boxes are in the storage locations) will allow the pusher to pass from A to B. However, it is easy to see that this traversal will either leave the device in its unsolved state, as shown on the right, or will leave the device in an unrecoverable state.

To restore the device the pusher must re-enter at B and exit at A. Thus, every passage through the device will have to be paired with one in the opposite direction. To solve the puzzle, the last passage must be from B to A.

 figure238
Figure 4: Pass-Reset 

The pass-reset device is shown in two configurations in figure 4. The arrows at A and B indicate that there are one-way devices located at the entrance and exit of the device, restricting the pusher's direction of travel as indicated. These simplify the arguments about the properties of the device, since they prevent entry at B or egress at A. Also, note that the bottom of the device is a reverser.

When in its solved (or closed) configuration, as on the left, it is not feasible to enter at A and exit the device. We remind the reader that by ``not feasible'' we mean it is either impossible, such as exiting through R, or would leave the device in an unrecoverable configuration. For example, an entry at A, followed by a single push of the first box encountered against the next one, followed by a detour around the boxes and egress at B would leave the two boxes adjacent on a wall, one of the unrecoverable configurations shown in figure 1.

Thus, the only feasible entry into the device when in the solved configuration is through the reverser via entry point R. This allows resetting the device as shown on the right. Once reset, egress can only be through R as demonstrated in the next paragraph. On a subsequent arrival at A the pusher may pass through the device, exiting at B and perforce putting the device into the solved state on the left of the figure. To do this the pusher would push the first box encountered one step to the left, then go around it and push it back, then push the exit box one step to the right (so both boxes are in storage locations) and exit through B.

Finally, we must verify that it is not feasible for the pusher to enter at R and exit at B. If the pusher enters at R and exits at B, then the device cannot be successfully entered again. The pusher cannot enter at R because the reverser will be in its alternate position. This also means that the device is in an unsolved state. Entry at B is forbidden by the one way device, and since the exit was through B the leftmost upper box must be in its storage position (if the device has not already been rendered unrecoverable). This means we cannot enter at A, since the only way to enter would push the two upper boxes together. Now since the pusher cannot feasibly enter the device again, and the reverser is in the unsolved state, this passage leaves the device in an unrecoverable state.

 figure253
Figure 5: Device Icons 

In figure 5 we show icons for the devices we need. The pass-reset device may be oriented either way; arrows indicating direction will be added in the final construction. We will discuss the planar crossover device in section 4. For now the reader may imagine a simple underpass, requiring the puzzles to be in three dimensions (but only two levels). The key idea is that the pusher may pass straight through the device, but not make a turn. Junctions are easily implemented as halls with passages leading off.


next up previous
Next: The Turing Machine Emulator Up: Sokoban is PSPACE-complete Previous: Introduction

& Culberson
Thu Apr 3 11:48:56 MST 1997