Struktur / Algorithmus für Spiel mit überlappenden Karten lösen

Question

Betrachten wir ein Kartenspiel nach dem Vorbild der Tower Solitaire, Tripeaks oder Fairway Solitaire: Der Tisch besteht aus einer Anzahl von Karten, die sofort verfügbar sind, von denen jeder andere Karten darunter bedeckt werden könnten (zu blockieren sie von abgespielten) . Sie haben eine „Fundament“ Karte, und Sie können eine Karte aus der Tabelle entfernen, wenn sie über oder unter dem Fundament Karte genau einen Rang sind, an welcher Stelle es Ihre neue Basis-Karte wird. Sie haben eine begrenzte Anzahl von Ersatzkarten aus zu ziehen, wenn Sie nicht eine Karte aus der Tabelle spielen können, so dass Sie wollen in der Regel die längste Sequenz von Karten möglich spielen.

Zuerst, wie würden Sie das Board vertreten zu erleichtern, eine Lösung zu finden? Zweitens, was Algorithmus würden Sie verwenden, um die längste spielbare Sequenz zu finden?

Beispiel:

  -4a- -5-
-3-  -2- -4b-

Karten auf den unteren Block Karten auf das Entnehmen von: Sie 4a nicht entfernen können, bis beide 3 und 2 verschwunden sind. Angenommen, Ihre Startkarte ist ein Ass, würde das optimale Spiel hier 2, 3, 4b, 5, 4a. (Sie könnten 2 spielen, 3, 4a statt, aber das ist nicht so gut.)

Ich nehme an, dies sollte als eine Art gerichteten Graphen dargestellt werden. Du müss Kanten von 3 und 2 bis 4a und 2 und 4b bis 5, aber würden Sie auch Kanten zwischen 3 und 2 und zwischen 4a und 5, da eine nach dem anderen spielbar ist? Wenn ja, würde die Tatsache, dass sie in beliebiger Reihenfolge abgespielt werden können (3 dann 2 oder 2, dann 3) einen Zyklus im Graphen bilden, die eine Verwendung der effizienten „längster Weg“ Algorithmen verhindert? (Ich glaube, in einem Diagramm den längsten Weg zu finden, ist NP-vollständig, wenn der Graph Zyklen enthält.)

Answer 1

Was ist, wenn Sie stellen dies als ein Graph von Spiel-Staaten (mit Potential on the fly berechnet nächsten Zustände) -, die keine Schleifen haben, was bedeutet, es auf die möglichen Zustände des Spiels eine gerade DFS ist (die sehr zahlreich sein könnte noch) vom Startpunkt.

Answer 2

Der Punkt ist ein gerichteter azyklischer Graph mit dem wenigsten Knoten möglich, deren Knoten vollständig Zustandsraum erfassen des Problems würde zu konstruieren. Dann können Sie Ihre üblichen Algorithmus ausgeführt werden.

Ich schlage vor, eine Codierung auf der Grundlage der Form der Struktur der verbleibenden Karten auf dem Tisch.

obersten Karte -

Die ersten Daten in dem Zustand könnten die eindeutige ID der am weitesten links sein. (Wie zum Beispiel 4a, ist es einzigartig in dem Sinne, dass es nur eine Karte 4a). Der Rest der Form kann durch eine von -1,0,1 für jede verfügbare Karte (Karte, die bereit ist, zu entnehmen) dargestellt werden beschreiben, wenn die nächste Karte auf der linken Seite auf der gleichen ‚Ebene‘ ist, oder es ist eine Ebene tiefer oder höher. (Dies nutzt die Annahme, dass eine Karte nur zwei andere Karten überlappt und dass die Struktur sieht aus wie die, die Sie in dem Beispiel gegeben haben).