| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 435416 | Theoretical Computer Science | 2016 | 11 Pages |
Abstract
In this paper we study the computational complexity of a generalized version of the logic puzzle Pete's Pike by Thinkfun [14]. It is shown that generalized Pete's Pike is PSPACE-complete. Moreover, we construct an infinite family of initial configurations with the property that the length of a shortest solution is superpolynomial in the size of the game.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bernd Meyer,