<p>Just a partial self-answer: I think the problem is NP-complete.</p>

<p>I found 3 gadgets (each one occupies $16 \times 16$ cells) that allows to build a Net game equivalent to a grid graph of degree $\leq 3$ and that should have a solution iif the original graph has an Hamiltonian cycle. The figure shows four different configurations of the gadget equivalent to a node with degree 3 (the full picture can be <a href="http://www.fractalmuse.org/wp-content/uploads/2012/11/netgadgets.jpg" rel="nofollow noreferrer">downloaded here</a>).</p>

<p><img src="https://i.sstatic.net/oNvFS.png" alt="enter image description here"></p>

<p>The gadget SHOULD have the following properties (I'll try to check them with a constraint solver):</p>

<ul>
<li>it can be linked to other gadgets only through the 3 <em>interface pairs</em> of corner wires ($A$, $B$, $C$);</li>
<li>the two wires of an interface pair must be directed both outwards or both inwards (otherwise there is an open ended wire or a cycle in the inner part of the gadget);</li>
<li>the gadget must be entered/exited exactly twice and from exactly two interface pairs (the green zones of the first three figures show the traversals A-C, B-C, A-B);</li>
<li>exactly two interface pairs must be directed outward (the red zone in the figure shows what happens if the three interface pairs are all directed outward);</li>
</ul>

<p>The gadgets equivalent to nodes of degree 2 and 1 are similar (and we can also build "fill" gadgets to fill the holes of the original grid graph).</p>

<p>Now replacing the two central cells of one gadget with the central unit that sends the power on one direction and a terminal at the other endpoint, the game SHOULD have a solution iif the original graph has an Hamiltonian cycle.</p>

CC BY-SA 3.0
2012-11-27T20:43:52.513Z
btw does this work for the variant on the torus ?
Suresh Venkat
CC BY-SA 3.0
2012-11-27T21:00:33.977Z
@SureshVenkat: the variant on the torus cannot be easier, because I think that there is an easy reduction from the normal version: add a border all made with terminals (like the bottom border of the gadget above); in this way the sides of the torus are filled with terminals that cannot transfer the signal between them.
Marzio De Biasi
CC BY-SA 3.0
2012-11-27T21:21:35.973Z
I am now addicted to net :) - http://www.logicgamesonline.com/netwalk/?g=Expert - and find the toroidal version to be much harder :)
Suresh Venkat
CC BY-SA 3.0
2012-12-10T16:11:22.373Z
I'd like to know how the NET puzzles in the actual programmed game are generated. Are they generated so as to be solvable by some kind of logic? To have unique solutions? (They all do seem to have unique solutions.)
Peter Shor 
CC BY-SA 3.0
2012-12-10T16:16:14.853Z
This is answered on [SO](http://stackoverflow.com/questions/6608104/what-is-the-algorithm-for-generating-the-maze-in-the-game-netwalk). The puzzles are not guaranteed to have unique solutions. I wonder how often they don't.
Peter Shor 
CC BY-SA 3.0
2012-12-13T20:27:24.663Z
@PeterShor: I made some checks with a constraint solver, and [wrote a more complete proof/explanation that can be downloaded here](http://www.fractalmuse.org/?p=87) (the 3-node gadget is a little bit different, but the argument is the same). For what regards the uniqueness of solutions, I didn't think about it, too much, but it easy to build a 5x4 block that doesn't have an unique valid configuration.
Marzio De Biasi
CC BY-SA 3.0
2012-11-26T22:24:03.980Z
2012-11-26T22:24:03.980Z
Marzio De Biasi
<p><a href="http://www.chiark.greenend.org.uk/~sgtatham/puzzles/java/net.html" rel="nofollow noreferrer">Net (known also as FreeNet, or as NetWalk)</a> is a puzzle game played on a $n \times n$ grid with the following objects:</p>

<ul>
<li>there are $m$ <em>computers</em> ; each computer occupies one cell and has one link cable;</li>
<li>each computer must be connected to the <em>central unit</em> which occupies one cell and has  1, 2 or 3 link cables;</li>
<li>the rest of the grid is filled with <em>wires</em> (there are no empty cells); a <em>wire cell</em> can be of three types: straight line, corner, or T-connection.</li>
</ul>

<p><img src="https://i.sstatic.net/fweD8.jpg" alt="enter image description here"></p>

<p>The aim of the game is to rotate each cell in order to connect all computers to the central unit without making loops (i.e. the final configuration must be a tree) and without wires with dead ends (the leaves of the final configuration are the computers).</p>

<blockquote>
* Has the complexity of this game been studied?<br>
* And/or do you see a quick reduction from a known similar NP-complete problem?
</blockquote>

<p>Eric Goles and Ivan Rapaport in "<a href="http://www.dim.uchile.cl/~rapaport/rot01.pdf" rel="nofollow noreferrer">Complexity of tile rotation problems</a>" prove that a similar problem is NP-complete but they use 5 tiles (we can assume that the Net game uses 4 tiles, because we can replace the central unit with a T-connector without changing the game structure), and in their proof loops are not forbidden.</p>

CC BY-SA 3.0
2012-11-20T09:23:49.087Z
@RickyDemer: I think that the central unit is ininfluent, and that the game "difficulty" doesn't change if it is restricted to 3 links and replaced by a T-wire (or even a corner). However a 4 links central unit can be simulated using two adjacent T connectors, and rearringing the level extending/filling the wires on the added column. I'll change the question and limit the links of the central unit to 3.
Marzio De Biasi
CC BY-SA 3.0
2012-11-26T20:29:26.757Z
It looks to me as if you might be able to reduce planar Hamiltonian path to this problem. It would take a lot of gadget-construction, though.
Peter Shor 
CC BY-SA 3.0
2012-11-26T21:01:08.060Z
@PeterShor: indeed I found the gadgets that allow to build a Net game equivalent to a grid graph with degree $\leq 3$, and that has a solution iif there is an Hamiltonian cycle in the original graph: but I didn't post a self-answer yet because I'm still checking it and I'm trying to find if another element of the game (a type of wire, or even the terminals ) can be thrown away and keep the game difficult. Perhaps I should post a picture of them.
Marzio De Biasi
CC BY-SA 3.0
2012-11-26T22:11:26.047Z
Nice! There's no hurry; wait until you're ready to post an answer.
Peter Shor 
CC BY-SA 3.0
2012-11-26T22:25:29.540Z
@PeterShor: too late :( I posted the gadget ... at least if it is wrong, it can be used like an aztec poster  :-)
Marzio De Biasi
<cc.complexity-theory><reference-request><np-hardness><puzzles>
The complexity of the puzzle game Net
Marzio De Biasi
# The complexity of the puzzle game Net

(Asked by: username_0 on 2012-11-19)

[Net (known also as FreeNet, or as NetWalk)](http://www.chiark.greenend.org.uk/~sgtatham/puzzles/java/net.html) is a puzzle game played on a $n \times n$ grid with the following objects:

* there are $m$ *computers* ; each computer occupies one cell and has one link cable;
* each computer must be connected to the *central unit* which occupies one cell and has 1, 2 or 3 link cables;
* the rest of the grid is filled with *wires* (there are no empty cells); a *wire cell* can be of three types: straight line, corner, or T-connection.

![enter image description here](https://i.sstatic.net/fweD8.jpg)

The aim of the game is to rotate each cell in order to connect all computers to the central unit without making loops (i.e. the final configuration must be a tree) and without wires with dead ends (the leaves of the final configuration are the computers).

> \* Has the complexity of this game been studied?  
> \* And/or do you see a quick reduction from a known similar NP-complete problem?

Eric Goles and Ivan Rapaport in "[Complexity of tile rotation problems](http://www.dim.uchile.cl/~rapaport/rot01.pdf)" prove that a similar problem is NP-complete but they use 5 tiles (we can assume that the Net game uses 4 tiles, because we can replace the central unit with a T-connector without changing the game structure), and in their proof loops are not forbidden.

**Tags:** cc.complexity-theory, reference-request, np-hardness, puzzles
> **Comments:**
> **username_0**: @RickyDemer: I think that the central unit is ininfluent, and that the game "difficulty" doesn't change if it is restricted to 3 links and replaced by a T-wire (or even a corner). However a 4 links central unit can be simulated using two adjacent T connectors, and rearringing the level extending/filling the wires on the added column. I'll change the question and limit the links of the central unit to 3.  
> **username_1**: It looks to me as if you might be able to reduce planar Hamiltonian path to this problem. It would take a lot of gadget-construction, though.  
> **username_0**: @PeterShor: indeed I found the gadgets that allow to build a Net game equivalent to a grid graph with degree $\leq 3$, and that has a solution iif there is an Hamiltonian cycle in the original graph: but I didn't post a self-answer yet because I'm still checking it and I'm trying to find if another element of the game (a type of wire, or even the terminals ) can be thrown away and keep the game difficult. Perhaps I should post a picture of them.  
> **username_1**: Nice! There's no hurry; wait until you're ready to post an answer.  
> **username_0**: @PeterShor: too late :( I posted the gadget ... at least if it is wrong, it can be used like an aztec poster  :-)  

---

## 1 answers

### Answer by username_0 on 2012-11-26. Score: 3

Just a partial self-answer: I think the problem is NP-complete.

I found 3 gadgets (each one occupies $16 \times 16$ cells) that allows to build a Net game equivalent to a grid graph of degree $\leq 3$ and that should have a solution iif the original graph has an Hamiltonian cycle. The figure shows four different configurations of the gadget equivalent to a node with degree 3 (the full picture can be [downloaded here](http://www.fractalmuse.org/wp-content/uploads/2012/11/netgadgets.jpg)).

![enter image description here](https://i.sstatic.net/oNvFS.png)

The gadget SHOULD have the following properties (I'll try to check them with a constraint solver):

* it can be linked to other gadgets only through the 3 *interface pairs* of corner wires ($A$, $B$, $C$);
* the two wires of an interface pair must be directed both outwards or both inwards (otherwise there is an open ended wire or a cycle in the inner part of the gadget);
* the gadget must be entered/exited exactly twice and from exactly two interface pairs (the green zones of the first three figures show the traversals A-C, B-C, A-B);
* exactly two interface pairs must be directed outward (the red zone in the figure shows what happens if the three interface pairs are all directed outward);

The gadgets equivalent to nodes of degree 2 and 1 are similar (and we can also build "fill" gadgets to fill the holes of the original grid graph).

Now replacing the two central cells of one gadget with the central unit that sends the power on one direction and a terminal at the other endpoint, the game SHOULD have a solution iif the original graph has an Hamiltonian cycle.

> **Comments:**
> **username_2**: btw does this work for the variant on the torus ?  
> **username_0**: @SureshVenkat: the variant on the torus cannot be easier, because I think that there is an easy reduction from the normal version: add a border all made with terminals (like the bottom border of the gadget above); in this way the sides of the torus are filled with terminals that cannot transfer the signal between them.  
> **username_2**: I am now addicted to net :) - http://www.logicgamesonline.com/netwalk/?g=Expert - and find the toroidal version to be much harder :)  
> **username_1**: I'd like to know how the NET puzzles in the actual programmed game are generated. Are they generated so as to be solvable by some kind of logic? To have unique solutions? (They all do seem to have unique solutions.)  
> **username_1**: This is answered on [SO](http://stackoverflow.com/questions/6608104/what-is-the-algorithm-for-generating-the-maze-in-the-game-netwalk). The puzzles are not guaranteed to have unique solutions. I wonder how often they don't.  
> **username_0**: @PeterShor: I made some checks with a constraint solver, and [wrote a more complete proof/explanation that can be downloaded here](http://www.fractalmuse.org/?p=87) (the 3-node gadget is a little bit different, but the argument is the same). For what regards the uniqueness of solutions, I didn't think about it, too much, but it easy to build a 5x4 block that doesn't have an unique valid configuration.  

---

