Serie-6

Aufgabe 3

Bernd geht wieder in die Schule und der Hausmeister, der eine Schach-Ag leitet, stellt ihm eine knifflige Aufgabe. Stelle 8 Damen so auf das Brett, dass keine eine andere schlagen kann. Das geht doch gar nicht, aber klar doch. Es soll 92 verschiedene Lösungen geben. Dabei wird das Brett natürlich nicht gedreht.
Okay, meint Mike, da jetzt Ferien sind knobeln wir da mal so richtig rum, denn Snowboardfahren darfst du ja eh noch nicht.
Die erste Dame soll auf a1 stehen. Es gibt bei dieser vorgebenen 4 Lösungen und damit kann es bis zu 12 Punkte geben.

Diese Aufgabe war recht knifflig und eine Lösungsformel wohl kaum in Sicht.
Eine Variante des systematischen Probierens besteht darin, dass die von links nach rechts immer nur so hoch gestellt werden wie notwendig und dann auf Widerspruchsfreiheit untersucht wird. Sollte der Fall eintreten, dass alle 8 Damen den Bedingungen entsprechen, dann hat man eine Lösung gefunden, wenn nicht dann wird von rechts beginnend weiter hoch gesetzt.
zu a1 ist b3 die tiefste Variante, dann muss c5 sein dann d2 und nun e4. Für f gibt es aber nun keine Dame mehr, also wird e nach oben verschoben, da geht aber nur noch e8, aber auch hier gibt es keine Dame auf f. Also wird jetzt d nach oben geschoben, da geht jetzt nur als tiefste Variante d7, dann e2, f4 und g6, aber nun gibt es wieder keine Variante auf h ... Dieses Verfahren wird Backtracking genannt.
Die Lösungen:
1. a1b5c8d6e3f7g2h4
2. a1b6c8d3e7f4g2h5
3. a1b7c4d6e8f2g5h3
4. a1b7c5d8e2f4g6h3
Eine vollständige Liste aller Lösungen gibt es in der Zeitschrift ALPHA 2/1977.

Eine interessante Nachfrage gab es von Andreas. Wie viele Damen braucht man mindestens, damit jedes Feld auf dem Brett durch eine Dame erreicht werden kann? Die Antwort ist: Es werden 5 Damen gebraucht. Eine der vielen Lösungen ist: a1b3c5d2e4 s.o. Die Fragestellung, schließt den Fall, dass sich die verwendeteten Damen selber auch schlagen können mit ein.