Name
Abstract | ||
|---|---|---|
Abstract We prove that a pushing - block puzzle called PushPush - k is Pspace - complete for any xed k 1 In this puzzle, a robot moves on a nite grid Each grid position is either empty or occupied by a single obstacle block While moving, the robot may push obstacle blocks in direction of its movement, subject to certain constraints In particular, once an obstacle block starts moving, it continues to do so until it hits another obstacle or the grid boundary The problem is to decide whether the robot can navigate from a given start position to a speci ed goal position on the grid |
Year | Venue | Field |
|---|---|---|
2002 | CCCG | Discrete mathematics,Combinatorics,Computer science,PSPACE-complete |
DocType | Citations | PageRank |
Conference | 9 | 0.75 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erik D. Demaine | 1 | 4624 | 388.59 |
| Robert A. Hearn | 2 | 169 | 20.52 |
| Michael Hoffmann | 3 | 227 | 22.74 |