Aufgabe 5: Auf dem Sprung
Zusammen mit 3 Damen lassen sich höchstens 11 Springer
auf dem Brett unterbringen.
Es gibt 7 verschiedene Lösungen. 6 davon werden mit der
gleichen Positionierung der drei Damen erreicht.
Hat jemand 14 oder 28 oder 56 Lösungen gefunden, so spricht
das stark dafür, daß die Symmetrien nicht richtig (bzw. gar nicht) herausgerechnet
wurden. Dafür gab es 1 Punkt Abzug.
Auf welche Art die Symmetrien herausgerechnet wurden,
spielte keine Rolle. Man kann beispielsweise alle Lösungen erzeugen und
durch 8 teilen, oder man wirft bereits während oder direkt nach der Damenpositionierung
die Symmetrien heraus.
Die Lösungen findet man mit Backtracking.
Eine mögliche Vorgehensweise:
Auch hierzu drucken wir das Struktogramm von Tiark Rompf ab:
(sorry, noch nicht da, siehe Aufgabe 2...)
Alternativ kann man auch alle möglichen Springerpositionierungen ohne Damen erzeugen und dann versuchen, diese mit den Damenpositionierungen zu mischen. Dann hat man aber das Problem, daß die Springerpositionierungen die Festplatte sprengen.
Solange man Damen und Springer getrennt voneinander betrachtet, kann man zur Speicherung des Feldes 2 longint-Variablen verwenden. Eine sagt, wo Figuren stehen, die andere, welche Felder damit bedroht sind.
Zwei mögliche Lösungen sind folgende:
|
|
D |
|
|
|
|
|
|
|
|
|
|
D |
|
|
|
|
|
|
|
D |
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
|
|
|
|
|
D |
|
|
|
|
D |
|
|
|
|
S |
|
|
|
|
|
|
|
|
D |
|
|
|
|
|
|
|
S |
|
|
S |
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
|
|
S |
|
|
S |
|
|
|
|
|
|
|
S |
|
S |
S |
|
|
|
|
|
S |
|
|
|
S | S |
|
|
|
S |
|
S | S |
|
S |
|
|
S |
|
|
|
S | S |
|
|
S |
|
S |
Zur 1. Lösung gibt es noch 5 weitere mit gleicher Damenpositionierung, aber anderer Positionierung der Springer.
In der Aufgabenstellung stand deutlich, daß sich die Damen untereinander oder die Springer untereinander nicht bedrohen dürfen. Dennoch gab es Einsendungen, in denen die Springer und genauso die Damen traulich beieinander standen. In diesem Fall passen 2 4 Springer auf das Brett und es gibt 2 Lösungen. Dafür gab es einen Trostpunkt.