"Snake" reconfiguration problem

Question

While writing a small post on the complexity of the videogames Nibbler and Snake; 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.

A simple example (pebbles are shown in green, the snake's head is P1).

Answer 1

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).

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.

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.

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.

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