Algorithmus zum Erstellen von Hex Flood Puzzle

Question

Ich erstelle ein Puzzle-Spiel, das, während für einfache Ebenen von Hand bespielbar ist, soll durch Computer-Programme für härtere gelöst werden. Das Puzzle ist eine Flutfüllung auf einem sechseckigen Brett. Sie können einen Prototyp here versuchen.

alt text http://www.hacker.org/flood/screen.png

Hier ist, wie das Puzzle funktioniert: durch eine Farbe aus der Top-Auswahl, können Sie eine Flutfüllung ausgehend von der oberen linken Kachel ausführen. Dies wandelt die Platine progressiv in eine feste Farbe um. Die Herausforderung besteht darin, dies in einer bestimmten Anzahl von Zügen zu tun.

Ich habe mehrere ähnliche Rätsel erstellt, und der Schlüssel ist, einen Algorithmus zu verwenden, der Boards generiert, die schwer zu lösen sind, ohne zu wissen, wie sie erstellt wurden. Zum Beispiel könnten wir hier ein Board produzieren, indem wir die Flutfüllung umkehren: Wir arbeiten rückwärts von einem festen Board, bis es unbelastet ist. Wir wissen, wie viele Schritte erforderlich waren, und können dies als untere Grenze für eine Lösung festlegen.

Das Problem, mit dem ich konfrontiert bin, ist, dass, wenn ich diesen Ansatz versuche, meine obere Grenze viel zu hoch ist. Es wird trivial, das Puzzle innerhalb dieser Anzahl von Zügen zu lösen, selbst wenn man sich zufällig bewegt.

Ein Ansatz, bei dem es sich nicht um eine Lösung handelt, ist die Erzeugung einer zufälligen Karte, die dann optimal gelöst und als Ziel festgelegt wird. Der Punkt ist, ein Puzzle zu erstellen, wo es optimal zu lösen ist NP Zeit oder zumindest eine harte P.

Also was ich suche ist ein Algorithmus, der extrem harte Boards erzeugen kann, wo sie zu lösen, wenn sie größer werden, wird zu einer ernsthaften Herausforderung.

Answer 1

Bei der RSA-Verschlüsselung finden wir keine Primzahlen, wir wählen Zufallszahlen aus und wenden dann Tests an, die uns eine immer höhere Wahrscheinlichkeit geben, dass die Zahl prim ist, ohne dass Sie sie jemals beweisen.

Ich schlage das gleiche vor. Versuchen Sie, Bedingungen zu finden, die dem Puzzle eine gute Wahrscheinlichkeit geben, die gewünschten Eigenschaften zu haben, und auf diese zu testen. Oder Sie könnten genetische Algorithmen/neuronale Netze benutzen und sie trainieren, die "guten" Rätsel zu erkennen, was auf dasselbe hinausläuft.

Answer 2

Ich würde versuchen, zu beweisen, dass es NP-vollständig oder in P ist, um ein Gefühl für die Konfigurationen zu bekommen, die schwierig sind.

Ich würde auch die Sechsecke abstrahieren und eine Darstellung als Grafik verwenden.

Answer 3

Ich habe das rechteckige Flutpuzzle viel gespielt (http://labpixies.com/gadget_page.php?id=10). Begeistert, eine Hex-Version zu sehen! Ich denke, ein hartes Spiel zu finden ist so einfach wie: Vermeiden Sie große Blöcke der gleichen Farbe, um im Puzzle zu erscheinen. Zumindest in den rechteckigen Fällen, die ich gesehen habe, haben fast alle Puzzles, die in einer kleinen Anzahl von Schritten gelöst werden können, große Farbblöcke.

P.S. Ich denke, deine "untere Grenze" ist nicht gültig. Wenn Sie mit einer guten Strategie arbeiten, könnten Sie in weniger Schritten fertig werden. Die "untere Grenze" ist wirklich eine obere Grenze für die optimale Lösung.