<p>There are no sliding blocks, so the game is in $P$</p>

<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. </p>

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

<p>For example:</p>

<p><img src="https://i.sstatic.net/Pliy2.jpg" alt="level"></p>

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

<p>Let me know if you need further details.</p>

CC BY-SA 3.0
2012-03-22T23:18:10.653Z
Good point. Stupid question.
Jeremy Kun
CC BY-SA 3.0
2012-03-22T23:45:28.577Z
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 :-) :-)
Marzio De Biasi
CC BY-SA 3.0
2012-03-22T23:13:32.640Z
2012-03-22T23:32:15.520Z
2012-03-22T23:32:15.520Z
Marzio De Biasi
<p>I've been looking at a few entries in <a href="http://library.msri.org/books/Book56/files/10demaine.pdf" rel="nofollow">http://library.msri.org/books/Book56/files/10demaine.pdf</a> (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:</p>

<p>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.</p>

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

<p>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.</p>

<cc.complexity-theory><np-hardness><combinatorial-game-theory>
What is the known complexity of this game? (similar to PushPush-1)
Jeremy Kun
# What is the known complexity of this game? (similar to PushPush-1)

(Asked by: username_0 on 2012-03-22)

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.

**Tags:** cc.complexity-theory, np-hardness, combinatorial-game-theory

---

## 1 answers

### Answer by username_1 on 2012-03-22. Score: 4 | Accepted answer

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](https://i.sstatic.net/Pliy2.jpg)

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

Let me know if you need further details.

> **Comments:**
> **username_0**: Good point. Stupid question.  
> **username_1**: 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 :-) :-)  

---

