Algorithmus zur Lösung von Flow Free Spiel

Ich habe vor kurzem angefangen zu spielen Flow Free Spiel.

Algorithmus zur Lösung von Flow Free Spiel

Schließen Sie passenden Farben mit Rohr, um erstellen Sie einen flow. Paar alle Farben und decken das gesamte board, jedes Rätsel zu lösen in Flow Free. Aber aufgepasst, werden Rohre brechen, wenn Sie sich kreuzen oder überlappen!

Wurde mir klar, es ist nur Weg zu finden Spiel zwischen gegebenen paar von Punkten mit den Bedingungen, dass keine zwei Pfade überschneiden. Ich war daran interessiert, schreiben eine Lösung für das Spiel, aber nicht wissen, wo zu beginnen. Ich dachte, der Verwendung von backtracking, aber für sehr große board-Größen wird es höchste Zeit, Komplexität.

Ist es keine geeigneten Algorithmus zu lösen, um das Spiel effizient. Kann mit Heuristiken zum lösen des Problems helfen? Geben Sie mir nur einen Hinweis, wo ich anfangen soll, ich nehmen es von dort.

Beobachtete ich in den meisten boards, die in der Regel

  1. Für die entferntesten Punkte, die Sie benötigen, zu Folgen Pfad entlang Kante.
  2. Für Punkt-zu-nächst an einander, Folgen Sie den direkten Weg, wenn es einen gibt.

Ist diese richtige Beobachtung und kann es verwendet werden, um es zu lösen effizient?

  • Das Stichwort ist hier "die meisten boards". Free-Flow ist ein visual Modernisierung eines bekannten NP-Schwer (wenn nicht NP-Vollständig) Spiel, dessen name(s) ich kann nicht denken, der offhand. Daher ist es nicht bekannt, noch zu erwarten, dass effiziente Lösungen in allen Fällen, das ist leichter zu sehen, wenn Sie versuchen, lösen die größeren.
  • So gibt es keine Lösung für das Rätsel?
  • Nein, es ist einfach keine effiziente Lösung. Ein computer lösen kann, jede Instanz von Free-Flow, aber die Zeit, die es dauert im Durchschnitt wächst exponentiell mit der puzzle-Größe. Eine grobe Schätzung könnte man sagen, dass ein 10x10 ist so etwas wie 30x schwieriger zu lösen als in einem 5x5 beispielsweise. Ich sehe dies in der Praxis, wie ich Sie lösen kann die 5x5-Rätsel in unter einer Sekunde, aber es dauert einiges länger, um das zu lösen 10x10. Inzwischen 20x20 könnte über 1000x schwerer zu lösen als ein 10x10. Es gibt keine 20x20s in Freier Strömung, aber ich habe es lösen alle Rätsel in diesem Spiel und einige haben sich viel Zeit genommen.
  • Ich denke, es ist ein Fall beschränkt von multicommodity flow, aber das bedeutet nicht unbedingt, es ist NP-schwer.
  • Es dauerte eine Weile, um es zu finden, aber here ist, wo ich zuerst über Sie kam. Ein wenig online-Forschung, scheint bestätigt. Das Spiel, das ich dachte, war NumberLink. Ich erinnerte mich, es war ein bekannter Japanischer Spiele-publisher, Nikoli und fand den Namen so.
  • Sie können versuchen, eine simulation:stackoverflow.com/questions/18511095/....
  • Naja, das problem ist sicherlich in NP (siehe meine Antwort). Die Frage ist, ob es NP-hart und damit auch NP-vollständig.
  • Die Suche nach "SAT Formulierung von numberlink" und "NP-Vollständigkeit von numberlink" führt zu ein paar Referenzen. Nicht überraschend, die zwei wichtigsten sind in Japanisch. ersten ist die tatsächliche Papier der Nachweis der NP-Vollständigkeit. zweiten - beschreibt, wie Sie zu lösen NumberLink mit der SAT-solver, Zucker.

