Aufgabe:
Betrachten Sie das dargestellte Schachbrett. Keine Figur außer dem
weißen Springer darf ziehen. Das Springerproblem besteht darin, zu beweisen,
ob mit dem weißen Springer auf a8 die schwarze Dame auf h1 geschlagen werden kann, wobei einige Felder von weißen Bauern blockiert werden und daher nicht vom Springer betreten werden dürfen. Wenn ja, soll die minimale Anzahl an dafür benötigten Springerzügen angegeben werden.
Problem/Ansatz:
1) Modellieren Sie dieses Problem mit Hilfe eines ungerichteten Graphen und geben Sie eine
Graphentheoretische Formulierung des Springerproblems an.
2) Verwenden Sie einen geeigneten Algorithmus aus der Vorlesung zur Lösung des unten
dargestellten Springerproblems. Erklären Sie Ihre einzelnen Schritte bei der Anwendung
des Algorithmus.