2
$\begingroup$

I've been looking at a few entries in http://library.msri.org/books/Book56/files/10demaine.pdf (on combinatorial algorithmic game theory). I didn't see the following game listed there, and I want to know if it has a name, and whether it's computational complexity has been studied:

A block sits on a starting position in a room containing a bunch of blocks, and an exterior agent can slide the block in any one of four directions (N, S, E, W). When it's moved, it slides in that direction until it is stopped by hitting a wall or a block.

For an illustration (not the sharpest, but the first I could find on Google), a student designed this game in the Scratch programming language: http://scratch.mit.edu/projects/StrykerV/1466085.

Specifically, I want to know if this game is NP-hard or PSPACE-complete. It seems that it should be, since it is similar to PushPush-1, but perhaps having only one moving piece makes it easier.

$\endgroup$
4
$\begingroup$

There are no sliding blocks, so the game is in $P$

Informally: from the starting position just mark the cells reachable by the cursor. The level has a solution iif the final position becomes reachable.

The algorithm is similar to the Dijkstra's algorithm for shortest path applied to the graph derived from the level.

For example:

level

For an $n \times n$ level the complexity is $O(n^4)$.

Let me know if you need further details.

$\endgroup$
  • $\begingroup$ Good point. Stupid question. $\endgroup$ – Jeremy Kun Mar 22 '12 at 23:18
  • $\begingroup$ I think the question can be transformed to a very tricky one if you modify the rules: when the cursor hits a block the block just shift 1 position up/down/left/right (if there is a space for the shift). When the cursor moves away, the block stays there for a fixed amount of time, then it returns to its original position (like a rubber band) .... whow ... I just invented a new game :-) :-) $\endgroup$ – Marzio De Biasi Mar 22 '12 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.