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

 

The Planar Crossover Construction

The planar crossover device is illustrated in figure 9.

This is by far the most complex device of the construction. The basic properties are that the device is initially in the solved state, that any passage through the device may leave it in the solved state, and that if entry is at A then the only feasible exit is at A' while if entry is at B then the only feasible exit is at B'.

Note that the device is directional since no entry can be forced at either A' or B'. This means that to build the TM emulator, each circle in figure 6 may require either one, two or four of these devices suitably rotated and reflected, depending on whether the intersecting passages are uni-directional or bi-directional.

To discuss the device, it has been broken into three subdevices. Two of these, device 2 and device 3, are essentially the same device under rotation. While discussing these devices, we will not consider infeasible moves of the pusher, that is those which clearly leave a box or boxes in unrecoverable positions.

 figure274
Figure 7: Subdevice One 

The first of these devices is shown somewhat compressed in figure 7. Its purpose is to force the pusher to move the box in the Lock to block the path from B to B', whenever the pusher enters at A.

Clearly the only feasible path requires the pusher to enter the Interlock. This device is an extension of the reverser. The pusher must move each box one push downwards (i.e. towards A') and exit the Interlock at the top. However, the pusher cannot exit immediately at A', since to do so would force two boxes together in an unrecoverable configuration.

The pusher may move the box in the Lock one step to the right, then return through the Interlock and re-enter the Lock from the top. An exit at A' will now be feasible, restoring the last box in the Interlock, and all boxes in this subdevice except the one in the Lock will be in storage locations. This last box may be stored while the pusher is passing through subdevice three.

 figure282
Figure 8: Subdevice Two 

Subdevice Two is illustrated in figure 8.

If entry to this device is from A then the B' exit has been blocked by passage through device one, so the only feasible exit is through A'. The only feasible path requires one box (on the far right) to be moved in the Interlock, which can be restored before leaving the subdevice by entering the Interlock through the Forward Reset Entrance.

We now consider other paths available on entry at A, and show they are not feasible. As discussed in the next paragraph when considering entrance at B, it is not feasible to enter through the Lock Reset Entrance and try to exit at A', because the two rightmost boxes in the Interlock will be left adjacent. For similar reasons entering the Interlock at the Forward Reset Entrance and circling back through the Lock and exiting at A' is also infeasible. Entering the Interlock through the Forward Reset Entrance and exiting the Interlock via the Lock Reset Entrance is impossible. These exhaust the possibilities when entering at A.

When entering at B, the pusher encounters the box in the Lock, which must be moved two cells blocking the path to A'. The only feasible path takes the pusher to the junction of the Lock Reset Entrance. The pusher now enters the Interlock through this reverser.gif By pushing each box in the Interlock except the rightmost one step to the right, the pusher may exit the Interlock to the Lock and restore the box to its solved position. The pusher cannot now exit through A' because to do so he would push the rightmost box of the Interlock against the next box in the Interlock, thus creating an unrecoverable configuration. The only way to restore the boxes inside the Interlock is to return through the Interlock, and then exit through the Lock Reset Entrance, and then perforce to exit at B'.

Thus, entering at A forces an exit at A', while entrance at B forces an exit at B'. In each case, all boxes are returned to storage locations.

The third subdevice is the same as subdevice two. Before exiting at A' (in figure 9) it allows restoring the box in the Lock in subdevice one, without allowing an exit at B'.

We have shown that the planar crossover device in figure 9 fulfills its function. Namely, entry at A requires exit at A', while entry at B requires exit at B', and all boxes in the device remain in storage locations after either passage.

 figure293
Figure 9: Planar Crossover 


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

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