<p>Moving a snake from one position to some other is PSPACE complete.
Snake is trivially in PSPACE.
We give a PSPACE hardness reduction from Hearn's Nondeterministic Constraint Logic.</p>

<h2>Nondeterministic Constraint Logic</h2>

<p>Let a <em>constraint graph</em> be a directed graph with edges of weight $1$ and $2$, such that every vertex has incoming weight $\geq 2$.
Given two constraint graphs, it is PSPACE hard to transform one into the other by reversing edges, one at a time, keeping the incoming weight of each vertex $\geq 2$.
This still holds if the graph is planar and each vertex has degree $3$, and either $1$ or all $3$ of its edges have weight $2$.
The former type of vertex is called And and the latter is called Or (see figure).
<img src="https://i.sstatic.net/3d1Xr.png" alt="NCL gadgets"></p>

<h2>Snake</h2>

<p>In our construction, the snake's head will be chasing its tail at some small distance and will be forced to repeat the same cycle with minor modifications.
We embed each edge of the constraint graph as in the figure (edges shown in red), where we indicate the position of the snake by thick lines.
An edge has two sides (vertices) and the snake takes the central route at the vertex to which the edge is directed.
<img src="https://i.sstatic.net/N67Ih.png" alt="Reversing an edge"></p>

<p>To reverse an edge, the snake first clears the center route and then takes the center route once its head reaches the opposite vertex.</p>

<p>We embed vertices of the constraint graph as shown below, where each of the three colored parts is a half of an edge gadget shown above. The points where the edges touch make sure that the incoming weight of each vertex is at least $2$ by forcing the snake to take the center route of some edge gadgets.</p>

<p><img src="https://i.sstatic.net/D4nkW.png" alt="Snake And">
<img src="https://i.sstatic.net/vvLEk.png" alt="Snake Or"></p>

<p>Finally, the black lines of all edge gadgets are connected to form a single cycle, so the head of the snake chases its tail.
If between two edge gadgets, we make the black path sufficiently long, the snake must always traverse the black paths in the same cyclic order.</p>

<p>To show that the black paths can always be constructed in a planar manner, consider a spanning subtree (thick edges in the figure below) of the constraint graph.
Then we can make black edges follow this tree as illustrated below, resulting in a planar graph.</p>

<p><img src="https://i.sstatic.net/oUjz8.png" alt="Spanning Subtree">
<img src="https://i.sstatic.net/SxCqj.png" alt="Planar Cycle"></p>

<p>The target position of the snake can be derived by the same transformation.
Hence, reconfiguring a snake is PSPACE complete, even on planar graphs.</p>

CC BY-SA 3.0
2015-01-21T21:24:29.360Z
Great! :-) :-) :-)
Marzio De Biasi
CC BY-SA 3.0
2015-01-17T11:40:08.737Z
2015-01-21T17:54:02.787Z
2015-01-21T17:54:02.787Z
Tim
<p>While writing a small post on the complexity of the videogames <a href="http://en.wikipedia.org/wiki/Nibbler" rel="nofollow noreferrer">Nibbler</a> and <a href="http://en.wikipedia.org/wiki/Snake_%28video_game%29" rel="nofollow noreferrer">Snake</a>; I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such problems have not been well studied in the motion planning area (imagine for example a chain of linked carriages or robots). The games are well known, however this is a short description of the related reconfiguration model:</p>

<p>SNAKE PROBLEM</p>

<p><strong>Input</strong>: given a planar graph $G = (V,E)$, $l$ pebbles $p_1,...,p_l$ are placed on nodes $u_1,...,u_l$ that form a simple path. The pebbles represent the <strong>snake</strong>, and the first one $p_1$ is his head. The head can be moved from its current position to an adjacent free node, and the body follows it. Some nodes are marked with a dot; when the head reaches a node with a dot, the body will increase by $e$ pebbles in the following $e$ moves of the head. The dot on the node is deleted after the traversal of the snake.</p>

<p><strong>Problem</strong>: We ask if the snake can be moved along the graph and reach a <em>target configuration</em> $T$ where the target configuration is the full description of the snake position, i.e. the position of the pebbles. </p>

<p>It is easy to prove that the SNAKE problem is NP-hard on planar graphs of max degree 3 even if no dots are used and also on SOLID grid graphs if we can use an arbitrary number of dots. Things get complicated on solid grid graphs without dots (it is related to another open problem).</p>

