Pushing Blocks in Gravity is NP-Hard

Erich Friedman
Stetson University, DeLand, FL 32723
efriedma@stetson.edu

Introduction

There has been much progress recently showing that certain classes of puzzles involving pushing blocks [2, 3, 4, 10] are NP-hard. For example, consider the block pushing puzzle Push-k which consists of movable unit square blocks on an integer lattice, and a robot that can move horizontally and vertically to attempt to reach a specified lattice position. The robot can push k blocks provided it pushes them to open squares. In [4], the authors prove that Push-k is NP-hard using a reduction from the 3-coloring of planar graphs. That is, for a given planar graph, they build a Push-k puzzle that can be solved if and only if the vertices of the original graph can be 3-colored. As 3-colorability is NP-hard [9], so is Push-k.

Their construction depends on the existence of four gadgets: a One-Way gadget that can only passed in one direction, a Fork gadget that allows only one of several exits to be used, an XOR Crossing gadget which allows possible passageways to cross provided that only one of these is used, and a NAND Non-Crossing gadget which allow only one of two nearby non-crossing passageways to be used. Any block puzzle that contains examples of these gadgets can be proved to be NP-hard by imitatating their proof.

We consider the block pushing puzzle called Push-1-G (the G stands for gravity) in which the robot can push only one block, and blocks that are directly over one or more open squares, fall immediately downward as far as possible. The robot is not afected by gravity. Push-1-G is fairly boring when all blocks are pushable, since all the blocks will always be in stacks at the bottom of the puzzle, so we allow the existence of fixed (non-pushable) blocks. We will use the fixed blocks to build passageways in which the robot must navigate.

An example of a simple Push-1-G puzzle is shown in Figure 1. The robot starts at S and finishes at F. The dark squares are fixed blocks, the light squares are pushable blocks, and the white squares are open. We will construct the required gadgets for Push-1-G, showing that Push-1-G puzzles are NP-hard. Since Goldpusher [8] is a subset of Push-1-G, Goldpusher is also NP-hard. All our gadgets are easily generalized to show that Push-k-G is NP-hard for general k.

Figure 1. A Push-1-G puzzle

Gadgets

Our One-Way gadget is shown in Figure 2. The robot can only move from left to right. We abbreviate a One-Way gadget with an arrow in a passageway.

Figure 2. One-way gadget

Our Fork gadget is shown in Figure 3. The robot can only enter at the bottom, and can only proceed by pushing one of the blocks to enter one of the passageways, but this blocks the other passageway. The Fork gadget for Push-k-G uses 2 groups of k blocks separated by one open square.

Figure 3. Fork gadget

Our XOR Crossing gadget is shown in Figure 4. The robot enters from one of the passageways on the left, pushes a block which blocks one of the passageways, and exits on the right. We abbreviate an XOR Crossing gadget with an X at the intersection of two passageways.

Figure 4. XOR Crossing gadget

Our NAND Non-crossing gadget is shown in Figure 5. The robot can only pass through one of the two passageways.

Figure 5. NAND Non-Crossing gadget

References

[1] D. Bremner, J. O'Rourke, and T. Shermer, "Motion Planning amidst movable square blocks is PSPACE complete". preprint, 1994.
[2] J. Culberson, "Sokoban is PSPACE complete." Proc. Internet Conf. Fun with Algorithms (1998), N. S. E. Lodi, L. Pagli, Ed., Carelton Scientific, 65-76.
[3] E. D. Demaine, M. L. Demaine, and J. O'Rourke, "PushPush and Push-1 are NP-hard in 2D". Proc. 12th Canad. Conf. Comput. Geom. (2000), 211-219.
[4] E. D. Demaine and M. Hoffman, "Pushing blocks is NP-complete for non-crossing solution paths". Proc. 13th Canad. Conf. Comput. Geom. (2001), 65-68.
[5] A. Dhagat and J. O'Rourke, "Motion planning amongst movable square blocks". Proc. 4th Canad. Conf. Comput. Geom. (1992), 188-191.
[6] D. Dor and U. Zwick, "Sokoban and other planning problems". Computational Geometry: Theory and Applications 13, 4 (1999), 215-228.
[7] E. Friedman, "Cubic is NP-complete". preprint.
[8] E. Friedman, D. Vree, and W. Vree, Goldpusher Page (http://www.tbm.tudelft.nl/webstaf/wimvr/gold-pusher.html)
[9] M.R. Garey and D.S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
[10] M. Hoffman, "Push-* is NP-hard". Proc. 12th Canad. Conf. Comput. Geom. (2000), 205-210.