ANSI-C: Künstliche Intelligenz: Knight Moves - Problem

[Plüschhase]

Hallo,

ich habe ein Problem aus dem Bereich der Künstlichen Intelligenz. Und zwar geht es darum 2 Lösungsansätze für das Problem des Schach-Springers zu finden. Jedes Feld auf dem Brett soll besucht werden. Im original ist es ja gefragt, dass kein Feld zweimal betreten werden darf. Das ist bei mir erstmal zweitrangig.

Einen Lösungsansatz habe ich bereits. Der simpelste eben: Das Pferd springt auf ein freies noch nicht besuchtes Feld in seiner Reichweite. Wenn er in einer Sackgasse landet nimmt er das erstbeste Feld (auch wenn es bereits besucht ist) und sucht erneut ein freies Feld oder springt erneut auf das erstbeste Feld das noch bereits besucht wurde.

Kennt jemand gute Algorithmen zu diesem Problem? Wurden diese Probleme bereits mal mit ANSI-C gelöst und sind irgendwo erhältlich?

Schonmal besten Dank im voraus.

 

[Matthias Reitinger]

Ich kann zwar mit keinem kompletten Sourcecode, aber mit einem Lösungsansatz (der auch das "nur einmal besuchen" mit einschließt) in Pseudocode dienen:

Liste BesuchteFelder;

Funktion RoesselSprung(StartFeld)
{
   Füge StartFeld an das Ende der Liste BesuchteFelder hinzu;
   Wenn Länge der Liste == 64, gebe Liste aus (Lösung gefunden);

   Für alle Felder 'Feld', auf die die Figur von StartFeld aus rein regeltechnisch springen dürfte
   {
      Wenn 'Feld' nicht in BesuchteFelder enthalten ist:
         Rufe RoesselSprung mit Parameter 'Feld' auf;
   }

   Entferne letztes Element der aus Liste BesuchteFelder (== StartFeld);
}

Somit sollten dir alle möglichen Rösselsprung-Lösungen für ein gegebenes Startfeld ausgegeben werden. Einen ähnlichen Algorithmus kann man übrigens auch für das Finden eines Weges durch ein Labyrinth verwenden