Ist Hidoku NP vollständig?

15

Ein Hidoku ist ein Gitter mit einigen vorgefüllten ganzen Zahlen von 1 bis n 2 . Ziel ist es, einen Pfad für aufeinanderfolgende ganze Zahlen (von 1 bis n 2 ) im Raster zu finden. Genauer gesagt muss jede Zelle des Gitters eine andere ganze Zahl von 1 bis n 2 enthalten, und jede Zelle mit dem Wert z n 2 muss eine Nachbarzelle mit dem Wert z + 1 haben (kann auch diagonal sein).n×nn2n2n2zn2z+1

Ist es NP schwer zu entscheiden, ob ein bestimmtes Hidoku lösbar ist? Welche Reduzierung könnte verwendet werden?

Edit: nach den Kommentaren gebe ich ein wenig Klarheit. Gegeben ist ein Gitter von Zellen, von denen einige bereits Werte enthalten (ganze Zahlen von 1 bis n²). Wir müssen alle verbleibenden Zellen mit ganzen Zahlen von 1 bis füllen , so dass keine zwei Zellen den gleichen Wert haben und jede Zelle mit dem Wert z n ² einen Nachbarn mit dem Wert . Das heißt, nach dem Ausfüllen der Zellen müssen wir den Pfad . In dem Raster, das jede Zelle logisch besucht.n2zn²1 , 2 , 3 , , n 2z+11,2,3,,n2

Ein Beispiel für ein Hidoku wäre http://www.janko.at/Raetsel/Hidoku/018.c.gif . Ein bereits gelöstes Hidoku ist http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel_7august_hidoku_schwer_loesung20100810172340.gif , wo Sie den Pfad sehen können, auf den ich mich bezog.

ipsec
quelle
1
Intuitiv, ohne viel darüber nachzudenken, klingt es auf den ersten Blick polytime-lösbar. So etwas wie eine dynamische Programmierung der zulässigen Werte ( ) und der Eckpunkte ( v 1 , v n ). Hört sich in Zeit O ( n 3 ) lösbar an . 1,,n2v1,vnO(n3)
Pål GD
Dies kann äquivalent als Graph modelliert werden, der Knoten mit Kanten verbindet, wenn sie Nachfolger in . Dann suchen Sie nach einem Hamilton-Pfad. Nach Hamilton-Pfaden in Gittergraphen von Itai et al. (1982) ist dieses Problem in Gittergraphen NP-vollständig. Dies passt nicht sofort zu Ihrem Problem, da Sie diagonale Verbindungen zulassen, aber es ist ein schlechtes Zeichen. N
Raphael
@Raphael Ist der konstruierte Graph keine DAG?
Pål GD
Ich verstehe nicht, wie das eine DAG ist. Soweit ich weiß, ist die Eingabe ein (ungerichteter) Gittergraph (der auch diagonale Kanten enthält) und das Ziel ist es, einen Hamilton-Pfad zu finden, in dem die Position einiger Knoten auf dem Pfad angegeben ist.
George
@ George Okey, ich habe die Frage so interpretiert, dass der maximale Pfad zunehmender Werte in einem Raster gefunden wird!
Pål GD

Antworten:

7

Ich denke , es ist -komplette: wie von Raffael, Hamilton - Zyklus auf Raster Graphen bemerkt mit Löchern Problem NP-vollständig ( Alon Itai, Christos Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton - Pfade in der Grid - Graphs SIAM J. Comput.. 11 (4): 676 & ndash; 686 (1982) ).NP

Wenn Sie also einen Gittergraphen mit Löchern haben, können Sie leicht ein äquivalentes Hidoku-Spiel erstellen, bei dem die anfänglichen festen Zellen alle geraden Diagonalen ausfüllen. Die leeren ungeraden Diagonalen bilden einen ungerichteten Graphen, der dem ursprünglichen Gittergraphen G entspricht, und das Hidoku hat nur dann eine Lösung, wenn der ursprüngliche Gittergraphen einen Hamilton-Pfad hat.GG

