Effizienteste Weg, um eine Reihe von Bewegungen in peg solitaire zu berechnen

Question

Da eine willkürliche peg solitaire Board-Konfiguration, was ist der effecient Weg, um jede Reihe von Bewegungen, dass die Ergebnisse in der „Endgame“ Position zu berechnen.

Zum Beispiel der Standard-Ausgangsposition ist:

..***..
..***..
*******
***O***
*******
..***..
..***..

Und die "Endspiel" Position ist:

..OOO..
..OOO..
OOOOOOO
OOO*OOO
OOOOOOO
..OOO..
..OOO..

Peg solitare genauer beschrieben wird, hier: Wikipedia , wir betrachten die „Englisch board“Variante.

Ich bin mir ziemlich sicher, dass es möglich ist, beliebiges Startbrett in nur wenige secconds auf einem vernünftigen Computer zu lösen, sagt ein P4 3 GHz.

Zur Zeit ist dies meine beste Strategie:

def solve:
    for every possible move:
        make the move.
        if we haven't seen a rotation or flip of this board before:
            solve()
            if solved: return
        undo the move.

Answer 1

Die Wikipedia Artikel, den Sie bereits verlinkt erwähnt, dass es nur 3.626.632 möglich Board Positionen, so dass er es einfach für jeden modernen Computer eine erschöpfende Suche nach dem Raum zu tun.

Ihr Algorithmus oben rechts ist, wird der Trick Umsetzung des „haben keine Rotation oder Flip dieser Platte zuvor gesehen“, was Sie tun können, eine Hash-Tabelle. Sie wahrscheinlich brauchen nicht die „rückgängig macht den Umzug“ Linie als eine reale Implementierung würde den Board Staat als Argument für den rekursiven Aufruf übergeben, so dass Sie den Stapel zum Speichern des Staates verwenden würden.

Auch ist es nicht klar, was Sie mit „effizient“ bedeuten könnte.

Wenn Sie alle Sequenzen von Bewegungen suchen, die zu einer Gewinnstufe führen, dann müssen Sie die erschöpfende Suche tun.

Wenn Sie die kürzeste Sequenz finden wollen, dann können Sie eine Branch-and-bound verwenden Algorithmus einige Suchbäume früh abzuschneiden. Wenn Sie mit einem guten statischen heuristischen kommen können, dann können Sie versuchen, A * oder eine seiner Varianten.

Answer 2

Start aus dem abgeschlossenen Zustand und zu Fuß zurück in der Zeit. Jeder Zug ist ein Sprung, dass Blätter einen zusätzlichen Zapfen auf dem Brett.

Zu jedem Zeitpunkt kann es mehrere unmoves sein, das Sie machen können, so dass Sie einen Baum von Bewegungen zu erzeugen werden. Traverse diesen Baum (entweder depth-first oder breadth-) Stoppen jeder Filiale, wenn es den Ausgangszustand erreicht hat oder nicht mehr irgendwelche möglichen Züge. Ausgabe der Liste der Pfade, die zu dem ursprünglichen Ausgangszustand geführt hat.