Damenproblem
Das Damenproblem ist eine im Jahre 1850 von Carl Friedrich Gauß gestellte Aufgabe:Man finde eine Stellung für acht Damen auf einem Schachbrett, so dass keine zwei Damen sich gegenseitig nach den Regeln des Schach schlagen können (die Figurenfarbe wird dabei ignoriert, und es wird angenommen, dass jede Figur jede andere angreifen könnte). Anders gesagt sollen sich keine zwei Damen die gleiche Reihe, Linie oder Diagonale teilen.
Auf diesem Schachproblem basierte ein in den frühen 1990er Jahren bekanntes Computerspiel, The 7th Guest. Das Problem wurde heute dahingehend generalisiert, dass es gilt, n nicht-dominierende Damen auf einem Brett von n x n Feldern zu positionieren. Für n=8 hat das Damenproblem 12 verschiedene Lösungen (92 Stück, wenn man die sich durch Spiegelung oder Rotation des Brettes ergebenden Lösungen mitzählt).
Table of contents |
2 Siehe auch 3 Weblinks |
Das Damenproblem als Beispiel zum Algorithmen-Design
Das Damenproblem ist ein gutes Beispiel für ein simples, aber nicht triviales Problem, das durch einen rekursiven Algorithmus gelöst werden kann, indem das Problem mit n Damen so aufgefasst wird, dass es gilt, zu jeder Lösung mit (n-1) Damen eine weitere Dame hinzuzufügen. Letztendlich lässt sich jedes Damenproblem damit auf ein Problem mit 0 Damen zurückführen, was nichts anderes als ein leeres Schachbrett ist.
Diese Herangehensweise ist wesentlich effizienter als ein naiver Brute Force-Algorithmus, der alle 648 = 248 möglichen Positionierungen von acht Damen durchprobiert und dabei alle Stellungen ausfiltert, in denen zwei Damen sich schlagen könnten. Dieser schlechte Algorithmus hat außerdem den Nebeneffekt, dass er mehrfach die gleichen Resultate berechnet und ausgibt, da die meisten Lösungen wie oben beschrieben lediglich durch Symmetrie aus einer anderen abgeleitet werden. Ein etwas verbesserter Brute Force-Algorithmus platziert in jeder Reihe nur eine Dame und reduziert die Komplexität dadurch auf nur noch 88 = 224 mögliche Stellungen.
Das Damenproblem wird oft auch als Beispiel-Problem für andere unorthodoxe Herangehensweisen genommen, z. B. Logische Programmierung oder Genetische Algorithmen.
Siehe auch
Weblinks
(alle bisher hier aufgeführten Seiten sind auf Englisch)
Links zu Lösungen