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

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

<p><img src="https://i.sstatic.net/Qk5z5.png" alt="3SAT"></p>

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

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

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

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

<p><em>Remark: We will use <strong>boldface</strong> to distinguish the <strong>Exit</strong> of the graph from exits of gadgets.</em></p>

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

<p><img src="https://i.sstatic.net/xHdDG.png" alt="One-way gadget">
<img src="https://i.sstatic.net/bQWmu.png" alt="Clause gadget"></p>

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

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

<ol>
<li>A <strong>One-way</strong> gadget is traversed in the unintended direction ($B$ to $A$).</li>
<li>A path traverses all three paths of some <strong>Clause</strong> gadget.</li>
</ol>

<p>In the first case, the <strong>One-way</strong> 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.</p>

<p>So consider the second case where the path traverses all three switches of some <strong>Clause</strong> 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 <em>backbone</em> of the <strong>Clause</strong> 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 <strong>Clause</strong> gadget is unrecoverable.</p>

<p><img src="https://i.sstatic.net/K5IBF.png" alt="Deadlocked Clause"></p>

<p>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 <strong>Exit</strong> wire can only be reached when there is a solution, or some Clause gadget becomes unrecoverable.</p>

<p>To place switches in their target position, we can now add additional <strong>One-way</strong> gadgets from the <strong>Exit</strong> wire to the entrance of every existing <strong>One-way</strong> gadget, as well as to the three exit wires of all <strong>Clause</strong> gadgets.
Then, once the token reaches the <strong>Exit</strong>, all the additional <strong>One-way</strong> 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 <strong>Exit</strong> and the puzzle is solved.</p>

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

<p>Hence, the switch network problem is NP-hard.</p>

<hr>

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

<p><img src="https://i.sstatic.net/dymX7.png" alt="Sokoban"></p>

