Unabhängig davon, welches Layout für die Kacheln verwendet wird, gibt es eine gute Möglichkeit, die Kacheln auszuspalten, damit Sie dem Benutzer garantieren können, dass zu Beginn des Spiels mindestens ein Pfad zum Vervollständigen des Rätsels vorhanden ist das Spiel gewinnen?
Offensichtlich können sie sich abhängig vom Spielzug des Benutzers vom Gewinn abschneiden. Ich möchte nur in der Lage sein, dem Benutzer immer zu sagen, dass das Puzzle gewinnbar ist, wenn sie gut spielen.
Wenn Sie zu Beginn des Spiels Steine nach dem Zufallsprinzip platzieren, ist es möglich, dass der Benutzer einige Züge machen kann und nicht mehr kann. Das Wissen, dass ein Puzzle zumindest lösbar ist, sollte mehr Spaß beim Spielen machen.
Spiele das Spiel rückwärts.
Teile zufällig Stücke paarweise aus, an Stellen, wo du sie in den Haufen schieben könntest. Du wirst einen Weg finden müssen zu wissen , wo du Teile platzieren darfst, um zu einem Haufen zu kommen, der mit einem voreingestellten Muster übereinstimmt, aber du wirst das sowieso brauchen.
Ich weiß, dass dies eine alte Frage ist, aber ich bin darauf gestoßen, als ich das Problem selbst gelöst habe. Keine der Antworten hier ist ziemlich perfekt, und einige von ihnen haben komplizierte Vorbehalte oder brechen pathologische Layouts. Hier ist meine Lösung:
Löse die Tafel (vorwärts, nicht rückwärts) mit nichtmarkierten Steinen. Entferne jeweils zwei freie Steine. Drücke jedes Paar, das du entfernst, auf einen "matched pair" Stack. Oft ist dies alles, was Sie tun müssen.
Wenn Sie auf eine Sackgasse treffen (numFreeTiles == 1), setzen Sie einfach Ihren Generator zurück :) Ich habe festgestellt, dass ich in der Regel keine Sackgassen triff und bis jetzt eine maximale Anzahl von Wiederholungen von 3 für die 10- oder so Layouts habe ich ausprobiert. Sobald ich 8 Wiederholungen treffe, gebe ich auf und ordne einfach den Rest der Kacheln zufällig zu. Dies erlaubt mir, den gleichen Generator sowohl für das Einrichten der Karte als auch für die Shuffle-Funktion zu verwenden, selbst wenn der Spieler es vermasselte und einen 100% unlösbaren Zustand erreichte.
Eine andere Lösung, wenn Sie auf eine Sackgasse treffen, ist das Zurückgehen (das Abspringen des Stapels, das Ersetzen von Kacheln auf dem Board), bis Sie einen anderen Pfad wählen können. Gehen Sie einen anderen Pfad ein, indem Sie sicherstellen, dass Sie Paare finden, die die ursprüngliche blockierende Kachel entfernen.
Leider kann dies je nach Board für immer wiederholt werden. Wenn Sie ein Paar entfernen, das einer Straße ohne Ausgang ähnelt, bei dem alle nachfolgenden "Straßen" eine Sackgasse sind und es mehrere Sackgassen gibt, wird Ihr Algorithmus niemals abgeschlossen. Ich weiß nicht, ob es möglich ist, eine Platine zu entwerfen, wo dies der Fall ist, aber wenn ja, gibt es immer noch eine Lösung.
Um dieses größere Problem zu lösen, behandeln Sie jeden möglichen Board-Zustand als Knoten in einer DAG, wobei jedes ausgewählte Paar eine Kante in diesem Graphen ist. Führen Sie eine zufällige Traversierung durch, bis Sie einen Blattknoten in der Tiefe 72 finden. Behalten Sie Ihre Traversalgeschichte im Auge, so dass Sie nie einen Abstieg wiederholen.
Da Sackgassen in den Layouts, die ich verwendet habe, seltener sind als Lösungen zum ersten Mal, fällt mir sofort eine Hybridlösung ein. Versuchen Sie zuerst, es mit minimalem Speicher zu lösen (speichern Sie ausgewählte Paare auf Ihrem Stack). Sobald Sie die erste Sackgasse erreicht haben, degradieren Sie beim Besuch jedes Knotens die volle Markierungs- / Kantengenerierung (faule Bewertung wenn möglich).
Ich habe jedoch sehr wenig über die Graphentheorie gelernt, also gibt es vielleicht eine bessere Lösung für das DAG-Zufallstraversal / Suchproblem:)
Bearbeiten: Sie könnten tatsächlich jede meiner Lösungen mit dem Erstellen der Platine in umgekehrter Reihenfolge verwenden, ala der 13. Oktober 2008 Post. Sie haben immer noch die gleichen Vorbehalte, weil Sie immer noch mit Sackgassen enden können. Das Erzeugen einer Karte in umgekehrter Richtung hat jedoch kompliziertere Regeln. Zum Beispiel, Sie werden garantiert Ihre Einrichtung zu versagen, wenn Sie nicht mindestens einige Ihrer Reihen mit dem ersten Stück in der Mitte, wie in einem Layout w / 1 langen Reihe beginnen. Das Auswählen eines völlig zufälligen (legalen) ersten Zuges in einem Vorwärtslösungsgenerator führt eher zu einer lösbaren Karte.
Das Einzige, was ich mir ausgedacht habe, ist, die Spielsteine als ein umgekehrtes Mahjong-Solitaire-Spiel in passende Paare zu legen. An jedem Punkt während der Platzierung der Kacheln sollte das Board so aussehen, als wäre es in der Mitte eines echten Spiels (dh keine Kacheln schweben 3 Schichten über anderen Kacheln).
Wenn die Kacheln in einem umgekehrten Spiel in passenden Paaren platziert werden, sollte es immer mindestens einen Vorwärtspfad ergeben, um das Spiel zu lösen.
Ich würde gerne andere Ideen hören.
Ich glaube, die beste Antwort wurde bereits nach oben gedrängt: Erstellen eines Sets, indem man es "rückwärts" löst - also mit einem leeren Brett beginnt, dann irgendwo ein Paar hinzufügt, ein weiteres Paar in einer lösbaren Position hinzufügt und so weiter. ..
Wenn du einen "Big Bang" bevorzugen würdest (der den ganzen Satz zufällig am Anfang erzeugt), bist ein sehr Mach-Entwickler oder fühlst du dich einfach nur masochistisch, kannst du alle Paare darstellen, die du nehmen kannst aus der gegebenen Menge und wie sie über einen gerichteten Graph aufeinander angewiesen sind.
Von dort müssen Sie nur die transitive Schließung dieser Menge erhalten und bestimmen, ob es mindestens einen Pfad von mindestens einem der ursprünglichen legalen Paare gibt, der zum gewünschten Ende führt (keine übrig gebliebenen Kachelpaare) / p>
Die Implementierung dieser Lösung bleibt dem Leser als Übung überlassen: D
Hier sind Regeln, die ich in meiner Implementierung verwendet habe.
Wenn Sie eine Heap erstellen, suchen Sie für jeden Bund eines Paares getrennt nach Zellen (Orten), die sind:
Diese Regeln garantieren nicht, dass ein Build immer erfolgreich ist - manchmal bleiben die letzten 2 freien Zellen selbstblockierend und der Build sollte wiederholt werden (oder mindestens die letzten Bünde) In der Praxis hat "Schildkröte" nicht mehr als 6 Wiederholungen eingebaut.
Die meisten existierenden Spiele scheinen zu beschränken, erste ("first on row") Bünde irgendwo in der Mitte zu platzieren. Dies führt zu bequemeren Konfigurationen, wenn keine Bünde an den Kanten sehr langer Reihen vorhanden sind, und bleiben so lange auf dem Spiel, bis sich der letzte Spieler bewegt. "Mittel" ist jedoch für verschiedene Konfigurationen unterschiedlich.
Viel Glück:)
P.S. Wenn du Algo gefunden hast, der lösbare Heaps in einer Runde erstellt - lass es mich wissen.
Sie haben 144 Spielsteine im Spiel, jede der 144 Spielsteine hat eine Blockliste. (obere Kachel auf Stapel hat eine leere Blockliste)
Alle gültigen Moves erfordern, dass ihre "current__vertical_Block_list" leer ist. Dies kann eine 144x144 Matrix sein, also 20k Speicher plus eine LINKE und RECHTE Blockliste, ebenfalls jeweils 20 k.
Generiere eine gültige Bewegungstabelle aus (remaning_tiles) UND ((leere AKTUELLE VERTIKALE BLOCKLISTE) und ((leere AKTUELLE LINKE BLOCKLISTE) ODER (leere AKTUELLE LINIE BLOCKLISTE))))
Wähle 2 zufällige Kacheln aus der gültigen Bewegungstabelle und zeichne sie auf Aktualisiere die (aktuellen Tabellen Vert, links und rechts), zeichne die Tiles auf einem Stapel auf
Jetzt haben wir eine Liste von Zügen, die ein gültiges Spiel darstellen. Ordne jedem der 72 Züge passende Kacheltypen zu.
Für herausfordernde Spiele, verfolgen Sie, wann jede Kachel verfügbar ist. Finde Sätze, die sind (früh früh früh zu spät) und (spät zu spät zu spät), da es leer ist, findet man 1 EE 1 LL- und 2 LE-Blöcke .. des 2 LE-Blocks, finde ein EARLY, das JEDEN anderen FRÜHER blockiert ( außer Rechtsblockierung eines linken Seitenteils)
Sobald Sie ein gültiges Spiel mit der Bestellung haben.
Solitaire? Nur eine Vermutung, aber ich würde annehmen, dass Ihr Computer das Spiel (oder in der Nähe davon) schlagen müsste, um das festzustellen.
Eine andere Möglichkeit könnte sein, mehrere voreingestellte Layouts zu haben (die es erlauben, zu gewinnen, gemischt mit deinem aktuellen Level).
Bis zu einem gewissen Grad können Sie versuchen, sicherzustellen, dass eines der 4 Kacheln nicht mehr als X Ebenen unter einem anderen X ist.
Die meisten Spiele, die ich sehe, haben den Shuffle-Befehl, wenn jemand hängenbleibt.
Ich würde versuchen, eine Mischung aus Dingen und sehen, was am besten funktioniert.