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:

  1. Berechne alle möglichen Positionierungen für 3 Damen.
  2. Entferne Rotationen und Spiegelungen, so daß nur noch tatsächlich verschiedene Positionierungen übrig bleiben.
  3. Für jede Damenpositionierung versuche, möglichst viele Springer unterzubringen. Maximum merken, alle schlechteren Lösungen gleich vergessen.

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.

Aufgabenstellung
vorherige Aufgabe vorherige Lösung
zurück