Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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? $\:$ –  Ricky Demer Nov 20 '12 at 3:13
    
@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 Nov 20 '12 at 9:23
    
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 Nov 26 '12 at 20:29
    
@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 Nov 26 '12 at 21:01
    
Nice! There's no hurry; wait until you're ready to post an answer. –  Peter Shor Nov 26 '12 at 22:11
show 1 more comment

1 Answer

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.

share|improve this answer
    
btw does this work for the variant on the torus ? –  Suresh Venkat Nov 27 '12 at 20:43
    
@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 Nov 27 '12 at 21:00
    
I am now addicted to net :) - logicgamesonline.com/netwalk/?g=Expert - and find the toroidal version to be much harder :) –  Suresh Venkat Nov 27 '12 at 21:21
    
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 Dec 10 '12 at 16:11
    
This is answered on SO. The puzzles are not guaranteed to have unique solutions. I wonder how often they don't. –  Peter Shor Dec 10 '12 at 16:16
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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