next up previous
Next: Basic Forbidden Configurations and Up: Sokoban is PSPACE-complete Previous: Sokoban is PSPACE-complete

Introduction

Sokoban is a puzzle game that can be found at various sites on the Internet [2, 3, 5], and through commercial vendors. If sources are correct, Sokoban is Japanese for warehouse person. We will refer to this person as ``the pusher''.

The game consists of the pusher who must push a number of boxes into a set of designated storage locations, without getting himself or the boxes stuck. The warehouse is a set of barriers, passages and storage areas. All elements are aligned in a two dimensional grid. The tricky part is that the pusher may only push one box at a time, cannot pull a box, and cannot occupy the same grid location as a box or barrier. Thus, pushing a box into a corner or allowing two boxes to come together on a wall means those boxes cannot be moved further. A puzzle is considered solved if all boxes are pushed into storage locations. The number of storage locations is equal to the number of boxes. Any box may occupy any storage location, (the locations and boxes are unlabeled), although our constructions are such that there is usually only one feasible location for each box.

In this paper we show that we can emulate a Turing Machine (TM) in linear time using an infinite version of the puzzle in which only a finite number of containers are initially out of storage. Restricting the tape to finite length (linear bounded automata) shows that finite puzzles are PSPACE hard. Since the problem is in PSPACE [1], this means the puzzles are PSPACE complete, solving the open problem posed by Dorit and Zwick[1]. We refer the reader to this paper for a summary of related research. Unlike the proof of PSPACE-completeness of SOKOBANtex2html_wrap_inline730 presented in [1], our constructions rely critically on the the fact that each of the boxes must be placed in a storage location.

Most of the constructions used in this paper are not much like those in the popular games. In any solution sequence in our constructions, the boxes never stray more than one or two pushes away from the storage location they must eventually occupy in the solution state. The designs are adapted to the goal of restricting the movements of the pusher. This is different in flavor from the design patterns of popular versions, where usually boxes are scattered but must be moved some distance to one of several contiguous sets of storage locations.

Throughout this paper, diagrams will be used to represent constructions. The pusher will be represented by a man-like figure, boxes will be represented by a circle. Filled circles will represent boxes that are in storage locations, while empty circles will represent boxes not in storage locations.


next up previous
Next: Basic Forbidden Configurations and Up: Sokoban is PSPACE-complete Previous: Sokoban is PSPACE-complete

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