Backtracking: Springer-Problem beim Schach (Optimierung)

[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