InformationsquelleAutor coder hacker | 2014-05-13
  1. 7

    Reduktion auf SAT

    Grundidee

    1. Reduzieren das problem auf SA
    2. Ein moderner SAT-solver, um das problem zu lösen
    3. Gewinn

    Komplexität

    Das problem ist offensichtlich in NP: Wenn Sie schätzen ein board Konstellation, es ist einfach (poly-Zeit), um zu überprüfen, ob es das problem löst.

    Ob es NP-hart (d.h. so hart, wie jedes andere problem in NP, z.B. SAT), ist nicht klar. Sicherlich moderne SAT-Solver wird das nicht zu kümmern und zu lösen große Instanzen, die in einer Brise, die sowieso (ich Schätze bis zu 100x100).

    Literatur über die Anzahl Link -

    Ich hier einfach kopieren Nuclearman Kommentar zu der OP:

    Suche nach "SAT Formulierung von numberlink" und "NP-Vollständigkeit von numberlink" führt zu ein paar Referenzen. Nicht überraschend, die zwei wichtigsten sind in Japanisch. Die erste ist das eigentliche Papier Nachweis der NP-Vollständigkeit. Die zweite beschreibt, wie Sie zu lösen NumberLink mit der SAT-solver, Zucker. –

    Hinweis für die Reduktion auf SAT

    Gibt es mehrere Möglichkeiten für die Kodierung des Problems. Ich gebe ein, dass ich machen konnte, schnell.

    Bemerkung

    j_random_hacker festgestellt, dass freistehende Zyklen sind nicht erlaubt. Die folgenden Codierung nicht zulässt. Dieses problem macht der SAT-Kodierung ein bisschen weniger attraktiv. Die einfachste Methode, die ich denken konnte, zu verbieten, free-standing loops einführen würde O(n^2) neuen Variablen, in denen n ist die Anzahl der Steine auf dem Brett (count Entfernung vom nächsten Waschbecken für jede Kachel), es sei denn, man verwendet log-Codierung für das, was würde es bringen, nach unten zu O(n*log n) möglich macht das problem schwieriger für den solver.

    Variablen

    Einer variable pro Stück, Stück Typ und Farbe. Beispiel, wenn einige Variablen X-Y-T-C ist wahr, es kodiert, dass die Kachel an position X/Y ist der Typ T und hat die Farbe C. Sie brauchen nicht die leere Kachel Typ, da kann das nicht passieren in einer Lösung.

    Ursprünglichen Variablen

    Setzen Sie die Variablen für die Spüle/Quellen und sagen, keine andere Fliesen können sink/source.

    Einschränkungen

    1. Für jede position genau eine Farbe/Stück Kombination (true cardinality constraint).
    2. Für jede variable (position, Typ, Farbe), die vier angrenzenden Fliesen haben, um kompatibel zu sein (wenn die Farbe passt).

    Ich könnte etwas verpasst haben. Es sollte aber leicht behoben werden.

    • Irgendeine Idee, wie zu verringern, problem-SA
    • Ich fand es sehr befriedigend zu reduzieren, Probleme zu SAT. Wenn Sie auf der JVM, können Sie einfach ziehen Sie Sie in einen SAT-solver als Maven-dependency (SAT4J). Es ist wirklich einfach und schnell.
    • Schöne Lösung! Ich denke, man könnte es reduzieren auf ein ganzzahliges lineares Programm (ILP) in der gleichen Weise und verwenden Sie einfach ein standard-solver. Einschränkungen sind von der Art: jede Quelle/Senke hat 1 oder 3 Nachbarn in der gleichen Farbe, jede andere Zelle hat 2 oder 4 Nachbarn der gleichen Farbe. Offene Frage: formal beweisen, dass eine Lösung, die diese Einschränkungen gültig ist. Kann nicht allzu schwer sein, durch Widerspruch.
    • Während die Reduktion auf ILP ist sicherlich möglich, ich würde nicht empfehlen, dies zu tun. Dies ist kein Optimierungsproblem, sondern lediglich die Erfüllbarkeit problem. Mit einem CSP-format kann mehr bequem zu bedienen als SA, aber. Der Unterschied zwischen SAT und CSP ist, dass die CSP-ermöglicht Variablen mit Werte mehr als zwei.
    • Ja, du hast Recht, es ist nicht wirklich ein Optimierungsproblem.
    • Angenommen, Sie haben 2 Stück-Typen "pipe" (die Steine) und die "endpoint" (die Kacheln am start anwesend), ich denke, die Einschränkungen sind Sie der Versorgung nicht auszuschließen, die Möglichkeit der Zyklen (loops) von "pipe" - Fliesen. Man muss hinzufügen, das äquivalent von "subtour elimination constraints" für das TSP.
    • Siehe meine Antwort für ein Beispiel, wie es zu lösen mit SAT.

    InformationsquelleAutor ziggystar
  2. 3

    Ich vermute, dass kein Polynom-Zeit-Algorithmus, der garantiert wird lösen jede Instanz des Problems. Aber da eine der Anforderungen ist, dass jedes Quadrat muss behandelt werden, von Rohr, einen ähnlichen Ansatz zu dem, was sowohl Menschen als auch Computern nutzen für die Lösung Sudoku sollte hier gut passen:

    1. Für jeden leeren Platz, bilden einen Satz von möglichen Farben für das Quadrat, und dann wiederholt, führen logische Abzüge auf jedes Quadrat zu schrumpfen, die zulässige Menge von Farben für das Quadrat.
    2. Wann immer ein Quadrat der Satz von möglichen Farben verkleinert, um der Größe 1, die Farbe für diesen Platz bestimmt.
    3. Wenn wir einen Zustand erreichen, wo keine logischen Schlussfolgerungen, kann durchgeführt werden und das puzzle ist nicht komplett gelöst, doch ist (d.h. es gibt mindestens ein Feld mit mehr als einem möglichen Farbe), wählen Sie eine dieser unentschiedenen Plätze und recurse auf Sie, versuchen, jedes der möglichen Farben in der Reihe. Bei jedem Versuch wird entweder zu einer Lösung führen, oder ein Widerspruch, die letztere beseitigt, dass die Farbe als eine Möglichkeit für das Quadrat.

    Wenn Kommissionierung ein Quadrat zum Zweig auf, es ist generell eine gute Idee, wählen ein Quadrat mit möglichst wenigen Farben erlaubt wie möglich.

    [EDIT: Es ist wichtig, zu vermeiden, die Möglichkeit der Bildung von ungültig "Schleifen" des Rohres. Ein Weg dies zu tun ist durch die Aufrechterhaltung, für jedes zugelassene Farbe, die ich von jedem Quadrat, x, 2 bits von Informationen: ob der Platz x ist verbunden durch einen Pfad, der bestimmte ich-farbigen Fliesen, um das erste ich-farbige Endpunkt, und das gleiche für das zweite ich-farbige Endpunkt. Dann, wenn recursing, nicht immer wählen Sie ein Quadrat, das zwei Nachbarn mit der gleichen bit-Satz (oder weder mit bit-set) für alle zulässigen Farben.]

    Braucht man eigentlich nicht zu verwenden, keine logischen Schlussfolgerungen, sondern mehr und bessere Abzüge, die Sie verwenden, desto schneller läuft das Programm, wie Sie wird (ggf. drastisch) reduzieren die Menge der Rekursion. Einige nützliche Abzügen zählen:

    1. Wenn ein Quadratmeter ist die einzig mögliche Art und Weise zu erweitern, den Weg für einige bestimmten Farbe, dann ist es muss zugeordnet werden, die Farbe.
    2. Wenn ein Quadrat hat die Farbe, die ich in den erlaubten Farben, aber es nicht mindestens 2 benachbarten Plätzen, die auch die Farbe, die ich in Ihre Sätze dürfen die Farben, dann kann es nicht sein "erreicht", Weg von Farbe i und Farbe i eliminiert werden kann als eine Möglichkeit.

    Erweiterte Abzüge basiert auf der Pfad-Konnektivität könnte weiter helfen -- wenn Sie z.B. feststellen können, dass jeder Weg Anschluss einige paar Anschlüsse müssen durch einen bestimmten Platz, Sie können sofort zuordnen, dass die Farbe auf den Platz.

    Diesem einfachen Ansatz lässt sich eine komplette Lösung ohne Rekursion in deinem 5x5 Beispiel: die Quadrate an (5, 2), (5, 3), (4, 3) und (4, 4) gezwungen sind, werden orange; (4, 5) ist gezwungen, grün zu sein; (5, 5) ist auch gezwungen, grün zu sein, aufgrund der Tatsache, dass keine andere Farbe könnte man diesen Platz und dann wieder zurück; jetzt ist das orange Weg endet am (4, 4) hat nirgendwo zu gehen, außer, um die komplette orange-Pfad an (3, 4). Auch (3, 1) ist gezwungen, zu rot sein; (3, 2) ist gezwungen, gelb zu werden, was wiederum Kräfte (2, 1) und (2, 2) rot werden, die schließlich zwingt die gelb-Pfad zu beenden, auf (3, 3). Das rote Rohr (2, 2) Kräfte (1, 2), zu blau, und die roten und blauen Wege eingereicht werden, ganz bestimmt, "zwingt jedes andere", wie Sie gehen.

    • Sieht vielversprechend aus, als die anderen Antworten, werde versuchen, die ur-Ansatz
    • Wenn Sie einen SAT-solver, er wird alles tun, was beschrieben ist in dieser Antwort, und mehr (Dinge, die Sie nicht nachdenken).
    • Es wäre schwer zu sagen, ein SAT-solver über die Notwendigkeit zu vermeiden, Schleifen der Leitung. Für die Beseitigung subtours aus der TDL dies erfolgt normalerweise durch die Erzeugung dieser constraints on-the-fly, wenn Sie gefunden werden, erforderlich zu sein, da gibt es eine exponentielle Anzahl von Ihnen, so die Angabe von Ihnen, alle am start wären ein non-starter. (Mit einer ILP-solver, aber es ist eine ähnliche situation.)
    • Also, a) sind Schleifen möglich in dem Spiel überhaupt? b) Sind Sie nicht zulässig? Dies ist kein kürzester Pfad Wettbewerb. Es ist fit in allen Stücken. Wenn Sie können sich einfach nicht Schleifen/Kreuzungen dann nicht zulässig, die entsprechenden Stücke.
    • Ich mag SA-Löser auch, aber j_random_hacker will propagieren einer mehr komplizierten Einschränkung als leicht ausgedrückt mit den solvern, die ich verwendet habe.
    • Ich bin damit einverstanden, dass Sie möglicherweise mehr tun, Ausbreitung, als das, was SAT-Löser zu tun (die Leute fanden heraus, dass alles komplizierter ist, als unit-propagation nicht bezahlen), und insbesondere können Sie dies tun, in einem Domäne-abhängigen Art und Weise wie vorgeschlagen. Aber es ist nicht einfach, und möglicherweise auch nicht schneller. Ich denke, was ich im Grunde sagen möchte ist dieses: Reduktion auf SAT ist einfach und das erste, was ich versuchen würde. Darüber hinaus ist es unklar, ob Sie implementieren können, etwas schneller, was in einer angemessenen Höhe der Zeit. Aber wenn Sie Spaß haben, Dinge Programmierung, der Kurs gehen.
    • In der online-version des Spiels, die ich gefunden haben, können Sie nicht schaffen free-standing loops. Nicht sicher, was du meinst mit "dann lassen Sie die entsprechenden Stücke" - wie würden Sie das tun?
    • Ah, ich vermisse die freistehend. In der Tat, das macht der SAT-Kodierung viel mehr kompliziert. Ich fühle den Drang, es zu implementieren.

    InformationsquelleAutor j_random_hacker
  3. 3

    Fand ich einen blog-post auf Unnötig Komplex, die vollständig erläutert, wie Sie SAß, um dieses problem zu lösen.

    Der code ist open-source, also kann man es anschauen (und verstehen) in Aktion.

    Gebe ich ein Zitat von ihm hier, das beschreibt die Regeln, die Sie implementieren müssen, um in SA:

    • Jede Zelle zugewiesen wird, eine einzelne Farbe.

    • Die Farbe von jedem Endpunkt Zelle ist bekannt und angegeben.

    • Jeden endpoint-Zelle hat genau einen Nachbarn passt seine Farbe.
    • Die Strömung durch jeden nicht-endpoint-Zelle entspricht genau einem der sechs Richtung-Typen.
    • Die Nachbarn einer Zelle, spezifiziert durch seine Richtung geben muss mit seiner Farbe.
    • Der Nachbarn einer Zelle nicht angegeben wird, indem seine Richtung geben muss, nicht mit seiner Farbe.

    Danke @Matt Zucker für die Erstellung dieses!

    InformationsquelleAutor Pro Q
  4. 0

    Ich mag Lösungen, die ähnlich wie das menschliche denken. Sie können (ziemlich leicht) die Antwort bekommen, von einem Sudoku durch brute-force, aber es ist mehr nützlich, um einen Pfad konnten Sie gefolgt sind, um das puzzle zu lösen.

    Beobachtete ich in den meisten boards, die in der Regel
    1.Für die äußersten Punkte, die Sie benötigen, zu Folgen Pfad entlang der Kante.
    2.Für Punkt-zu-nächst an einander, Folgen Sie den direkten Weg, wenn es einen gibt.
    Ist diese richtige Beobachtung und kann es verwendet werden, um es zu lösen effizient?

    Diese wahr sind "meistens", aber nicht immer.

    Ich würde ersetzen Sie Ihre erste Regel von dieser einen : wenn die beiden senken sind entlang der Kante, die Sie benötigen, zu Folgen Pfad entlang der Kante. (Sie bauen konnte ein Gegenbeispiel, aber es ist wahr, die meisten der Zeit). Nachdem Sie einen Pfad entlang der Kante, die Blöcke entlang der Kante sollten als Teil der Kante, so dass Ihr Algorithmus wird versuchen, die Folgen der neuen Kante aus, die durch die Vorherige Leitung. Ich hoffe, dieser Satz macht Sinn...

    Natürlich, bevor Sie diese verwenden, "die meisten der Zeit," die Regeln, die Sie Folgen müssen, absolute Regeln (siehe die beiden Abzüge von j_random_hacker s post).

    Andere Sache ist, zu versuchen, Sie zu beseitigen boards, die nicht zu einer Lösung führen. Nennen wir ein unfertiges Rohr (startet aus einem Waschbecken aber noch nicht erreicht, die anderen sink) eine Schlange, und die letzten Quadratmeter des unvollendeten pipe aufgerufen wird, werden der Schlange den Kopf. Wenn Sie nicht finden können, einen Weg der leeren Felder zwischen den zwei Köpfen der gleichen Farbe, bedeutet dies, dass dein board nicht zu einer Lösung führen, und sollte weggeworfen werden (oder müssen Sie ansetzen, je nach Implementierung).

    Den freien Fluss Spiel (und ähnliche Spiele) zu akzeptieren, als eine gültige Lösung ein board wo es gibt zwei Linien der gleichen Farbe nebeneinander, aber ich glaube, es gibt immer eine Lösung auch ohne side-by-side-Zeilen. Das würde bedeuten, dass jeder Platz, der nicht sinken würde, haben genau zwei Nachbarn in der gleichen Farbe, und sinkt würde genau einen. Wenn die Regel passiert immer wahr (ich glaube, es ist, es aber nicht können, beweisen es), das wäre eine weitere Einschränkung zum verringern der Anzahl der Möglichkeiten. Ich löste einige der Free-Flow-Rätsel mithilfe von side-by-side-Zeilen, aber die meisten Male, die ich eine andere Lösung gefunden ohne Sie. Ich habe nicht gesehen side-by-side-Zeilen auf Free Flow solutions web-site.

    InformationsquelleAutor Yves Forget
  5. 0

    Einige Regeln, die Sie führen zu einer Art von Algorithmus Level zu lösen, in Fluss, basierend auf der IOS-vertions von Big Duck Games, diese Firma scheint zu produzieren, die kanonische Versionen. Den rest dieser Antwort übernimmt keine Wände, Brücken oder Ketten.

    Selbst wenn Ihr unheimlich gut, die riesige 15x18 square-Platinen sind ein gutes Beispiel, wie nur werde es in einer Weise, die sehr wahrscheinlich bekommen Sie stecken kurz vor dem Ende immer und immer wieder und praktisch, die nun wieder von vorn beginnen. Dies ist wohl mit den bereits erwähnten exponentiellen Zeitkomplexität im Allgemeinen Fall. Aber dies bedeutet nicht, dass eine einfache stratergy ist nicht überwältigend wirksam für die meisten boards.

    1. Blöcke sind nie leer, also verwaiste Blöcke meinst, du hast etwas falsch gemacht.

    2. Kardinal benachbarten Zellen der gleichen Farbe angeschlossen werden muss. Diese Regeln 2x2 Blöcke der gleichen Farbe und auf dem hexagonalen Gitter mit Dreiecken in 3 benachbarten Zellen.

    3. Können Sie oft machen perminent Fortschritte durch den Nachweis, dass eine Farbe geht oder ausgeschlossen ist, von einem bestimmten Quadratmeter.

    4. Aufgrund der Punkte 1 und 2, auf dem hexagonalen raster auf boards, die sind sechseckig in der Form einer Rohr entlang geht, eine Kante ist in der Regel stecken entlang geht es hin nach der Ausfahrt, effektiv bewegen der äußeren Kante und macht das board kleiner, so dass der Prozess wiederholt werden kann. Es ist vorhersehbar, welche Arten von benachbarten Bedingungen garantieren und was Arten können brechen dieses Zyklus für beide Arten von grid.

    Meisten, wenn nicht alle 3rd-party-Varianten die ich gefunden habe, fehlen 1 bis 4, aber diese Beschränkungen Generierung valider boards kann eine schwierige Aufgabe sein.

    Antwort:

    Punkt 3 schlägt ein Wert gespeichert werden, der für jede Zelle, die in der Lage ist, um entweder eine Farbe, oder einen Satz falsch/unbestimmt Werte, wobei es einen für jede Farbe.

    Solver konnte wiederholt die Punkte 1 und 2 zusammen mit den Daten gespeichert werden für Punkt 3 auf den kleinen Stadtteilen von Pfaden, die um die enden der Rohre zu immer legen Sie Farben oder legen Sie die unbestimmten Werte falsch.

    InformationsquelleAutor alan2here
Schreibe einen Kommentar