Lösungsalgorithmus für Solitär(Brettspiel)

[Rantwik]

Hallo,

ich möchte gerne einen Lösungsalgorithmus in mein Solitärspiel(Beschreibung des Spiels bei Wikipedia) implementieren. Ansich habe ich das auch schon getan doch rekursives Backtracking ist viel zu langsam. Selbst wenn es gut läuft warte ca. 30 Sekunden auf ein Ergebnis was für einen spielenden Nutzer wohl etwas zu lange sein könnte.

Der Zweck der Methode soll die Möglichkeit sein den Nutzer nach jedem Zug mitteilen zu können ob das Spielfeld noch komplett lösbar ist(nur noch ein Stein über und dieser in der Mitte platziert) und auf Wunsch möchte ich den Nutzer auch den nächsten sinnvollen Zug anzeigen.

Nachdem ich ein komplettes Mittagessen auf den nächsten Zug wartete und keine Endlosschleife finden konnte überschlug ich kurz die Anzahl der möglichen Varianten und mir wurde einwenig übel... Daher habe ich mich nun dafür entschieden das ich nicht während des Spielens die Lösung berechnen möchte sondern das ich entweder die Daten und/oder einen Generator mitliefere der die Ergebnisse für das komplette Spiel berechne.

Nun kommt endlich ihr ins Spiel:
Mit rekrusiven Backtracking wird das generieren der Daten wohl mindestens ein paar Tage in Anspruch nehmen und daher brauche ich nun einen effizienteren Algorithmus... Könnt ihr mir bitte Tipps, Vorschläge oder am besten sogar einen vollständigen Algorithmus geben der das ganze zumindest innerhalb eines Tages erfüllen kann?

Es geht um das englische Brett(Abb. 4 bei Wikipedia) mit 33 Feldern und 32 Steinen

Viele Grüße,
Rantwik

 

[Marco13]

Es gibt (natürlich) schon fertigen Code für sowas: peg-solitaire - Project Hosting on Google Code

Solve it for
* the center position: [...] (requires 500MB memory and ~10 minutes)
* for all start positions: [...] (requires 5GB memory and ~3-4 hours)

(Falls du das meintest ???:L )