La complejidad del juego de rompecabezas Net

Net (también conocido como FreeNet o NetWalk) es un juego de rompecabezas que se juega en una cuadrícula con los siguientes objetos: $n \times n$

hay computadoras ; cada computadora ocupa una celda y tiene un cable de enlace; $m$
cada computadora debe estar conectada a la unidad central que ocupa una celda y tiene 1, 2 o 3 cables de enlace;
el resto de la cuadrícula está llena de cables (no hay celdas vacías); Una celda de cable puede ser de tres tipos: línea recta, esquina o conexión en T.

ingrese la descripción de la imagen aquí

El objetivo del juego es rotar cada celda para conectar todas las computadoras a la unidad central sin hacer bucles (es decir, la configuración final debe ser un árbol) y sin cables con puntos muertos (las hojas de la configuración final son las computadoras) .

* ¿Se ha estudiado la complejidad de este juego?
* ¿Y / o ves una reducción rápida de un problema NP-completo similar conocido?

Eric Goles e Ivan Rapaport en " Complejidad de los problemas de rotación de fichas" demuestran que un problema similar es NP-completo pero usan 5 fichas (podemos suponer que el juego Net usa 4 fichas, porque podemos reemplazar la unidad central con una T- conector sin cambiar la estructura del juego), y en sus bucles de prueba no están prohibidos.

cc.complexity-theory reference-request np-hardness puzzles Marzio De Biasi
fuente

¿Cómo reemplazar la unidad central con un conector en T cuando la unidad central tenía 4 cables de enlace no cambia la estructura del juego?

$\hspace{1.4 in}$

$\:$

@RickyDemer: Creo que la unidad central no es fluida y que la "dificultad" del juego no cambia si se limita a 3 enlaces y se reemplaza por un cable en T (o incluso una esquina). Sin embargo, se puede simular una unidad central de 4 enlaces utilizando dos conectores T adyacentes y estableciendo el nivel que extiende / llena los cables en la columna añadida. Cambiaré la pregunta y limitaré los enlaces de la unidad central a 3.

Marzio De Biasi

Me parece que podría reducir el camino planar hamiltoniano a este problema. Sin embargo, se necesitaría mucha construcción de gadgets.

Peter Shor

@PeterShor: de hecho, encontré los gadgets que permiten construir un juego de red equivalente a un gráfico de cuadrícula con grado , y eso tiene una solución si hay un ciclo hamiltoniano en el gráfico original: pero no publiqué un auto Todavía respondo porque todavía lo estoy comprobando y estoy tratando de encontrar si otro elemento del juego (un tipo de cable, o incluso los terminales) se puede tirar y mantener el juego difícil. Quizás debería publicar una foto de ellos.

\leq 3

$\leq 3$

Marzio De Biasi

¡Agradable! No hay prisa; espera hasta que estés listo para publicar una respuesta.

Peter Shor

Respuestas:

Solo una respuesta parcial: creo que el problema es NP completo.

$16 \times 16$ $\leq 3$

ingrese la descripción de la imagen aquí

El gadget DEBE tener las siguientes propiedades (intentaré verificarlas con un solucionador de restricciones):

$A$ $B$ $C$
los dos cables de un par de interfaz deben dirigirse hacia afuera o hacia adentro (de lo contrario, hay un cable abierto o un ciclo en la parte interna del dispositivo);
el dispositivo debe ingresarse / salir exactamente dos veces y de exactamente dos pares de interfaces (las zonas verdes de las primeras tres figuras muestran los recorridos AC, BC, AB);
exactamente dos pares de interfaces deben dirigirse hacia afuera (la zona roja en la figura muestra lo que sucede si los tres pares de interfaces se dirigen hacia afuera);

Los dispositivos equivalentes a los nodos de grado 2 y 1 son similares (y también podemos construir dispositivos de "relleno" para llenar los agujeros del gráfico de cuadrícula original).

Ahora, reemplazando las dos celdas centrales de un dispositivo con la unidad central que envía la energía en una dirección y una terminal en el otro punto final, el juego DEBERÍA tener una solución si el gráfico original tiene un ciclo hamiltoniano.

Marzio De Biasi
fuente

Por cierto, ¿esto funciona para la variante en el toro?

Suresh Venkat

@SureshVenkat: la variante en el toro no puede ser más fácil, porque creo que hay una reducción fácil de la versión normal: agregue un borde todo hecho con terminales (como el borde inferior del gadget anterior); De esta manera, los lados del toro se llenan de terminales que no pueden transferir la señal entre ellos.

Marzio De Biasi

Ahora soy adicto a la red :) - logicgamesonline.com/netwalk/?g=Expert - y encuentro que la versión toroidal es mucho más difícil :)

Suresh Venkat

Me gustaría saber cómo se generan los rompecabezas NET en el juego programado real. ¿Se generan para ser solucionables por algún tipo de lógica? ¿Tener soluciones únicas? (Todos parecen tener soluciones únicas)

Peter Shor

Esto se responde en SO . No se garantiza que los rompecabezas tengan soluciones únicas. Me pregunto con qué frecuencia no lo hacen.

Peter Shor