Schachzüge vom Springer berechnen

[Java Noob]

Hi habe folgendes Problem. Auf einem Schachbrett 8*8 Felder steht an irgend einer prosition der Springer. Nun soll für jedes Feld auf dem Schachbrett bestimmt werden wie viel züge man mindestens braucht um mit dem Springer dort hin zu gelangen. Wie der Springer zeiht wird wohl jeder wíssen. Hat einer nen vorschlag wie man das realisieren könnte???


MFG

 

[0xdeadbeef]

Naja, für den Anfang könntest Du mal alle erlaubten und sinnvollen Züge durchprobieren, bis Du auf der Zielposition landest. Wenn Du jeweils alle Möglichkeiten einer "Zugtiefe" absuchst, dann ist die erstee gefundere Möglichkeit auch die kürzeste.
z.B. beim ersten Zug kann der Springer auf 8 verschiedene Felder. Insofern diese alle im Schachfeld liegen, müßten nun die 8 nächsten Positionen dieser 8 Züge bestimmt werden usw.
Als erstes kannst Du natürlich alle Züge ignorieren, die außerhalb des Schachfeldes landen.
als Optimierung würde ich mir zudem die bereits betrachteten Felder markieren (sind ja bloß 64) ud im folgenden ignorieren.

 

[Java Noob]

Danke erst mal für den tipp. Sowas in der art hatte ich mir auch schon überlegt. Aber da ich wie der name schon sagt neu in Java bin, hab ich mit der realisierung noch etwas probleme. Also wenn du oder andere mir noch bissle weiter helfen könten wäre super.

MFG

 

[Beni]

Der Algorithmus der das macht, heisst übrigens "Breitensuche", und da findest du sicher was im Netz :wink:

[Edit: Google-Link Nummer 1]

 

[foobar]

Guckst du hier http://de.wikipedia.org/wiki/Backtracking und hier http://de.wikipedia.org/wiki/Springerproblem

 

[Java Noob]

Leider kann ich damit nicht viel anfangen. Die links sind dafür gedacht das alle Felder einamal berührt werden. Mein Problem ist es aber für jedes Feld zu bestimmen wie viel Züge man braucht um dort hinzugelangen. Hat nocheiner nen vorschlag??

MG

 

[bygones]

mhm - man könnte das ganze doch als einen Graphen sehen, bei dem knoten x mit knoten y verbunden ist, wenn der springer auf x steht und y erreichen kann...

dann kannst du z.b. den Dijkstra Algorthmus nehmen zur Bestimmung des kürzesten Pfads in einem Graphen

 

[Illuvatar]

Du könntest auch A* statt Dijkstra nehmen. Guckst du hier.