Bildbeschreibung hier eingeben

Abbildung 1: Ein Gitterdiagramm mit Löchern und dem entsprechenden Hidoku-Puzzle (blaue Zellen stehen für die ersten Zellen mit fester Nummer ( 1 ist die erste, 144 ist die letzte), weiße Zellen sind die Zellen, die der Spieler ausfüllen muss, violette Linie gibt die Reihenfolge der anfänglichen Zellen mit fester Nummer an).12×121144

Zusätzliche (gefüllte) Linien können unten oder rechts hinzugefügt werden, um ein Quadrat daraus zu machen.

Ein weiteres Beispiel für die Reduzierung von einem Gitterdiagramm auf ein Hidoku-Puzzle: Das 6x4-Gitterdiagramm ist in ein größeres 13x13-Gitter eingebettet. Die geraden Diagonalen werden mit festen Zahlen gefüllt, und die verbleibenden freien Zellen entsprechen dem ursprünglichen Gitterdiagramm.

Bildbeschreibung hier eingeben

Das vollständige Bild mit Transformation kann hier heruntergeladen werden .

Einige zusätzliche Hinweise zur Vervollständigung der Antwort:

  • das Problem ist auch als Hidato bekannt ; Das Board kann eine beliebige Form haben (aber als Verallgemeinerung des quadratischen Gehäuses bleibt es NP-hart).

  • n×n

  • Ich denke, dass die ursprünglichen Spielregeln besagen, dass die Lösung einzigartig sein sollte . Das Problem liegt also in den USA (US-schwer), und es ist unwahrscheinlich, dass es sich um NP handelt.

Zusammenfassend lässt sich sagen, dass wir die eindeutige Lösungseinschränkung aufheben und die erste Karte mit einer Liste von n 2 angebenn2NP

Vor
quelle
Ist das nicht eine DAG? Habe ich die Frage völlig falsch verstanden?
Pål GD
@ PålGD: nein, ich glaube nicht, dass es eine DAG ist, es ist ein ungerichteter Gittergraph mit diagonalen Kanten. Das Spiel beginnt mit einem teilweise gefüllten Brett und der Spieler von der Zelle 1 und erreichen die letzte machen orthogonal oder diagonal Schritten beginnen müssen (aber vielleicht kann ich nicht merken aus sehr gut die Regeln ... Ich kann es jetzt überprüfen)
Vor
1
Aber es heißt "finde einen Pfad von aufeinanderfolgenden ganzen Zahlen".
Pål GD
Vielleicht bedeutet es einfach , dass es nicht die gleiche Zelle zweimal besuchen können, und dass alle Zellen besucht werden müssen
Vor
1n2
2

n×nΩ(n)nlgn(xich,yich,wich):xich,yichn,wichn2(xich,yich)wichlgn+lgn+lgn2=4lgnÖ(lgn)Ω(n)Ö(n)

Ω(n)

(Eine Diskussion über ähnliche Themen finden Sie in meiner Frage vor einiger Zeit zur Komplexität von prägnantem Nurikabe auf der Website cstheory.SE.)

Steven Stadnicki
quelle
1
Die Angabe der Boardgröße in unary erscheint mir als unvernünftige Interpretation.
David Eisenstat
@ DavidEisenstat Es ist nicht unbedingt die natürliche Interpretation, aber es scheint mir eine vollkommen gültige zu sein.
Steven Stadnicki
@StevenStadnicki: Ich stimme Ihnen zu, ich habe eine ähnliche Anmerkung zum Nachweis der NP-Vollständigkeit von Binary Puzzle gemacht , die ich kürzlich auf cstheory.stackexchange.com gepostet habe. Obwohl die nicht-einheitliche Darstellung in der Tat nicht so vernünftig ist :-). Ich werde eine Notiz zu meiner Antwort hinzufügen. Und ich sollte auch das Problem der Eindeutigkeit der Lösung ansprechen; weil ich denke, dass die ursprünglichen Regeln besagen, dass die Lösung einzigartig sein sollte.
Vor