Ist dieses klassische Puzzle-Buch-Spiel NP-komplett?

10

Es gibt ein klassisches Puzzlespiel, das einem Kreuzworträtsel sehr ähnlich ist, außer dass eine Liste von Wörtern angegeben wird und dann eine quadratische Tafel aus Einheitsquadraten gegeben wird, wobei einige Quadrate wie ein Kreuzwortwort verdunkelt sind. und auf einigen Quadraten ist bereits ein Brief vorgeschrieben. Das Ziel ist es, jedes Wort aus der Liste einmal und nur einmal in das Puzzle zu schreiben, wobei jedes Wort entweder horizontal (von links nach rechts) oder vertikal (von oben nach unten) in nicht verdunkelte aufeinanderfolgende Quadrate geschrieben wird und wenn Sie ein Wort schreiben Die beiden Quadrate, die die Wortenden flankieren, müssen entweder verdunkelt oder von der Tafel entfernt sein. Auch für die in einige Quadrate vorgeschriebenen Buchstaben müssen die geschriebenen Wörter, die diese Quadrate überlappen, den vorgeschriebenen Buchstaben berücksichtigen.N×N

Wenn wir nun ein Alphabet mit fester Größe für die Wörter annehmen, entscheiden wir, ob wir die Tafel mit einer gültigen Lösung füllen können, indem wir genau jedes Wort auf der Liste einmal und nur einmal als NP-vollständiges Problem verwenden, wenn die Seitenlänge der Tafel ist nicht behoben?

user2566092
quelle

Antworten:

6

Entschuldigung für die Beantwortung eines alten Beitrags.

Ich habe darüber nachgedacht und ich denke, dass das Problem mit einem festen Alphabet auch NP-vollständig ist.

Ich werde das positive 1-in-3-SAT auf dieses Wortproblem reduzieren

Gestern hatte ich Probleme mit Ideen zur Lösung des Problems. Ich hatte Probleme, jede Variable anders zu machen, bis ich mir die Frage noch einmal ansah und feststellte, dass Sie Quadrate mit gepflanzten Symbolen zulassen. Dies vereinfachte die Reduzierung erheblich. Meine andere Idee war, Wörter unterschiedlicher Länge für jede unterschiedliche Variable zu haben.

DIE REDUZIERUNG

Jetzt werde ich die Gadgets beschreiben, die wir verwenden werden:

Variables Gadget

Wir kennzeichnen jede Variable mit einem anderen numerischen Index und haben für jede Variable eine andere Nummer. Wir wählen den größten Index und stellen die Zahl in Binärform dar. Wir nennen diese Binärkette .n

Dann erstellen wir zwei verschiedene vertikale Wörter für jede Variable. Alle Wörter haben eine Länge von(Nur wenn wir doppelte Wörter in der Liste der Wörter zulassen), wobeiist die Länge der Binärkette .3+|n||n|n

Der größte Index sei beispielsweise die Zahl . Wenn wir diese Zahl in Binär umwandeln, erhalten wir die Kette in Binär, diese Kette hat eine Länge von drei. In diesem Beispiel hat jedes variable Wort eine Länge von .41006

Jetzt erstellen wir zwei verschiedene Wörter für jede Variable. Ein Wort hat das Symbol am Anfang, dann das Symbol unten, dann eine binäre Kette, die den Index der Variablen darstellt, und wir füllen die Kette mit Nullen auf, so dass sie dieselbe Länge hat wie die Kette und schließlich das Symbol Am Ende. Natürlich können die Symbole geändert werden.32n3

Das andere Wort ist fast dasselbe, aber es wird das Symbol anstelle des Symbols .43

Der größte Index sei beispielsweise die Zahl . Wir werden die folgenden zwei Wörter für die Variable mit Index :41

320013 und420014

Wie wir sehen, haben wir die binäre Darstellung der Zahl mit Nullen aufgefüllt, so dass sie eine Länge von1|n|

Wir müssen diese Wörter viele Male kopieren, wir benötigen eine Kopie jedes Wortes für jedes Auftreten einer Variablen in der SAT-Instanz. Dadurch werden Duplikate in der Liste der Wörter erstellt. Wir können die Duplikate entfernen, indem wir der Binärkette eine weitere Binärkette hinzufügen, die die Variable eindeutig identifiziert. Diese neue Kette identifiziert jedes Auftreten einer Variablen eindeutig.

Dazu weisen wir einfach jedem Auftreten der Variablen eine andere Binärkette zu und setzen diese Kette am Ende der Binärdarstellung der Variablen frei.

Um diese neue Binärkette zuerst zu erstellen, müssen wir für jede Variable einen anderen Index erstellen. Wir nennen die größte Zahl in jedem Index wobeiniini|ni||ni|

