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

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 \times 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?

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 .$4$$100$$6$

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.$3$$2$$n$$3$

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

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

$320013$ und$420014$

Wie wir sehen, haben wir die binäre Darstellung der Zahl mit Nullen aufgefüllt, so dass sie eine Länge von$1$$|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 wobei$n_i$$i$$n_i$$|n_i|$$|n_i|$

Dadurch werden Duplikate in den variablen Wörtern entfernt.

$x_2$

$32010013$ $42010014$$32010103$ $42010104$$32010113$ $42010114$

Klausel-Gadget

$6$

$535354$$535453$$545353$

$4$$3$$5$

$m$$m$$|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:

$(x_2 \lor x_3 \lor x_4)$$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

$4$

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

$5b5b5b10$

$b201010b$$b201110b$$b21001b$

$b$

Siehe ein Beispiel:

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.

$2 * k$$k$$x_2$$63$ $k$$64$ $k$

$x_2$

$6363$$6464$

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:

$x_2$$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

$3$$4$$3$$4$. 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:

$6b6b010$$6b6b010$

Für die Spalten:

$b201001b$$b201010b$

$b$

Siehe ein Beispiel:

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:

Wenn wir wiederholte Wörter nicht zulassen:

Die Instanz, die reduziert wurde, ist:

$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

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

$G=(V,E)$$s,t\in V$

$V\cup \{*\}$$*$$V$

$v*v$$v\in V$$vu$$(u,v)\in E$

$|V|$

$|E|-(|V|-1)$

$s*s$$t*t$

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).