<blockquote>
  <p>I would like to know if the problem has been studied under another name.<br>
  <s>and, in particular, if there is a proof that it is in NP ...</s></p>
</blockquote>

<p><strong>Edit:</strong> the problem turned out to be PSPACE-complete even on planar graphs and the result seems very interesting, so it remains to find out if it is a new problem
and if there are known results about it.</p>

<p><img src="https://i.sstatic.net/nU00q.png" alt="enter image description here"><br>
A simple example (pebbles are shown in green, the snake's head is P1).</p>

CC BY-SA 3.0
2014-12-17T08:46:20.637Z
Whether the problem is in $NP$ can't have anything to do with whether pebbles are allowed or not: if the Snake Problem without pebbles is in $NP$, then so is the Snake Problem with pebbles, since as a certificate we can specify in what order the dots are picked up, the state of the snake just before it reaches a dot, and in the $e$ states after picking up the dot. Under the assumption that Snake Problem without pebbles is in $NP$, there exists a certificate that tells us how to do the moves "in between".
Tom van der Zanden
CC BY-SA 3.0
2014-12-17T09:51:48.107Z
Can you provide a better and clear definition for target configuration? e.g what do you mean by full description of snake position?
Saeed
CC BY-SA 3.0
2014-12-17T09:57:51.587Z
@Saeed: the target configuration is simply the final positions of the pebbles (i.e. the snake). I'll add a figure to clarify the problem.
Marzio De Biasi
CC BY-SA 3.0
2014-12-17T10:06:20.563Z
Your question was clear enough, but I got the terminology mixed up in my comment. It should read "dots" everywhere instead of "pebbles".
Tom van der Zanden
CC BY-SA 3.0
2014-12-17T10:42:49.390Z
@TomvanderZanden: ok thanks, I agree with you (see also my comment to Zimmux's answer). I wrote "... with or without dots ..." to say that they are irrelevant; but it was not clear enough; so I edited the question and made it more explicit.
Marzio De Biasi
CC BY-SA 3.0
2014-12-17T14:38:53.473Z
Marzio this was simply possible to guess but when you are talking about position of the head that I naturally expect to have it already in the final position (with respect to pebble sequence), made it unclear for me, if you mean something else (well the picture is nice but doesn't add any extra information, anyhow my ambiguities resolved).
Saeed
CC BY-SA 3.0
2014-12-17T15:57:04.623Z
@Saeed: I only cited several ways in which the target configuration can be defined (according to some variations of the game). I'm actually interested in the full final configuration of the pebbles (discard "head position", and the "remaining dots"). I'll clarify it!
Marzio De Biasi
CC BY-SA 3.0
2014-12-17T16:30:06.780Z
I read all of them as a(lmost) same thing (in fact first one admits all others but not the other way around). But right now it's quite clear ;-)
Saeed
<cc.complexity-theory><reference-request><np-hardness><planar-graphs>
"Snake" reconfiguration problem
Marzio De Biasi
# "Snake" reconfiguration problem

(Asked by: username_0 on 2014-12-16)

While writing a small post on the complexity of the videogames [Nibbler](http://en.wikipedia.org/wiki/Nibbler) and [Snake](http://en.wikipedia.org/wiki/Snake_%28video_game%29); I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such problems have not been well studied in the motion planning area (imagine for example a chain of linked carriages or robots). The games are well known, however this is a short description of the related reconfiguration model:

SNAKE PROBLEM

**Input**: given a planar graph $G = (V,E)$, $l$ pebbles $p\_1,...,p\_l$ are placed on nodes $u\_1,...,u\_l$ that form a simple path. The pebbles represent the **snake**, and the first one $p\_1$ is his head. The head can be moved from its current position to an adjacent free node, and the body follows it. Some nodes are marked with a dot; when the head reaches a node with a dot, the body will increase by $e$ pebbles in the following $e$ moves of the head. The dot on the node is deleted after the traversal of the snake.

**Problem**: We ask if the snake can be moved along the graph and reach a *target configuration* $T$ where the target configuration is the full description of the snake position, i.e. the position of the pebbles.

It is easy to prove that the SNAKE problem is NP-hard on planar graphs of max degree 3 even if no dots are used and also on SOLID grid graphs if we can use an arbitrary number of dots. Things get complicated on solid grid graphs without dots (it is related to another open problem).

> I would like to know if the problem has been studied under another name.  
> ~~and, in particular, if there is a proof that it is in NP ...~~

**Edit:** the problem turned out to be PSPACE-complete even on planar graphs and the result seems very interesting, so it remains to find out if it is a new problem
and if there are known results about it.

![enter image description here](https://i.sstatic.net/nU00q.png)  
A simple example (pebbles are shown in green, the snake's head is P1).

**Tags:** cc.complexity-theory, reference-request, np-hardness, planar-graphs
> **Comments:**
> **username_1**: Whether the problem is in $NP$ can't have anything to do with whether pebbles are allowed or not: if the Snake Problem without pebbles is in $NP$, then so is the Snake Problem with pebbles, since as a certificate we can specify in what order the dots are picked up, the state of the snake just before it reaches a dot, and in the $e$ states after picking up the dot. Under the assumption that Snake Problem without pebbles is in $NP$, there exists a certificate that tells us how to do the moves "in between".  
> **username_2**: Can you provide a better and clear definition for target configuration? e.g what do you mean by full description of snake position?  
> **username_0**: @Saeed: the target configuration is simply the final positions of the pebbles (i.e. the snake). I'll add a figure to clarify the problem.  
> **username_1**: Your question was clear enough, but I got the terminology mixed up in my comment. It should read "dots" everywhere instead of "pebbles".  
> **username_0**: @TomvanderZanden: ok thanks, I agree with you (see also my comment to Zimmux's answer). I wrote "... with or without dots ..." to say that they are irrelevant; but it was not clear enough; so I edited the question and made it more explicit.  
> **username_2**: Marzio this was simply possible to guess but when you are talking about position of the head that I naturally expect to have it already in the final position (with respect to pebble sequence), made it unclear for me, if you mean something else (well the picture is nice but doesn't add any extra information, anyhow my ambiguities resolved).  
> **username_0**: @Saeed: I only cited several ways in which the target configuration can be defined (according to some variations of the game). I'm actually interested in the full final configuration of the pebbles (discard "head position", and the "remaining dots"). I'll clarify it!  
> **username_2**: I read all of them as a(lmost) same thing (in fact first one admits all others but not the other way around). But right now it's quite clear ;-)  

---

## 1 answers

### Answer by username_3 on 2015-01-17. Score: 9

Moving a snake from one position to some other is PSPACE complete.
Snake is trivially in PSPACE.
We give a PSPACE hardness reduction from Hearn's Nondeterministic Constraint Logic.

## Nondeterministic Constraint Logic

Let a *constraint graph* be a directed graph with edges of weight $1$ and $2$, such that every vertex has incoming weight $\geq 2$.
Given two constraint graphs, it is PSPACE hard to transform one into the other by reversing edges, one at a time, keeping the incoming weight of each vertex $\geq 2$.
This still holds if the graph is planar and each vertex has degree $3$, and either $1$ or all $3$ of its edges have weight $2$.
The former type of vertex is called And and the latter is called Or (see figure).
![NCL gadgets](https://i.sstatic.net/3d1Xr.png)

## Snake

In our construction, the snake's head will be chasing its tail at some small distance and will be forced to repeat the same cycle with minor modifications.
We embed each edge of the constraint graph as in the figure (edges shown in red), where we indicate the position of the snake by thick lines.
An edge has two sides (vertices) and the snake takes the central route at the vertex to which the edge is directed.
![Reversing an edge](https://i.sstatic.net/N67Ih.png)

To reverse an edge, the snake first clears the center route and then takes the center route once its head reaches the opposite vertex.

We embed vertices of the constraint graph as shown below, where each of the three colored parts is a half of an edge gadget shown above. The points where the edges touch make sure that the incoming weight of each vertex is at least $2$ by forcing the snake to take the center route of some edge gadgets.

![Snake And](https://i.sstatic.net/D4nkW.png)
![Snake Or](https://i.sstatic.net/vvLEk.png)

Finally, the black lines of all edge gadgets are connected to form a single cycle, so the head of the snake chases its tail.
If between two edge gadgets, we make the black path sufficiently long, the snake must always traverse the black paths in the same cyclic order.

To show that the black paths can always be constructed in a planar manner, consider a spanning subtree (thick edges in the figure below) of the constraint graph.
Then we can make black edges follow this tree as illustrated below, resulting in a planar graph.

![Spanning Subtree](https://i.sstatic.net/oUjz8.png)
![Planar Cycle](https://i.sstatic.net/SxCqj.png)

The target position of the snake can be derived by the same transformation.
Hence, reconfiguring a snake is PSPACE complete, even on planar graphs.

> **Comments:**
> **username_0**: Great! :-) :-) :-)  

---