Dadurch werden Duplikate in den variablen Wörtern entfernt.

x2

32010013 4201001432010103 4201010432010113 42010114

Klausel-Gadget

6

535354535453545353

435

mm|m||m|. Wir hängen jede Binärkette an die Klauselwörter an, die zur Klausel gehören.

Nun sehen wir uns ein Bild eines Klausel-Gadgets an der Tafel an:

Beispielklausel

(x2x3x4)(x1x2x3)(x2x3x4)

4

Wenn wir keine Duplikate in der Wortliste zulassen, müssen wir das Bild ändern.

5b5b5b10

b201010bb201110bb21001b

b

Siehe ein Beispiel:

Klausel, keine Wiederholungen

Gadget mit variabler Konsistenz

Dies ist ein Gadget, das sicherstellt, dass der Player nur allen Literalspalten einer Variablen denselben Wert zuweisen kann.

Wir werden für jede Variable ein neues Gadget haben

Wir werden zwei neue Wörter für jedes Gadget erstellen.

2kkx263 k64 k

x2

63636464

Wenn Sie wiederholte Wörter vermeiden möchten, beachten Sie, dass jedes Konsistenz-Gadget zu einer anderen Variablen gehört. So können wir die Binärkette, die jede Variable identifiziert, an die beiden Wörter anhängen, die wir für dieses Gadget erstellt haben.

Sehen wir uns nun ein Beispielbild dieses Gadgets an:

Gadget mit variabler Konsistenz

x2(x1x2x3)(x2x3x4)

3434. Wir können das verbleibende Wort dieses Gagdet in die andere Zeile setzen

Wenn wir keine Duplikate in der Liste der Wörter zulassen, lauten die Wörter im Beispielbild wie folgt:

Für die Zeilen:

6b6b0106b6b010

Für die Spalten:

b201001bb201010b

b

Siehe ein Beispiel:

Konsistenz-Gadget, keine Wiederholungen

Klausel-Dump-Gadget

Dies ist ein Gadget, das zum Platzieren der nicht verwendeten Klauselwörter erstellt wurde. Dazu müssen wir nur zwei Zeilen für jedes Klauselwort in einen leeren Teil der Tafel einfügen. Diese Zeilen sind mit keiner anderen Zeile oder Spalte verbunden.

Damit beenden wir die Reduktion, da wir behaupteten, wir brauchen nur 6 Symbole für die Reduktion.

Beispiel

Wenn die vorherige Erklärung verwirrend war, ist hier ein Beispielbild einer Instanz von positivem 1: 3-SAT, die auf dieses Wortproblem reduziert wurde:

Beispieltafel

Wenn wir wiederholte Wörter nicht zulassen:

Beispieltafel, keine Wiederholungen

Die Instanz, die reduziert wurde, ist:

(x1x2x3)(x2x3x4)

Rotia
quelle
Vielen Dank für die Veröffentlichung! Ein unglückliches Merkmal von Stack Exchange ist, dass lange Antworten wahrscheinlich von niemandem gelesen werden, sodass es sehr unwahrscheinlich ist, dass Sie von der Menge an Arbeit, die Sie hier geleistet haben, viele Stimmen erhalten. Ich werde versuchen, das zu lesen, aber wenn ich ehrlich bin, besteht eine gute Chance, dass ich nicht dazu komme.
David Richerby
2
@ DavidRicherby Jaja ja. Ich habe eine Weile über diese Frage nachgedacht. Ich dachte, wenn ich diese Antwort poste, wird jeder sie positiv bewerten. Ist nicht passiert. Na egal. Wenn Sie Fragen zur Ermäßigung haben, können Sie mich fragen
Rotia
4

Ich denke, die folgende Reduktion vom gerichteten Hamilton-Pfad funktioniert:

G=(V,E)s,tV

V{}V

vvvVvu(u,v)E

|V|

Treppe

|E|(|V|1)

sstt

Um die Treppe zu füllen, können jetzt nur Scheitelpunktwörter in die Schritte eingefügt werden. Um zwei Scheitelpunkte zu verbinden, muss ein Kantenwort zwischen ihnen eingefügt werden, das einer vorhandenen Kante im Diagramm entspricht. Die nicht verwendeten Kanten können in den zweiten Teil der Platine gelegt werden. Die zweite Richtung ist trivial.

Ich denke, das funktioniert (der von mir skizzierte Korrektheitsnachweis ist bestenfalls von Hand gewellt, aber immer noch).

Shaull
quelle
1
stN×NN
Das ist schön und scheint zu funktionieren, aber die Alphabetgröße ist nicht wie in meinem ursprünglichen Beitrag angefordert festgelegt. Ist eine Änderung möglich, um ein Alphabet mit fester Größe zu verwenden und diese Reduzierung dennoch durchzuführen?
user2566092
uv