A complexidade do jogo de quebra-cabeça Net

Net (conhecido também como FreeNet, ou como NetWalk) é um jogo jogado em um grade com os seguintes objetos:$n \times n$

• existem computadores ; cada computador ocupa uma célula e possui um cabo de ligação;$m$
• cada computador deve estar conectado à unidade central que ocupa uma célula e possui 1, 2 ou 3 cabos de ligação;
• o restante da grade é preenchido com fios (não há células vazias); uma célula de arame pode ser de três tipos: linha reta, canto ou conexão em T.

O objetivo do jogo é girar cada célula para conectar todos os computadores à unidade central sem fazer loops (ou seja, a configuração final deve ser uma árvore) e sem fios com becos sem saída (as folhas da configuração final são os computadores) .

* A complexidade deste jogo foi estudada?
* E / ou você vê uma rápida redução de um problema NP-completo semelhante conhecido?

Eric Goles e Ivan Rapaport em " Complexidade dos problemas de rotação de ladrilhos " provam que um problema semelhante é NP-completo, mas eles usam 5 ladrilhos (podemos supor que o jogo Net use 4 ladrilhos, porque podemos substituir a unidade central por um T- conector sem alterar a estrutura do jogo) e em suas provas não são proibidos.

Apenas uma resposta parcial: acho que o problema é NP-completo.

$16 \times 16$$\leq 3$

O gadget DEVE ter as seguintes propriedades (tentarei verificá-las com um solucionador de restrições):

• $A$$B$$C$
• os dois fios de um par de interface devem ser direcionados para fora ou para dentro (caso contrário, há um fio de extremidade aberta ou um ciclo na parte interna do dispositivo);
• o gadget deve ser inserido / retirado exatamente duas vezes e de exatamente dois pares de interface (as zonas verdes das três primeiras figuras mostram os percursos AC, BC, AB);
• exatamente dois pares de interface devem ser direcionados para o exterior (a zona vermelha na figura mostra o que acontece se os três pares de interface forem todos direcionados para o exterior);

Os dispositivos equivalentes aos nós de grau 2 e 1 são semelhantes (e também podemos criar dispositivos de "preenchimento" para preencher os buracos do gráfico de grade original).

Agora, substituindo as duas células centrais de um dispositivo pela unidade central que envia a energia em uma direção e um terminal no outro ponto final, o jogo DEVE ter uma solução, se o gráfico original tiver um ciclo Hamiltoniano.