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.
The complexity of the puzzle game Net
cc.complexity theory;reference request;np hardness;puzzles