17
$\begingroup$

A switch network (the name is invented) is made with three types of nodes:

  • one Start node
  • one End node
  • one or more Switch nodes

The switch node has 3 exits: Left, Up, Right; has two states L and R and a target state TL or TR. Each switch can be traversed with the following rules:

  • always from Left to Up; the state of the switch changes to L
  • always from Right to Up; the state fo the switch changes to R
  • from Up to Left only if the switch is in state L; the state doesn't change
  • from Up to Right if the switch is in state R; the state doesn't change
  • never from Left to Right or Right to Left

switch node
Figure 1. Switch node in state L with target state TR

These properties also hold:

  • 0, 1 or 2 of the exits of a switch can be isolated (not connected to another switch);
  • a path can just "touch" a switch to change its state: enter from Left and exit from Left or enter from Right and exit from Right;
  • there are no restrictions on the number of times a switch can be traversed / touched.

The decision problem is: "Does a path from the Start node to the End node exist such that all the final states of the switches match the corresponding target state?"

Obviously, all the switches that are not initially in their target state must be traversed (or touched) at least once;

This is a quick draw of a trivial network (made with Excel ... I'll make a better one):

example2

A trivial solutions is:

S -> 1 -> 2 -> 3 -> 2 -> E -> 1 -> E

EDIT 2:

  1. Is this problem known? ---> you gave me the good reference to the Hearn's thesis (constraint graphs);

The problem is in $NPSPACE = PSPACE$; before posting a sketch of my proof that it is in NP, I found an error; so the open questions are again:

2 . Is it $\mathsf{NP}$?

3 . Has the problem any chance to be $\mathsf{NP\text{-}complete}$?

$\endgroup$
  • 1
    $\begingroup$ I gave a quick look to the suggested paper (now I'll read it more carefully), but my problem seems different: the switches change their state according to the direction in which they are traversed. In the article the switches are "fixed" and the (simpler) problems are of the kind: "Does a switch configuration exists, such that ...". $\endgroup$ – Marzio De Biasi Dec 12 '11 at 12:44
  • 4
    $\begingroup$ @Vor: This seems closely related to the constraint logic games of Demaine and Hearn (I think Hearn's thesis groups.csail.mit.edu/mac/users/bob/hearn-thesis-final.pdf is a very nice writeup of this work). I wonder if one could resolve the complexity of your problem using their techniques. It seems like it might be NEXP-complete... $\endgroup$ – Joshua Grochow Dec 12 '11 at 18:14
  • 3
    $\begingroup$ I was just going to point out the Hearn/Demaine work - note that it's also available as a book now, "Games, Puzzles & Computation" (ISBN 978-1-56881-322-6), and it definitely feels germane to this question. $\endgroup$ – Steven Stadnicki Dec 12 '11 at 18:41
  • 2
    $\begingroup$ @Kaveh: for my level of expertise it is trivially in NPSPACE = PSPACE. It seems not able to "count"; but I don't see any easy proof that if a solution exists, then another solution exists in which every switch is traversed/touched only a constant number of times. $\endgroup$ – Marzio De Biasi Dec 13 '11 at 8:17
  • 1
    $\begingroup$ Just a side note: a simpler version of this puzzle was considered also by Dillenburg and Nelson and it is presented in their Research Note Perimeter Search $\endgroup$ – Carlos Linares López Dec 13 '11 at 10:44
2
$\begingroup$

The problem is at least NP-hard, by a reduction from 3-SAT.

First consider the problem of finding a path from the Start to the Exit of the following directed graph with the restriction that no path may visit all three (square) nodes of a clause:

3SAT

For this graph, such a path only exists if the formula $(X1 \lor X2 \lor X3)\land(X1\lor\neg X2\lor X4)$ can be satisfied. We can build such graphs for arbitrary formulas in 3-CNF, and finding such a path is NP-complete.

We transform these graphs to a switch network. For this we use three gadgets:

  1. Every circle node and bidirectional edge becomes a Wire, forming the connections between switches.
  2. Every directed edge becomes a One-way gadget consisting of a single switch (see below).
  3. Every square node represents one of the three switches that are part of a Clause gadget (see below).

In the following illustrations, switches are drawn as two incoming arrows, one of which is dashed (disabled). The target direction is drawn with a black circle (such that the solid arrow must eventually be on the side of the circle).

Remark: We will use boldface to distinguish the Exit of the graph from exits of gadgets.

For the One-way gadget, entrance $A$ cannot be reached from exit $B$ until $B$ has been reached from $A$. For the Clause gadget, entrances $X1$, $X2$ and $X3$ lead to exits $X1'$, $X2'$ and $X3'$, respectively.

One-way gadget Clause gadget

Recall that for the original graph, finding a path that led to the Exit and did not visit all three square nodes of any clause was NP-complete. Now consider the problem of reaching the Exit of the transformed graph without worrying about the target positions of the switches.

Observe that any path that is a solution for the original graph problem is also a solution for the transformed graph. So assume a path for the transformed graph is not a solution for the original graph. This may happen in two cases:

  1. A One-way gadget is traversed in the unintended direction ($B$ to $A$).
  2. A path traverses all three paths of some Clause gadget.

In the first case, the One-way gadget must have first been traversed in the intended direction, in which case the path might as well have avoided traversing it in the first place.

So consider the second case where the path traverses all three switches of some Clause gadget. Then that gadget will have all its three switches flipped (see below). This is where we make use of the target positions. Notice that the gray backbone of the Clause gadget can no longer be reached, meaning that the switches can no longer be directed to their target positions. In this case, we say that this Clause gadget is unrecoverable.

Deadlocked Clause

It remains to show that for any solution of the original graph problem, the switches of the transformed graph can be placed in their target position. For this, we make use of the fact that the Exit wire can only be reached when there is a solution, or some Clause gadget becomes unrecoverable.

To place switches in their target position, we can now add additional One-way gadgets from the Exit wire to the entrance of every existing One-way gadget, as well as to the three exit wires of all Clause gadgets. Then, once the token reaches the Exit, all the additional One-way gadgets can be traversed (and thereby put in their target position), and also put the remaining switches in their target positions (unless there is an unrecoverable clause). Finally, the token can return to the Exit and the puzzle is solved.

We should remark that Clause gadgets can only be recovered when entered from an untraversed exit; and due to the One-way gadgets that are placed between Clause gadgets and the next variable, this cannot happen until the Exit wire is reached.

Hence, the switch network problem is NP-hard.


It is still unclear if the problem is in NP or PSPACE-hard. An NP-hardness reduction constructing a planar switch network will have great implications for restricted variants of Sokoban, namely because all switches are equivalent to the Sokoban gadget below.

Sokoban

$\endgroup$

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.