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