13
$\begingroup$

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.

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

$\endgroup$
  • 1
    $\begingroup$ 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". $\endgroup$ – Tom van der Zanden Dec 17 '14 at 8:46
  • $\begingroup$ Can you provide a better and clear definition for target configuration? e.g what do you mean by full description of snake position? $\endgroup$ – Saeed Dec 17 '14 at 9:51
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Dec 17 '14 at 9:57
  • $\begingroup$ Your question was clear enough, but I got the terminology mixed up in my comment. It should read "dots" everywhere instead of "pebbles". $\endgroup$ – Tom van der Zanden Dec 17 '14 at 10:06
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Dec 17 '14 at 10:42
8
$\begingroup$

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

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

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 Snake Or

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 Planar Cycle

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

$\endgroup$
  • $\begingroup$ Great! :-) :-) :-) $\endgroup$ – Marzio De Biasi Jan 21 '15 at 21:24

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.