Das 8-Damen-Problem

Letztmalig dran rumgefummelt: 20.12.07 11:09:32

	Das Acht Damenproblem ist ein klassisches Schachproblem, das zuerst von M. Bezzel 1845 in einer Schachzeitung veröffentlicht wurde, aber weithin keine Beachtung fand. Erst als die Aufgabe am 1.6.1850 von Dr. Naue erneut zur Diskussion gestellt wurde, fand sie ein großes Echo. Als der blinde Dr. Nauk am 21.9.1850 sämtliche 92 Lösungen publizierte, hatte Gauß erst 72 Lösungen gefunden. Die Gesamtzahl aller möglichen Damenstellungen ist hier immerhin 88 = 224 = 16777216. Dann wären aber alle Felder mit Figuren besetzt. Damen schlagen waagerecht und senkrecht wie Türme, außerdem schräg wie Läufer. Also darf zunächst in jeder Zeile und Spalte des Schachbretts nur eine von ihnen stehen. Für die erste gibt es 8 Möglichkeiten, für die zweite noch 7 usw. Insgesamt sind das 8 • 7 • 6 • ... 2 • 1 = 8! = 40320 Möglichkeiten. Du findest per Algorithmus ein effizientes Verfahren, um alle Möglichkeiten mit vertretbarem Zeitaufwand zu testen um die "richtigen" herauszufinden?
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösunsverfahren Logo für das 8-Dame-Problem Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	Ausgangssituation im .GIF-Format Ausgangssituation im .CDR-Format mit 50 KByte 8-Dame-Problem zum Selbst-Probieren als CorelDraw 11.0-Datei mit 49 KByte
	... und hier eine mögliche Lösung
	Schach und matt - Falk hat schon wieder verloren! Kunststück, wo sein Gegner doch einen Bauern eintauschen konnte und mit zwei Damen der Weg zum Sieg leicht war. Selbst müsste er alle seine acht Bauern in Damen verwandeln können ... Aber so einfach geht das wohl nicht. Vor allem heute nicht mehr, denn für eine Revanche ist es zu spät. Beim Einschlafen denkt er immer noch an seine Idee, mit acht Damen das ganze Schachbrett beherrschen zu können, und dann im Traum passiert es: Zwischen den Damen bricht ein Streit aus. Keine will sich von einer anderen bedroht sehen, also weder in der gleichen Reihe (Zeile oder Spalte) noch in der gleichen Diagonalen mit einer anderen stehen. Ein wüstes Gedränge entsteht, nur unterbrochen vom Rasseln des Weckers. Den ganzen Tag über vergisst Falk dieses Gerangel nicht; abends beschließt er, über das Problem systematisch nachzudenken. Damen schlagen waagerecht und senkrecht wie Türme, außerdem schräg wie Läufer. Also darf zunächst in jeder Zeile und Spalte des Schachbretts nur eine von ihnen stehen. Für die erste gibt es 8 Möglichkeiten, für die zweite noch 7 usw. Insgesamt sind das 8 • 7 • 6 • ... 2 • 1 = 8! = 40320 Möglichkeiten. Falk schreibt eine solche Möglichkeit auf, indem er von links nach rechts (die Schachspieler bezeichnen die Spalten mit a, b, .*., h) die Zeiten (1, 2, ..., 8) notiert, in der die Damen stehen, also: a3, b5, c2, d8, el, f6, g4, h7 entspricht 3528 1647. Doch unter diesen Stellungen sind gewiss solche, bei denen sich Damen wie Läufer untereinander bedrohen; in Falks Beispiel die Damen in der d- und f-Spalte. Wie kann das erkannt werden, ohne die Stellung auf dem Schachbrett aufzubauen? Hier steht eine Dame zwei Spalten weiter rechts auch zwei Zeilen tiefer. Verschieben wir nun jede Dame um so viele Zeilen nach oben, wie ihre Spaltennummer angibt, so stehen diese beiden danach in der gleichen Zeile (eventuell in einem nach oben fortgesetzten Schachbrett). Auch umgekehrt stehen jetzt nur dann zwei Damen in der gleichen Zeile, wenn sie sich schon vorher wie Läufer angriffen. Wie das im Beispiel geht, zeigt die Tabelle unten. Zeile a b c d e f g h Spalte 3 5 2 8 1 6 4 7 Verschiebung +1 +2 +3 +4 +5 +6 +7 +8   4 7 5 12 6 12 11 15 Also bestand auch wirklich nur zwischen den Damen in der d- und f-Spalte ein Läuferangriff - parallel zur Diagonalen a8-hl wohl gernerkt! Für Läuferangriffe parallel zur anderen Diagonalen muss gerade von hinten mit der Addition begonnen werden (Tabelle unten) Zeile a b c d e f g h Spalte 3 5 2 8 1 6 4 7 Verschiebung +8 +7 +6 +5 +4 +3 +2 +1   11 12 8 13 5 9 6 8 Es stellt sich heraus, dass in dieser Stellung auch ein Angriff zwischen den Damen der c- und h-Spalte bestand. Diese Methode, eine Stellung auf Läuferangriffe hin zu prüfen, geht auf C. F. GAUSS (1777-1855) zurück, der schon 1850 erkannte: Eine Vertauschung der Zahlen I, . . ., 8 stellt genau dann eine Lösung des Problems dar, wenn die absolute Differenz zweier Zahlen nie gleich dem Unterschied ihrer Platznummern ist. Damit liefert 35281746 eine Möglichkeit, die acht Damen zu postieren. Falk kann daraus sofort drei weitere Lösungen ableiten, indem er die Stellung (Abb. 1) am linken Brettrand spiegelt oder eine Drehung um 90° im Uhrzeigersinn ausführt oder die gespiegelte noch dreht. Ganz nebenbei überlegt er sich, dass bei einer Spiegelung, ganz gleich, ob an waagerechter, senkrechter oder diagonaler Brettachse, stets eine neue Lösungsmöglichkeit entstehen muss. v Knobelaufgabe 13: Überlegen auch Sie, warum bei Spiegelungen stets eine neue Lösung entsteht! Während aus der Lösung 35281746 durch Spiege-lung und Drehungen nur insgesamt vier Stellungen hervorgehen, gibt es noch elf andere Positionen, die zu Gruppen von jeweils acht Lösungen gehören (Tabelle unten.
	als echte Lösungen ergeben sich somit: 1586 3724 1683 7425 2574 1863 2736 8514 3625 8174 24G8 3175 2617 4835 2758 1463 2571 3864 2683 1475 3584 1726
	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer

1. Problembeschreibung

	Die einzelnen Damen werden solange in der Folgezeile um zwei Felder versetzt plaziert, bis sie sich irgendwann einmal schlagen könnten.
	Man setzt zuerst in das erste Feld oben links eine Dame. In dieser Zeile kann man keine weitere unterbringen, da sie ja durch die erste besetzte bedroht wäre. Also überprüft man nun das erste Feld der zweiten Zeile. Dieses wird aber durch die Dame in Zeile 1 bedroht ebenso das Feld rechts daneben. Erst das dritte Feld ist “unbedroht”, dorthin wird also unsere zweite Dame plaziert. Da durch das Setzen einer Dame die jeweilige Zeile für weitere Damen gesperrt ist, werden nun die Felder der nächsten (dritten) Zeile von links nach rechts daraufhin untersucht, ob sie bedroht sind. An dieser Stelle merkt man, dass man keine Dame in die dritte Zeile setzen kann, da sich alle ihre Felder im Einflussbereich der bisher gesetzten Damen befinden. Also muss die letzte -aussichtslose- Konfiguration so verändert werden, dass man neue Aussichten auf Lösungsmöglichkeiten gewinnt: Man wirft nicht alle Damen vom Brett, sondern sucht nun für Dame 2 in ihrer Zeile die nächste unbedrohte Position, hier das letzte Feld der Zeile 2. Nun kann man von links kommend in der Zeile 3 eine Dame unterbringen, aber in der vierten Zeile ist kein unbedrohter Platz für eine vierte Dame! Also bringt uns auch diese Stellung nicht weiter, und wir gehen zurück zu Dame 3. Rechts von ihr ist in ihrer Zei1e kein unbedrohter P1atz mehr, also wird sie vom Brett genommen. Aus demselben Grund muss Dame 2 danach das Brett verlassen. Es existiert also keine Lösung mit Dame 1 auf ihrem bisherigen Platz: Sie wandert auf das rechte Nachbarfeld. In der zweiten Zeile ist nur das letzte Feld unbedroht, dorthin wird Dame 2 gesetzt. Auf dem ersten Feld inZei1e 3 kann die Dame 3 untergebracht werden, danach kommt auf das dritte Feld der vierten Zeile die vierte Dame, wir haben eine Lösung gefunden. Damit ist aber das Problem noch nicht vollständig gelöst; es sollen ja alle Lösungen gefunden werden. Also entfernt man - nach Ausgabe dieser Lösung die letzte Dame. Es hätte keinen Zweck sie weiter nach recht zu verschieben, ad ja alle Spalten durch die N-1 (noch) gesetzten Damen bedroht sind. Man versucht nun, die Dame in der Zeile darüber auf die nächste unbedrohte Position rechts von sich zu verschieben. Falls man aber keine solche Position findet, nimmt man sie vom Brett und probiert es mit der Dame darüber. Auf diese Art und Weise wird auch die Dame in der ersten Zeile wieder erreicht. Das ganze Verfahren ist beendet, wenn die erste Dame die Feldgrenze überschreitet.
	eine extrem elegante Lösung für das 8-Dame Problem - vorgelegt von Carsten Schwalbe im Schuljahr 2004 im Rahmen eines Programmierprojektes der Jahrgangsstufe 10 startbare EXE-Datei
	das Backtracking-Verfahren Basis des Springer-Problems ist das Verfahren des Backtrackings

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Das Lösungsverfahren für das 8-Dame-Problem ist das Backtracking
	effiziente Lösung nur als rekursiver Algorithmus
	der Kern des diesem Algorithmus entsprechendem Programms zur Lösung des N- Damen Problems besteht also im wesentlichen aus Prozeduren NEUEZEILE und SCHIEBE - das eigentliche Hauptprogramm stellt nur noch das Brett in gewünschter Größe bereit und ruft die Prozedur NEUEZEILE für die erste Zeile auf siehe unten unter Problemlösung
	Jede  der beiden Prozeduren ist  rekursiv, d.h. sie rufen sich selbst auf. Zwischen ihnen besteht die Beziehung einer indirekten Rekursion, d.h. die erste ruft die zweite auf, die wiederum die erste aufruft. Dabei wird eine sehr hohe Rekursionstiefe erkennbar:  N   Rekursionstiefe     4  29   5 87   6 297    .      .   Anzahl der Lösungen N Anzahl   4 2   5 10   6 14   7 40   8 92   9 352   1 724   11 2680   12 1420
	Komplexität empirisch ermittelt mit

3. Lösungsalgorithmus

	Sollte es mindestens eine Lösung geben, dann ist sie grundsätzlich in dem Versuch enthalten, alle Felder mit Damen zu besetzen und anschließend alle diejenigen weg zu nehmen, welche die Eingangsbedingung nicht erfüllen.
	Es ist deutlich zu sehen, dass bei dieser Variante der rekursive Aufruf der Fibonacci-Funktion als letzte Aktion ausgelöst wird. Das o wird mit dem Wert 1 und m mit dem Wert 0 gestartet. So erhält man immer die letzte und die vorletzte Zahl der Fibonacci-Zahl nach der kompletten Abarbeitung, aller Aufrufe und m stellt dann das Ergebnis dar. Durch diese Art haben wir eine Verschachtelung vermieden, und der zeitliche Gewinn ist ab der Größenordnung von 20 und ab 30 bei schnellen Rechnern (Tabelle) erheblich.

4. Programmvorschläge

	Prozedure NEUEZEILE(i:integer);               Suche von  links erstes, unbedrohtes Feld in Zeile i               falls erfolgreich                           dann stelle Dame darauf                                      falls i<N dann NEUEZEILE ( i+1 )                                                     sonst                                                          DRUCKE                                                          entferne Dame in Zeile i                                                          SCHIEBE(i-1)               sonst SCHIEBE(i-1)
	Prozedure SCHIEBE (i: integer);               Suche von links die Dame in Zeile i               Entferne sie               Suche  rechts  davon das nächste unbedrohte Feld               falls erfolgreich                           dann stelle Dame darauf                                      NEUEZEILE ( i+1 )                           sonst fa11s i>1  dann  SCHIEBE(i-1)
	Die Entscheidung, ob ein Feld bedroht ist, liefert die Funktion BEDROHT (zei, spa :integer): boolean;   var k: integer;               K  <--  1               BEDROHT <-- falsch               solange zei - k >= 1 tue        falls  BRETT(zei - k, spa) dann BEDROHT  <-- wahr        falls spa - k >= 1 und BRETT(zei-k, spa-k) dann BEDROHT  <-- wahr        falls spa + k >= 1 und BRETT(zei-k, spa+k) dann BEDROHT  <-- wahr        k <-- k+1

5. Zusammenfassung

	Hier greifen wir unter anderem die Argumente für einen Algorithmus auf und vergleichen, ob Übereinstimmung in allen Punkten gegeben ist.
	Endlichkeit der Beschreibung ist gegeben
	Eindeutigkeit ist gegeben - jeder Schritt ist für jede Bedingung eindeutig fest vorgegeben und lässt keine Abweichung zu
	Effektivität ist gegeben - jeder Schritt ist ausführbar
	Terminierung ist nicht gegeben - der Algorithmus läuft nach erreichen des Zwischenergebnisses 91 ewig und generiert einen Stapelüberlauf
	Determiniertheit ist gegeben, der Folgeschritt nach einer Operation ist immer bekannt

6. Weiterführende Literatur

	Walter Kranzer; „So interessant ist Mathematik“; VEB Deutscher Verlag der Wissenschaften Berlin 1989; © 1989 by Aulis Verlag Deubner & Co. KG Köln

7. Links zum Thema

	Karsten Schwalbe hat im Schuljahr 2003/04 schon mal eine Visualisierung in Delphi geschrieben - hier sein Projekt

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rucksackproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im November 1996