CC BY-SA 3.0
2014-09-01T22:27:45.117Z
2014-09-01T22:39:07.540Z
2014-09-01T22:39:07.540Z
Tim
<p>A <em>switch network</em> (the name is invented) is made with three types of nodes:</p>
<ul>
<li>one Start node</li>
<li>one End node</li>
<li>one or more Switch nodes</li>
</ul>
<p>The switch node has 3 exits: Left, Up, Right; has two <em>states L and R</em> and
a <em>target state TL or TR</em>. Each switch can be traversed with the following rules:</p>
<ul>
<li>always from Left to Up; the state of the switch changes to L</li>
<li>always from Right to Up; the state fo the switch changes to R</li>
<li>from Up to Left only if the switch is in state L; the state doesn't change</li>
<li>from Up to Right if the switch is in state R; the state doesn't change</li>
<li>never from Left to Right or Right to Left</li>
</ul>
<p><img src="https://i.sstatic.net/eMW3U.jpg" alt="switch node" /><br>
Figure 1. Switch node in state L with target state TR</p>
<p>These properties also hold:</p>
<ul>
<li>0, 1 or 2 of the exits of a switch can be isolated (not connected to another switch);</li>
<li>a path can just <em>&quot;touch&quot;</em> a switch to change its state: enter from Left and exit from Left or enter from Right and exit from Right;</li>
<li>there are no restrictions on the number of times a switch can be traversed / touched.</li>
</ul>
<p>The decision problem is: <em>&quot;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?&quot;</em></p>
<p>Obviously, all the switches that are not initially in their target state must be traversed (or touched) at least once;</p>
<p>This is a quick draw of a trivial network (made with Excel ... I'll make a better one):</p>
<p><img src="https://i.sstatic.net/pKw6J.jpg" alt="example2" /></p>
<p>A trivial solutions is:</p>
<pre><code>S -&gt; 1 -&gt; 2 -&gt; 3 -&gt; 2 -&gt; E -&gt; 1 -&gt; E
</code></pre>
<p><strong>EDIT 2:</strong></p>
<ol>
<li>Is this problem known? ---&gt; you gave me the good reference to the <a href="http://groups.csail.mit.edu/mac/users/bob/hearn-thesis-final.pdf" rel="noreferrer">Hearn's thesis</a> (constraint graphs);</li>
</ol>
<p>The problem is in <span class="math-container">$NPSPACE = PSPACE$</span>; before posting a sketch of my proof that it is in NP, I found an error; so the open questions are again:</p>
<blockquote>
<p>2 . Is it <span class="math-container">$\mathsf{NP}$</span>?</p>
<p>3 . Has the problem any chance to be <span class="math-container">$\mathsf{NP\text{-}complete}$</span>?</p>
</blockquote>

CC BY-SA 3.0
2011-12-12T12:24:27.633Z
These look like they are related to _switching graphs_. e.g, http://www.win.tue.nl/~jfg/articles/CSR-08-28.pdf
Dave Clarke
CC BY-SA 3.0
2011-12-12T12:44:20.583Z
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 ...".
Marzio De Biasi
CC BY-SA 3.0
2011-12-12T14:04:23.807Z
I think he means "Given starting configuration X and target configuration Y, does traversing the unique walk from the Start node to the End node, starting in configuration X, actually yield configuration Y?"  A naive traversal may go through an exponential number of configurations.
Jeffε
CC BY-SA 3.0
2011-12-12T14:07:49.913Z
@Peter: Yes of course; as specified in the question, the switch can always be traversed from left to up and from right to up (but this causes its state to change). The switch can be traversed from top to left (respectively right) only if its current state is TL (respectively TR). The decision problem is "Exists a path from S to E **AND** every switch is in its target state." So all the switches that are not initially in their target state must be traverseed at least once.
Marzio De Biasi
CC BY-SA 3.0
2011-12-12T14:13:10.713Z
@Jeffe: it is what I mean, but the path from Start node to the End node must not necessarily be unique. (I added a clarification paragraph in the question, let me know if it is still unclear).
Marzio De Biasi
CC BY-SA 3.0
2011-12-12T14:48:24.217Z
@Peter: I added a trivial example. See if its enough.
Marzio De Biasi
CC BY-SA 3.0
2011-12-12T15:07:56.633Z
@Peter: yes the switch triggers "when the path reaches it" ... perhaps I must be more clear in the question :-(
Marzio De Biasi
CC BY-SA 3.0
2011-12-12T18:14:32.133Z
@Vor: This seems closely related to the constraint logic games of Demaine and Hearn (I think Hearn's thesis http://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...
Joshua Grochow
CC BY-SA 3.0
2011-12-12T18:41:39.220Z
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.
Steven Stadnicki
CC BY-SA 3.0
2011-12-12T20:39:54.473Z
@Joshua: thanks for the reference; and I found that I already have the thesis in my archive and it definitely sticks to the point; now I'll read it ... however I think that my switch gate is not so powerful (max PSPACE-complete).
Marzio De Biasi
CC BY-SA 3.0
2011-12-12T23:35:23.227Z
It seems this should be trivially in NP. Is there any reason it shouldn't be in NP?
Kaveh
CC BY-SA 3.0
2011-12-13T08:17:22.407Z
@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.
Marzio De Biasi
CC BY-SA 3.0
2011-12-13T10:44:30.260Z
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](http://www.sciencedirect.com/science/article/pii/000437029490040X)
Carlos Linares López
CC BY-SA 3.0
2011-12-15T12:47:31.133Z
So, why is the problem in NP?
Emil Jeřábek
CC BY-SA 3.0
2011-12-15T15:59:18.213Z
@Vor: Maybe post an answer to your own question?
Aaron Sterling
CC BY-SA 3.0
2011-12-17T17:50:28.207Z
@Emil: before posting my proof I found there is an error in it (and I was not able to fix it) ... the question is still open.
Marzio De Biasi
CC BY-SA 3.0
2011-12-23T22:07:03.623Z
This game has to be PSPACE-complete. I suggest you look into other proofs of this type (see http://en.wikipedia.org/wiki/List_of_PSPACE-complete_problems), e.g. Sokoban.
domotorp
CC BY-SA 3.0
2011-12-23T23:35:21.497Z
@domotorp: I read the PSPACE-completeness proof of Sokoban, and indeed my problem is a kind of Sokoban with the following tightening conditions: 1) the blocks move only horizontally, and 2) they do  not interact with each other; plus a weaker condition: 3) not planar. But perhaps the two tight conditions are enough to "break" the PSPACE-completeness of Sokoban. The switch "gadget" *seems* very simple, and I didn't succeed even in finding an NP-hardness proof, so I decided to post the question here.
Marzio De Biasi
CC BY-SA 3.0
2011-12-31T07:09:31.627Z
@Vor: I am sorry you did not receive any answers. I guess no one is motivated enough to design the gadgets and carefully think over the details of the reduction...
domotorp
CC BY-SA 3.0
2012-01-05T07:13:57.717Z
Very nice problem... I will think about it.
Bob Hearn
CC BY-SA 3.0
2012-01-05T18:12:37.057Z
@Bob: out of curiosity, are you *R. A.* Hearn?
Marzio De Biasi
CC BY-SA 3.0
2012-01-06T06:26:58.747Z
@Vor: Yes. My intuition is that this is PSPACE-complete, and there should be a reduction from Nondeterministic Constraint Logic, specifically the configuration-to-configuration variant. The gadgets would probably be similar to those used in the PSPACE-completeness proof of Push-2F. See page 3 of http://groups.csail.mit.edu/mac/users/bob/push2f.pdf.
Bob Hearn
CC BY-SA 3.0
2012-01-06T12:04:34.400Z
@Bob: congratulations for your great book "Games, Puzzles and Computation"! I tried to find a reduction from NCL, too; but failed to build a choice vertex. I'll read the Push-2F article but at a first look, the unidirectional diode gadget seems not realizable: with a switch you can "cut" the way-back, but you can arbitrarily delay such a cut (at least until the "cut" entrance is reachable).
Marzio De Biasi
CC BY-SA 3.0
2012-01-06T17:57:22.493Z
@Vor: You shouldn't need a Choice vertex for this reduction, just And and Or. I threw out the Push-2F reduction only as a loose analogy -- it feels to me like the reduction here would be similar to parts of that. It wouldn't necessarily use identical gadgets. However, diode-like things are often very useful in these kinds of reductions, and it may well be a problem if (as it seems) one can't be made.
Bob Hearn
CC BY-SA 3.0
2013-07-12T07:54:19.907Z
@Vor=Marzio: Btw, what is the motivation to study this question, would it have some interesting consequence if it turned out to be PSPACE-complete?
domotorp
<ds.algorithms><reference-request><graph-algorithms><np>
Complexity of a switch network problem
Marzio De Biasi
# Complexity of a switch network problem

(Asked by: username_0 on 2011-12-12)

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


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

A trivial solutions is:
S -> 1 -> 2 -> 3 -> 2 -> E -> 1 -> E

EDIT 2:

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}$?

