Motion planning with pull moves

Abstract

It is well known that Sokoban is PSPACE-complete (Culberson 1998) and several of its variants are NP-hard (Demaine et al. 2003). In this paper we prove the NP-hardness of some variants of Sokoban where the warehouse keeper can only pull boxes.

9 pages, 7 figures

References in corpus (1)

• PushPush is NP-hard in 3D

Cited by in corpus (2)

• PSPACE-completeness of Pulling Blocks to Reach a Goal
• A handle is enough for a hard game of Pull