Backtracking: Springer-Problem beim Schach (Optimierung)

[Antiexperte]

Hallo allerseits! :)

Ich hab da so ein kleines Problem, bei dem ich auf eure Hilfe hoffe:
Wir haben im Informatik-Unterricht momentan Backtracking als Thema.
Dabei sollten wir mit Hilfe von Delphi das "Springer-Problem" vom Schach ausprogrammieren.

Das Grundgerüst habe ich auch schon stehen, aber leider happert es bei uns an der Optimierung.
Mit 7 * 7-Feldern läuft er noch durch, aber bei 8 * 8 dauert es schon >20min auf nem 1GHz Celeron (abgebrochen).

Ich hab das komplette Programm mal als *.zip-Datei angehängt.
Wir arbeiten in der Schule mit Delphi 6.

Kann mir jemand ein paar Tipps + Anleitungen geben, wie ich das Programm noch weiter optimieren kann? :)
Die Struktur der Procedures soll weitesgehend so bleiben, da wir die vorgegeben gekriegt haben. :!:

Das größte Problem an der Sache ist aber, dass die Deadline schon morgen um 10:30Uhr ist.

Ich (und meine Projektmitarbeiten, die aber überhaupt gar keine Ahnung haben :roll: ) wäre(n) da sehr dankbar!
Stehe für weitere Fragen natürlich den Tag über bereit!

Grüße & auf ein harmonisches Zusammenleben im Forum!

:)

[Net7]

Dieser Algo wird Stunden brauchen, was aber nicht direkt am Algo liegt. Sondern an der Vorgehensweise.

Schau mal hier..

Springerproblem

Weiter unten auf dieser Seite ist noch ein Algo mit Heuristik. Der rechnet das in ein Paar Sekunden.

Gruß Net7

[Eichhoernchen]

haben wir gerade in der schule gemacht.. hier haste was.. guckst du Annhang... musste so modifizieren wie du gern hättest!


Ach ja... bau nen abbruchbutton ein ;) kann ganz schön nervig sein


Mist: hätte lesen sollen.. naja schneller wird das auch nicht sein... aber ist vielleicht nen bisschen besser struckturiert als deins. Aber zur optimierung würd ich mir die Seite meines vorredners angucken!

[Antiexperte]

Danke euch beiden erstmal!

Hab mir die Seite mal ausgedruckt und werde mich dann mal dadurch kämpfen.

Hat denn jmd. nich so "ad hoc" nen paar Zeilen Quelltext oder kann mir sagen, WAS ich verändern muss? :oops: :)

[faux]

OT:
Man bedenke, dass das ein 12 Jähriger im Kopf bei "Wetten, dass?" gelöst hat. Er hat das Spielfeld nicht gesehen. :D

[Antiexperte]

Ich war das nich :-D

[schöni]

Hallo!

Habe grad mal die Netzseite aufgerufen, auf der das Springerproblem erklärt ist. Dazu hab ich paar Fragen:

Zitat:

Zur Wiederholung: Die Breitensuche funktioniert mit zwei Beuteln:
1. Beutel 1 ist leer. (In Beutel 1 werden all die Felder geworfen, die mit dem Feld, auf dem der Springer gerade steht (aktuelles Feld), verbunden sind).
2. Beutel 2 ist leer.
3. Die von dem aktuellen Feld aus erreichbaren und freien Felder werden in Beutel 1 geworfen, das aktuelle Feld selbst kommt in Beutel 2.

Warum muss hier noch was in Beutel 1. Der ist doch durch Scritt 1 schon gefüllt? Ich kann doch nur die erreichbaren Felder in Beutel 1 füllen und Alternativen geeignet markieren.

Zitat:

4. Solange Beutel 1 nicht leer ist, wiederhole folgende drei Schritte:
4.1 Nimm ein Feld aus Beutel 1.
4.2 Werfe die Nachfolger dieses Feldes, sofern sie a) frei und b) noch nicht in Beutel 1 oder Beutel 2 sind, in Beutel 1.

Diesen Ablauf hier kann ich mir bildlich überhaupt nicht vorstellen! Der Springer zieht entweder:

-2 Felder hoch, 1 Feld rechts/links
-2 Felder links, 1 Feld hoch/runter
-2 Felder rechts,1 Feld hoch/runter
-2 Felder runter,1 Feld rechts/links

Ich verstehe Schritt 1 so, das ich alle vom Springer erreichbaren Felder in Beutel 1 lege. Und zwar als geeignete Datenstruktur, die aufzeigt, welches Feld Nachfolger ist. Baumstruktur, denk ich mal, und zwar so:



-- --
| | |
--.--
| | |
-- --


Der Punkt in der Mitte soll die Position des Springers sein. Die Striche symbolisieren die möglichen Wege. Immer, egal welche Richtung -> 2 vor(rück,links,rechts) und dann ein Feld
90 Grad versetzt in 2 Richtungen.

Wieso muß ich dann biem Ziehen noch mal Felder in Beutel 1 legen?
Wenn ich die richtige Datenstruktur habe, habe ich doch auch die blegbaren Felder!

Zitat:

4.3 Werfe danach das Feld in Beutel 2.

Verstehe ich so, das ein ausgeführter Zug in Beutel 2 liegt. Ist das richtig?

Zitat:

5. Zähle nun die Felder in Beutel 2 und vergleiche sie mit der Anzahl der noch freie Felder. Sind die beiden Zahlen nicht gleich, so existiert ein Feld oder mehrere Felder, die nicht mehr erreicht werden können.

Was ist das nun schon wieder? Ich dachte (siehe oben), in Beutel 2 seien die Felder, die schon angesprungen wurden? Wo liegt mein Denkfehler?

schöni