**Tags:** ds.algorithms, reference-request, graph-algorithms, np

> **Comments:**
> **username_1**: These look like they are related to _switching graphs_. e.g, http://www.win.tue.nl/~jfg/articles/CSR-08-28.pdf  
> **username_0**: 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 ...".  
> **username_2**: I think he means "Given starting configuration X and target configuration Y, does traversing the unique walk from the Start node to the End node, starting in configuration X, actually yield configuration Y?"  A naive traversal may go through an exponential number of configurations.  
> **username_0**: @Peter: Yes of course; as specified in the question, the switch can always be traversed from left to up and from right to up (but this causes its state to change). The switch can be traversed from top to left (respectively right) only if its current state is TL (respectively TR). The decision problem is "Exists a path from S to E **AND** every switch is in its target state." So all the switches that are not initially in their target state must be traverseed at least once.  
> **username_0**: @Jeffe: it is what I mean, but the path from Start node to the End node must not necessarily be unique. (I added a clarification paragraph in the question, let me know if it is still unclear).  
> **username_0**: @Peter: I added a trivial example. See if its enough.  
> **username_0**: @Peter: yes the switch triggers "when the path reaches it" ... perhaps I must be more clear in the question :-(  
> **username_3**: @Vor: This seems closely related to the constraint logic games of Demaine and Hearn (I think Hearn's thesis http://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...  
> **username_4**: 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.  
> **username_0**: @Joshua: thanks for the reference; and I found that I already have the thesis in my archive and it definitely sticks to the point; now I'll read it ... however I think that my switch gate is not so powerful (max PSPACE-complete).  
> **username_5**: It seems this should be trivially in NP. Is there any reason it shouldn't be in NP?  
> **username_0**: @username_5: 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.  
> **username_6**: 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](http://www.sciencedirect.com/science/article/pii/000437029490040X)  
> **username_7**: So, why is the problem in NP?  
> **username_8**: @Vor: Maybe post an answer to your own question?  
> **username_0**: @Emil: before posting my proof I found there is an error in it (and I was not able to fix it) ... the question is still open.  
> **username_9**: This game has to be PSPACE-complete. I suggest you look into other proofs of this type (see http://en.wikipedia.org/wiki/List_of_PSPACE-complete_problems), e.g. Sokoban.  
> **username_0**: @username_9: I read the PSPACE-completeness proof of Sokoban, and indeed my problem is a kind of Sokoban with the following tightening conditions: 1) the blocks move only horizontally, and 2) they do  not interact with each other; plus a weaker condition: 3) not planar. But perhaps the two tight conditions are enough to "break" the PSPACE-completeness of Sokoban. The switch "gadget" *seems* very simple, and I didn't succeed even in finding an NP-hardness proof, so I decided to post the question here.  
> **username_9**: @Vor: I am sorry you did not receive any answers. I guess no one is motivated enough to design the gadgets and carefully think over the details of the reduction...  
> **username_10**: Very nice problem... I will think about it.  
> **username_0**: @Bob: out of curiosity, are you *R. A.* Hearn?  
> **username_10**: @Vor: Yes. My intuition is that this is PSPACE-complete, and there should be a reduction from Nondeterministic Constraint Logic, specifically the configuration-to-configuration variant. The gadgets would probably be similar to those used in the PSPACE-completeness proof of Push-2F. See page 3 of http://groups.csail.mit.edu/mac/users/bob/push2f.pdf.  
> **username_0**: @Bob: congratulations for your great book "Games, Puzzles and Computation"! I tried to find a reduction from NCL, too; but failed to build a choice vertex. I'll read the Push-2F article but at a first look, the unidirectional diode gadget seems not realizable: with a switch you can "cut" the way-back, but you can arbitrarily delay such a cut (at least until the "cut" entrance is reachable).  
> **username_10**: @Vor: You shouldn't need a Choice vertex for this reduction, just And and Or. I threw out the Push-2F reduction only as a loose analogy -- it feels to me like the reduction here would be similar to parts of that. It wouldn't necessarily use identical gadgets. However, diode-like things are often very useful in these kinds of reductions, and it may well be a problem if (as it seems) one can't be made.  
> **username_9**: @Vor=Marzio: Btw, what is the motivation to study this question, would it have some interesting consequence if it turned out to be PSPACE-complete?  

---

## 1 answers

### Answer by username_11 on 2014-09-01. Score: 2

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

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](https://i.sstatic.net/xHdDG.png)
![Clause gadget](https://i.sstatic.net/bQWmu.png)

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

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


---

