Damenproblem

Auf diesem Schachproblem basierte ein in frühen 1990er Jahren bekanntes Computerspiel The 7th Guest . Das Problem wurde heute dahingehend generalisiert 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 Stück wenn man die sich durch Spiegelung Rotation des Brettes ergebenden Lösungen mitzählt).

Inhaltsverzeichnis

1 Das Damenproblem als Beispiel zum Algorithmen-Design 2 Siehe auch 3 Weblinks 3.1 Links zu Lösungen

Das Damenproblem als Beispiel zum Algorithmen-Design

Diese Herangehensweise ist wesentlich effizienter als naiver Brute Force -Algorithmus der alle 64 ⁸ = 2 ⁴⁸ möglichen Positionierungen von acht Damen durchprobiert dabei alle Stellungen ausfiltert in denen zwei sich schlagen könnten. Dieser schlechte Algorithmus hat den Nebeneffekt dass er mehrfach die gleichen berechnet und ausgibt da die meisten Lösungen oben beschrieben lediglich durch Symmetrie aus einer abgeleitet werden. Ein etwas verbesserter Brute Force-Algorithmus in jeder Reihe nur eine Dame und die Komplexität dadurch auf nur noch 8 ⁸ = 2 ²⁴ mögliche Stellungen.

Das Damenproblem wird oft auch als für andere unorthodoxe Herangehensweisen genommen z. B. Programmierung oder Genetische Algorithmen .

Siehe auch

• Schachproblem
• Funktionale Programmierung

Weblinks

• http://bridges.canterbury.ac.nz/features/eight.html

Links zu Lösungen

• Atari BASIC
• Haskell/Java hybrid
• Java
• Standard ML
• ANSI-C

Bücher zum Thema Damenproblem

Dieser Artikel von Wikipedia unterliegt der GNU FDL.