Die Komplexität des Puzzlespiels Net

Net (auch als FreeNet oder NetWalk bekannt) ist ein Puzzlespiel, das auf einem Raster mit den folgenden Objekten gespielt wird: $n \times n$

es gibt Computer ; Jeder Computer belegt eine Zelle und verfügt über ein Verbindungskabel. $m$
Jeder Computer muss an die Zentraleinheit angeschlossen sein, die eine Zelle belegt und über 1, 2 oder 3 Verbindungskabel verfügt.
Der Rest des Gitters ist mit Drähten gefüllt (es gibt keine leeren Zellen). eine Draht Zelle kann von drei Typen sein: gerade Linie, Ecke oder T-Verbindung.

Geben Sie hier die Bildbeschreibung ein

Das Ziel des Spiels ist es, jede Zelle zu drehen, um alle Computer mit der Zentraleinheit zu verbinden, ohne Schleifen zu bilden (dh die endgültige Konfiguration muss ein Baum sein) und ohne Drähte mit Sackgassen (die Blätter der endgültigen Konfiguration sind die Computer). .

* Wurde die Komplexität dieses Spiels untersucht?
* Und / oder sehen Sie eine schnelle Reduzierung eines bekannten ähnlichen NP-vollständigen Problems?

Eric Goles und Ivan Rapaport in " Komplexität von Kachelrotationsproblemen " beweisen, dass ein ähnliches Problem NP-vollständig ist, aber sie verwenden 5 Kacheln (wir können davon ausgehen, dass das Netzspiel 4 Kacheln verwendet, da wir die Zentraleinheit durch eine T- ersetzen können. Konnektor ohne Änderung der Spielstruktur), und in ihren Proof-Loops sind nicht verboten.

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

Wie ersetzt man die Zentraleinheit durch einen T-Stecker, wenn die Zentraleinheit

$\hspace{1.4 in}$ Hatten 4 Verbindungskabel die Spielstruktur nicht verändert?

$\:$

@ RickyDemer: Ich denke, dass die Zentraleinheit keinen Einfluss hat und dass sich die "Schwierigkeit" des Spiels nicht ändert, wenn sie auf 3 Links beschränkt und durch einen T-Draht (oder sogar eine Ecke) ersetzt wird. Eine Zentraleinheit mit 4 Verbindungen kann jedoch unter Verwendung von zwei benachbarten T-Verbindern simuliert werden und die Ebene neu anordnen, die die Drähte auf der hinzugefügten Säule verlängert / füllt. Ich werde die Frage ändern und die Verbindungen der Zentraleinheit auf 3 beschränken.

Marzio De Biasi

Es sieht für mich so aus, als könnten Sie den planaren Hamilton-Pfad auf dieses Problem reduzieren. Es würde jedoch viel Gadget-Konstruktion erfordern.

Peter Shor

@PeterShor: In der Tat habe ich die Gadgets gefunden, mit denen ein Net-Spiel erstellt werden kann, das einem Grid-Diagramm mit Grad , und das eine Lösung hat, wenn das ursprüngliche Diagramm einen Hamilton-Zyklus enthält: aber ich habe kein Selbst gepostet -Antwort noch, weil ich es immer noch überprüfe und versuche herauszufinden, ob ein anderes Element des Spiels (eine Art Draht oder sogar die Terminals) weggeworfen werden kann und das Spiel schwierig hält. Vielleicht sollte ich ein Bild von ihnen posten.

\leq 3

$\leq 3$

Marzio De Biasi

Nett! Es besteht keine Eile; Warten Sie, bis Sie bereit sind, eine Antwort zu veröffentlichen.

Peter Shor

Antworten:

Nur eine teilweise Selbstantwort: Ich denke, das Problem ist NP-vollständig.

Ich habe 3 Gadgets gefunden (jedes belegt Zellen), mit denen ein Netzspiel erstellt werden kann, das einem Gitterdiagramm mit Grad und das eine Lösung haben sollte, wenn das ursprüngliche Diagramm einen Hamilton-Zyklus hat. Die Abbildung zeigt vier verschiedene Konfigurationen des Gadgets, die einem Knoten mit Grad 3 entsprechen (das vollständige Bild kann hier heruntergeladen werden ). $16 \times 16$ $\leq 3$

Geben Sie hier die Bildbeschreibung ein

Das Gadget sollte die folgenden Eigenschaften haben (ich werde versuchen, sie mit einem Constraint-Solver zu überprüfen):

Es kann nur über die 3 Schnittstellenpaare der Eckdrähte ( , , ) mit anderen Geräten verbunden werden . $A$ $B$ $C$
Die beiden Drähte eines Schnittstellenpaars müssen sowohl nach außen als auch nach innen gerichtet sein (andernfalls befindet sich im inneren Teil des Geräts ein Draht mit offenem Ende oder ein Zyklus).
Das Gadget muss genau zweimal und von genau zwei Schnittstellenpaaren aus betreten / verlassen werden (die grünen Zonen der ersten drei Abbildungen zeigen die Durchquerungen AC, BC, AB).
Es müssen genau zwei Schnittstellenpaare nach außen gerichtet sein (die rote Zone in der Abbildung zeigt, was passiert, wenn die drei Schnittstellenpaare alle nach außen gerichtet sind).

Die Gadgets, die Knoten der Grade 2 und 1 entsprechen, sind ähnlich (und wir können auch "Füll" -Gadgets erstellen, um die Löcher des ursprünglichen Gittergraphen zu füllen).

Wenn Sie nun die beiden Zentralzellen eines Gadgets durch die Zentraleinheit ersetzen, die die Energie in eine Richtung und ein Terminal am anderen Endpunkt sendet, sollte das Spiel eine Lösung haben, wenn der ursprüngliche Graph einen Hamilton-Zyklus hat.

Marzio De Biasi
quelle

Übrigens funktioniert das für die Variante auf dem Torus?

Suresh Venkat

@SureshVenkat: Die Variante des Torus kann nicht einfacher sein, da ich denke, dass es eine einfache Reduzierung gegenüber der normalen Version gibt: Fügen Sie einen Rand hinzu, der alle aus Terminals besteht (wie der untere Rand des Gadgets oben); Auf diese Weise werden die Seiten des Torus mit Anschlüssen gefüllt, die das Signal zwischen ihnen nicht übertragen können.

Marzio De Biasi

Ich bin jetzt süchtig nach net :) - logogamesonline.com/netwalk/?g=Expert - und finde die toroidale Version viel schwieriger :)

Suresh Venkat

Ich würde gerne wissen, wie die NET-Rätsel im tatsächlich programmierten Spiel generiert werden. Werden sie so generiert, dass sie durch irgendeine Logik lösbar sind? Einzigartige Lösungen haben? (Sie scheinen alle einzigartige Lösungen zu haben.)

Peter Shor

Dies wird auf SO beantwortet . Es ist nicht garantiert, dass die Rätsel einzigartige Lösungen haben. Ich frage mich, wie oft sie es nicht tun.

Peter Shor