Damenproblem
Inhaltsverzeichnis
- 1 Aufgabenstellung:
- 2 Geschichte des Problems:
- 3 Erweiterung des Problems:
- 4 Der Begriff Backtracking:
- 5 Algorithmus des "n-Dameproblems":
- 6 Erweiterung des Programms
- 7 Das Programm
Aufgabenstellung:
Bei dem „8-Damenproblem“ soll es Ziel sein, 8 „Damen“ auf ein Schachbrett aufzustellen, ohne dass eine „Dame“ eine andere bedroht (die Figurenfarbe wird dabei ignoriert, und es wird angenommen, dass jede Figur jede andere angreifen könnte).
Zu beachten ist dabei, dass eine „Dame“ sowohl vertikal, horizontal als auch diagonal soweit sie möchte, angreifen kann.
Bewegungsmöglichkeiten einer Dame:
Geschichte des Problems:
Das „8-Damenproblem“, welches als ein weit bekanntes und behandeltes Schachproblem bekannt ist, wurde im Jahr 1845 zuerst formuliert.
Max Friedrich Wilhelm Bezzel, der bis in das Jahr 1870 der einzige bedeutendste Meisterspieler im Schach in Bayern war, stellte das Problem erstmals in einer Schachzeitung auf. Bereits im Jahr 1850 hatte ein gewisser Dr. Nauck, welcher blind war, alle möglichen 92 Lösungen veröffentlicht, während der berühmte Mathematiker Gauß erst 72 gefunden hatte.
(Falls man die durch Spiegelung oder durch Rotationen des Bretts ergebenden Lösungen nicht mit zählt, erhält man 12 verschiedene Lösungen).
Der englische Mathematiker J. W. L. Glaisher bewies im Jahr 1874, dass es nicht mehr als 92 Lösungen geben könnte, womit das Problem vollständig gelöst war.
Erweiterung des Problems:
Das „8-Damenproblem“ lässt sich auch zu einem „n-Damenproblem“ erweitern. Da ein gewöhnliches Schachbrett 8 x 8 Felder besitzt, muss das Schachbrett beim „n-Damenproblem“ folglich auf n x n Feldern erweitert werden. So wird zu Hinführung zum „8-Damenproblem“ oftmals mit dem „4-Damenproblem“ gearbeitet, da es sich auf Grund seiner geringeren Komplexität besser eignet. Das „1-Damenproblem“ wäre zu einfach und das „2- bzw. 3-Damenproblem“ ist nicht zu lösen.
Lösung des „4-Damenproblems" durch probieren:
Um zu einer Lösung des „4-Damenproblems“ zu kommen, kann man verschiedene Konstellationen ausprobieren. Man fängt an und setzt eine „Dame“ in das obere linke Feld (also in die 1.Spalte|1.Zeile). Danach markiert man sich die Felder, die nun nicht mehr besetzt werden können. Folglich muss man in der zweiten Zeile der nächsten Spalte weiter machen und so weiter. Kann man keine weitere „Dame“ mehr setzen und hat man noch keine 4 „Damen“ auf dem Schachbrett verteilt, dann ist es zwingend notwendig, für die letzt gesetzte „Dame“ eine neue Position zu suchen. Scheitert der Versuch trotzdem muss man die Position der davor gesetzten „Dame“ verändern und danach die der zuletzt gesetzten. Reicht dies immer noch nicht, folgt man diesem Schema bis man wieder bei der ersten „Dame“ angekommen ist und man ihre Position verschieben muss. (demnach 1.Spalte|2.Zeile).
Da mann die nächste Dame immer in die nächste Spalte setzt´, ist es nur notwendig, wenn man sich die bedrohten Felder horizontal, diagonal nach rechts oben und diagonal nach rechts unten makiert. Nach links braucht man nicht zu makieren, da man ja bei der "neuen Dame" immer prüft ob sie von einer "alten Dame" geschlagen werden kann.
Beispiellösung des 4-Damenproblems:
Schritt1
Schritt2
Schritt3
Schritt4
Schritt5
Schritt6
Schritt7
Schritt8
Schritt9
Schritt10
Beispiellösung des "8-Damenproblems"
Der Begriff Backtracking:
„Backtracking ist das Zurückverfolgen im Rahmen einer baumartigen Lösungsuche von einer Sackgasse im Sinne der Problemlösung aus zu einer vorhergehenden Stelle im Lösungsbaum, von der aus ein erneuter Lösungversuch gestartet werden soll.“
(Quelle: http://ivs.cs.uni-magdeburg.de/~dumke/EAD/Skript25.html)
Aufgrund unseres Versuchs zur Lösung des „4-Damenproblems“ und der Definition des Begriffs Backtracking können wir nun sagen, dass unser „n- bzw. 8-Damenproblem“ mit Hilfe des Lösungswegs Backtracking gelöst werden kann. Ziel ist es demnach im Folgenden einen allgemein gültigen Algorithmus zu entwickeln.
Des weiteren können wir an dieser Stelle schon behaupten, dass es sich um einen rekursiven Algorithmus handeln wird, da wir wie in dem Beispiel des "4-Damenproblems" deutlich gemacht haben, dass wir immer wieder das gleiche tun nur auf einer höheren Stufe (Vergleich Monsterkurven, die wir dieses Halbjahr behandelt haben).
Algorithmus des "n-Dameproblems":
Um einen effizienten Algorithmus für das "n-Damenproblem" zu finden, sollten wir uns zuerst überlegen, welche grundlegenden Prozeduren wir bei der Lösungssuche benötigen.
Offensichtlich ist, dass wir einen Algorithmus brauchen, der in der Lage ist eine Dame in die jeweilige Spalte zu setzen. Somit können wir gleich schon feststellen, dass es sinnvoll wäre eine Variable Spalte beim Prozedurenaufruf mit zu übergeben. Den Prozedurenkopf nennen wir "NeueSpalte". Auch können wir uns im voraus schon darauf vorbereiten, dass es sich um einen rekursiven Algorithmus handeln sollte, da zum einen n beliebig gewählt werden kann und zum anderen die Prozedur auch einige Schritte zurückgehen muss, wenn das Aufstellen der Damen bei einer Variante missglückt ist. Außerdem wäre es sinnvoll wenn sich die Procedure selbst aufrufen könnte, wenn sie es geschafft hat eine "Dame" in eine entsprechende Spalte zu setzten, um die nächste "Dame" in die nächste Spalte setzen zu können.
Weiterhin sollten wir uns überlegen, wie wir feststellen können, ob ein Feld von einer "Dame" bereits bedroht ist. Es wäre sicherlich hilfreich eine Funktion zu haben, die einen Rückgabewert "wahr" oder "falsch" liefert. An diese Funktion sollten die Koordinaten der "neuen Dame" übergeben werden. Diese Funktion nennen wir "IstFeldBedroht".
Daraus lässt sich schlussfolgern, dass wir schließlich auch eine Prozedur brauchen, die diverse Felder auf "bedroht" setzt. Dabei können wir gleich schon erkennen, dass es lediglich nötig sein wird, die Diagonalen nach rechts oben und unten und die Horizontale nach rechts auf eine Bedrohung zu untersuchen (siehe "Lösung des 4-Damenproblems durch probieren"). Es wäre auch sinnvoll, wenn die Felder der Diagonalen und der Horizontalen immer dann auf bedroht gesetzt werden, wenn wir eine Dame in ein entsprechendes Feld setzen. Somit müssten wir die Koordinaten der Dame (Spalte|Zeile) an die Prozedur übergeben. Wir sollten uns gleich zu Anfang auch überlegen, wie unser Programm sich am besten merken kann, dass Felder bedroht sind. Dabei bietet sich an, ein bzw. mehrere Arrays zu verwenden, deren Felder entweder "wahr" oder "falsch" sind. Weiterhin sollten wir auch eine Variable Schalter mit übergeben, die die entsprechenden Felder entweder auf "wahr" oder "falsch" setzt. Dies ist hilfreich, wenn wir eine Dame wieder löschen möchten, da auch dann die Bedrohung gelöscht werden muss. Nennen wir diese Prozedur "FeldBedrohungSetzen".
Pseudocode von "NeueSpalte"
|
Prozedur "NeueSpalte"
|
Erklärung des Pseudocodes:
Wenn man den Pseudocode betrachtet, dann könnte man sich vielleicht die Frage stellen, warum der Algorithmus von der 1. bis zur letzten Zeile den Programmablauf durchführen soll. Die Begründung hängt damit zusammen, dass der Algorithmus möglichst alle Konstellationen finden soll, die die n "Damen" auf dem Schachbrett besetzen können.
Falls das Feld nicht bedroht ist, dann wird die Dame und die entsprechende Bedrohung gesetzt. Bis hierhin ist der Algorithmus noch trivial. Überspringen wir die Zeile "falls die letzte Spalte erreicht wurde", dann folgt als nächstes, dass die gleiche Prozedur wieder aufgerufen wird um die nächste Spalte abzuarbeiten. Das Programm löscht also zunächst nicht die Dame und die Bedrohung, was sehr wichtig ist, sondern arbeit in der Rekursion weiter. Falls jetzt eine Sackgasse kommt, also alle Felder bedroht sind, dann wird die if-Schleife gar nicht durchlaufen, sondern die Prozedur wird ohne eine Dame zu setzen oder zu löschen beendet. Danach wird die Prozedur, die zuvor aufgerufen wurde, abgearbeitet, die bei dem rekursiven Aufruf stehen geblieben ist. Da dieser Weg nun eine Sackgasse war, wird die Dame gelöscht und in die nächte oder übernächste usw. Zeile gesetzt, falls dieses Feld unbedroht ist. Anderenfalls geht die Prozedur wie eben beschrieben immer weiter zurück.
Somit wird klar, warum Zeile 1 bis bis letzte Zeile durchlaufen werden muss, da nur so alle möglichen Lösungen gefunden werden können.
Kommt es dazu, dass eine Lösung gefunden wurde kommt es zur Grafischen Ausgabe.
Jetzt könnte man die berechtigte Behauptung aufstellen, dass der Algorithmus doch äußerst ineffizient sein muss, da er in seiner momentanen Form weiter arbeitet und nur die letzte Konstellation für den Benutzer sichtbar ausgeben würde. Deshalb sollten wir uns überlegen, dass die Prozedur zumindest teilweise beendet werden sollte, falls eine Lösung gefunden wurde, um anschließend durch den Benutzer wieder fortgesetzt werden zu können. Erweitern wir den Pseudocode um den Aufruf "Anhalten", damit wir dann die Prozedur zu gegebenem Zeitpunkt wieder fortsetzen können. Zu dem Algorithmus von Anhalten wollen wir später kommen.
|
Prozedur "NeueSpalte"
|
Verdeutlichung am "4-Damenproblem"
|
Prozedur "NeueSpalte"
|
|
Die Prozedur wird wieder aufgerufen:
|
|
|
|
| Im nächsten Schritt wird die vorherige Prozedur, die bei uns in der 2. Zeile steht, weiter fortgesetzt. Nun wird die Dame und ihre Bedrohung gelöscht, um sie anschließend in die nächste Zeile setzen zu können.
|
|
|
Dies wird jetzt immer weiter so fort gesetzt bis schließlich eine Möglichkeit gefunden wurde
|
siehe oben in der Bilder-Gallerie |
Schließlich wird die Prozedur in der letzten Spalte aufgerufen und eine Möglichkeit gefunden...
|
|
Der eigentliche Quelltext von "NeueSpalte"
procedure TMainForm.NeueSpalte(Spalte : Integer);
var Zeile : Integer;
begin
for Zeile:= 1 to SpinEdit1.Value do // SpinEdit1.Value gibt die Anzahl der Zeilen bzw. Spalten an und somit der Damen
begin
if (IstFeldBedroht(Spalte, Zeile) = false) then
begin
Damenbesetzung[Spalte]:= Zeile; // ein eindimensionales Array, welches sich die Position der Dame merkt
FeldBedrohungSetzen(Spalte, Zeile, true);
if Spalte = SpinEdit1.Value then
begin
inc(Anzahl);
Edit1.Text:= IntToStr(Anzahl); // gibt die Anzahl der Möglichkeiten aus
GrafischeAusgabe;
Anhalten;
end
else NeueSpalte(Spalte+1);
FeldBedrohungSetzen(Spalte, Zeile, false);
Damenbesetzung[Spalte]:= 0; // 0 heißt, dass keine Dame gesetzt wurde
end;
end;
end;
Anhand des Pseudocodes und dem Beispiel am "4-Damenproblem" müsste die Prozedur "NeueSpalte" jetzt verständlich geworden sein.
Pseudocode von "FeldBedrohungSetzen"
|
Prozedur "FeldBedrohungSetzen"
|
Erklärung des Pseudocodes von "FeldBedrohungSetzen"
Zuerst einmal sollte man wissen, dass der Prozedur diverse Werte übergeben werden müssen. Zum einen müssen die Koordinaten der gesetzten / gelöschten Dame mit übergeben werden, zum anderen muss ein Wert übergeben werden, der sagt, ob eine Bedrohung gelöscht oder gesetzt werden soll.
Spalte und Zeile übernehmen die Aufgabe der Koordinaten. Der Schalter sagt nun, ob eine Bedrohung gesetzt oder gelöscht wird. Sinnvoll ist es den Schalter vom Typ Boolean zu wählen, da dieser "true" und "false" übergeben kann. Es wäre natürlich auch möglich sich einen eigenen Typ zu definieren, der Bedrohung oder KeineBedrohung mit übergibt. Ich habe mich für ersteres entschieden.
Bei der Abspeicherung wird es nun etwas komplizierter. In meinem Pseudocode übernehmen drei verschiedene Arrays, die auch jeweils von Typ boolean sind, diese Aufgabe. Somit kann ein einzelnes Feld in derm Array durch den Schalter auf "true" oder "false" gesetzt werden.
Wie genau die Abspeicherung und Ausgabe erfolgt, sodass man auch abfragen kann welche Felder allesamt bedroht sind, wird im folgenden erklärt:
Fangen wir mit dem Einfachsten an, die Abspeicherung der Horizontalen. Dafür ist es nur notwendig dass wir uns die Zeile merken. Dementsprechend setzen wir in dem Array AZeile die Kooridinate "Zeile" ein (siehe Pseudocode). Somit ist nicht nur das Feld sondern gleich die ganze Spalte auf bedroht gesetzt.
Bei der Aufwärtsdiagonalen müssen wir einen kleinen Trick anwenden. Betrachten wir die Felder genau. Wenn man die Zeile und die Spalte addiert, merkt man, dass dieser Diagonale entlang immer die selbe Zahl herauskommt. In diesem Fall wäre dies fünf:
(1|4): 1 + 4 = 5
(2|3): 2 + 3 = 5
usw.
Das heißt für uns, wenn wir uns die Zahl fünf merken, können wir jederzeit genau sagen um welche Aufwärtsdiagonale es sich handelt, da es jeweils nur eine Aufwärtsdiagonale mit der selben Zahl gibt, die sich aus der Addition von Spalte und Zeile zusammensetzt.
Bei der Abwärtsdiagonalen müssen wir einen ähnlichen Trick anwenden. Wenn man von der Spalte die Zeile abzieht, merkt man, dass dieser Diagonale entlang immer der selbe Wert herauskommt. In diesem Fall wäre die minus drei:
(1|4): 1 - 4 = -3
(2|5): 2 - 5 = -3
usw.
Für uns heist dass, dass wir uns nur -3 meken müssten, um genau zu sagen um welche Abwärtsdiagonale es sich handelt. Dies geschiet in dem Array für die Abwärtsdiagonale
Der Quelltext von FeldBedrohungSetzen
procedure TMainForm.FeldBedrohungSetzen(Spalte, Zeile : Integer; Schalter : Boolean); begin AZeile[Zeile]:= Schalter; AAufDiag[Zeile + Spalte]:= Schalter; AAbDiag[Spalte-Zeile]:= Schalter; end;
Pseudocode von "IstFeldBedroht"
|
Funktion "IstFeldBedroht"
|
Erklärung des Pseudocodes von "IstFeldBedroht"
Der Funktion "IstFeldBedroht" muss selbstverständlich auch Spalte und Zeile übergeben werden. Den Schalter braucht man diesmal jedoch nicht. Anstelle des Schalters brauch die Funktion jedoch einen Rückgabewert, der Boolean sein muss, da wir für die Arrays auch Boolean als Datentyp gewählt haben.
Die Abfrage ist trivial. Man prüft lediglich, ob das entsprechende Feld, welches sich aus Zeile bzw. Zeile und Spalte ergibt, auf true gesetzt ist. Falls dies so sein sollte, wird das Funktionsergebnis auch "true", ansonsten wird es "false"
Der Quelltext von "IstFeldBedroht"
function TMainForm.IstFeldBedroht(Spalte, Zeile : Integer) : Boolean; begin if (AZeile[Zeile] = true) or (AAufDiag[Spalte + Zeile] = true) or (AAbDiag[Spalte-Zeile] = true) then Result:= true else Result:= false; end;
Die Sache mit Application.HandleMessage
Die Prozedur "Anhalten"
Wie ihr euch sicherlich noch erinnern könnt, habe ich oben eine Prozedur "Anhalten" angesprochen, die wir bis jetzt nicht weiter untersucht haben.
"HandleMessage unterbricht die Ausführung einer Anwendung, damit Windows eine einzelne Botschaft aus der Windows-Botschaftswarteschlange verarbeiten kann, bevor die Steuerung wieder an die Anwendung zurückgegeben wird. Wenn die Botschaftswarteschlange leer ist, generiert HandleMessage ein OnIdle-Ereignis und beginnt die Aktualisierung der Aktionen in der Anwendung." Dies ist die Definition von HandleMessage, die uns Delphi liefert.
Was genau heißt das für uns?
In unserer Prozedur "NeueSpalte" können wir uns diese Application von Nutzen machen. Rufen wir Anhalten auf, passiert folgendes:
|
Prozedur "Anhalten"
|
Das heißt also, dass die Prozedur in einen sogenannten "Leerlauf" übergeht. Man könnte anstelle von Application.HandleMessage auch Application.ProcessMessage benutzen. Ich habe dabei jedoch festgestellt, als ich den TaskMenager aufrief, dass meine Cpu-Auslastung schlagartig auf ca. 50% hochging. Bei HandleMessage dagegen bleibt meine Auslastung bei ca. 1-2%, was natürlich besser ist. Die Frage nach dem Warum liefert auch Delphi:
"Hinweis: ProcessMessages ermöglicht nicht, dass die Anwendung in den Leerlauf übergeht. Hier liegt ein Unterschied zu HandleMessage."
Prinzipiell ist es zwar möglich auch Application.ProcessMessages zu verwenden, wie ich festgestellt habe, jedoch ist es nicht besonders gut dafür geeignet.
Zum Schluss muss man sich noch die Frage stellen, wie man die Prozedur wieder fortsetzen kann oder wie sich die Suche beenden lässt.
Dazu verwenden wir die Prozedur "WeiterSuchen" und "Aufhoeren".
Der Quelltext von "Anhalten"
procedure TMainForm.Anhalten;
begin
repeat
Application.HandleMessage;
until (Weiter = true) or (Schluss = true); // zu Weiter und Schluss kommen wir gleich
Weiter:= false; // eine Erklärung dazu folgt auch im Weiteren
end;
Die Prozedur "WeiterSuchen" und "Aufhoeren"
Die Prozedur "WeiterSuchen" ist trivial. Wie wir oben festgestellt haben, muss der Benutzer diese Aufforderung tätigen. Dies vermag er, indem er in eine globale Variable in der Prozedur "WeiterSuchen" auf "true" setzt, wenn er einen bestimmten Schalter betätigt.
Somit wird die Schleife in "Anhalten" unterbrochen. Am Ende dieser Schleife wurde die Variable wieder auf false gesetzt, sodass die Schleife auch beim nächsten mal, wenn Anhalten aufgerufen wird, auf "false" steht.
|
Prozedur "WeiterSuchen"
|
Die Prozedur "Aufhoeren" unterscheidet sich nicht wesentlich. Nur eine andere Variable, wird auf "true" gesetzt, die jedoch anschließend von der Prozedur "Anhalten" nicht mehr auf "false" gesetzt wird und somit alle Möglichkeiten in rascher Folge durchlaufen werden. Dies ist nur nützlich, da wir am Ende die Anzahl aller Möglichkeiten wissen möchten.
|
Prozedur "Aufhoeren"
|
Der Quelltext von "WeiterSuchen" und "Aufhoeren"
procedure TMainForm.WeiterSuchen; begin Weiter:= true; end;
procedure TMainForm.Aufhoeren; begin Schluss:= true; end;
Erweiterung des Programms
Eine interressante Erweiterung des Programms, die ich ebenfalls eingebaut habe, jedoch hier nicht näher erklären werde, da ich denke, dass der Algorithmus nichts mehr mit dem eigentlichen Problem zu tun hat, ist, dass der Benutzer die Damen selbst setzen kann. Danach kann er das Programm dazu auffordern, zu kontrollieren, ob der Benutzer die Damen auch wirklich richtig gesetzt hat.
Das Programm
Hier könnt ihr euch mein Programm runterladen: Datei:MeinProgramm.zip
