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).
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.1 , 2 , 3 , ⋯ , n 2
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.
Antworten:
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.G G
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×12 1 144
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.
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).
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 angebenn2 NP
quelle
(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.)
quelle