8
$\begingroup$

Net (known also as FreeNet, or as NetWalk) 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

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

Improve this question
$\endgroup$
6
  • $\begingroup$ How does replacing the central unit with a T-connector when the central unit $\hspace{1.4 in}$ had 4 link cables not change the game structure? $\:$ $\endgroup$
    – user6973
    Commented Nov 20, 2012 at 3:13
  • $\begingroup$ @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. $\endgroup$
    – Marzio De Biasi
    Commented Nov 20, 2012 at 9:23
  • $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented Nov 26, 2012 at 20:29
  • $\begingroup$ @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. $\endgroup$
    – Marzio De Biasi
    Commented Nov 26, 2012 at 21:01
  • $\begingroup$ Nice! There's no hurry; wait until you're ready to post an answer. $\endgroup$
    – Peter Shor
    Commented Nov 26, 2012 at 22:11

1 Answer 1

Reset to default
3
$\begingroup$

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

enter image description here

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ btw does this work for the variant on the torus ? $\endgroup$
    – Suresh Venkat
    Commented Nov 27, 2012 at 20:43
  • $\begingroup$ @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. $\endgroup$
    – Marzio De Biasi
    Commented Nov 27, 2012 at 21:00
  • $\begingroup$ I am now addicted to net :) - logicgamesonline.com/netwalk/?g=Expert - and find the toroidal version to be much harder :) $\endgroup$
    – Suresh Venkat
    Commented Nov 27, 2012 at 21:21
  • $\begingroup$ 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.) $\endgroup$
    – Peter Shor
    Commented Dec 10, 2012 at 16:11
  • $\begingroup$ This is answered on SO. The puzzles are not guaranteed to have unique solutions. I wonder how often they don't. $\endgroup$
    – Peter Shor
    Commented Dec 10, 2012 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.