Eine Lösung des Acht-Damen-Problems

Das Damenproblem ist eine Denksportaufgabe: Man finde eine Stellung für acht Damen auf einem Schachbrett , derart 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.

Das Problem kann auf Schachbretter beliebiger Größe verallgemeinert werden. Dann gilt es, 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, wenn man die sich durch Spiegelung oder Rotation des Brettes ergebenden Lösungen mitzählt).

Geschichte

Erstmals formuliert wurde das Damenproblem von dem bayrischen Schachmeister Max Bezzel (1824-1871). In der "Berliner Schachzeitung" fragte er 1848 nach der Anzahl der möglichen Lösungen. Als erster nannte 1850 Dr. Franz Nauck in der "Leipziger Illustrierten Zeitung" die korrekte Zahl 92. Auch Carl Friedrich Gauß zeigte Interesse an dem Problem, weshalb es irrtümlich häufig auf ihn zurückgeführt wird.

Nauck verallgemeinerte die Problemstellung und fragte, auf wie viele verschiedene Arten man n Damen auf einem nxn-Schachbrett aufstellen könne.

Symmetrische eindeutige Lösung, sorgt für 92 statt 96 verschiedene Lösungen

1991 wurde von B. Bernhardsson eine explizite Lösung des N-Damenproblems für jede beliebige Brettgröße im ACM SIGART Bulletin, Vol. 2, No. 7 angegeben.

Im Jahre 1992 fanden Demirörs, Rafraf und Tanik eine Äquivalenz zwischen magischen Quadraten und Damenproblemen.

Das Damenproblem tauchte auch in The 7th Guest auf, einem Computerspiel aus den 1990er Jahren.

Zählen aller Lösungen

Das klassische Problem mit 8 Damen hat 92 verschiedene Lösungen. Wenn man solche, die durch Drehen oder Spiegeln des Brettes aufeinander abgebildet werden, nur einfach zählt, bleiben 12 eindeutige Lösungen übrig. Da es für jede dieser reduzierten Lösungen 4 Spiegelungen (an Diagonalen, Horizontale und Vertikale durch die Brettmitte) und 4 Rotationen gibt, könnte man eine Gesamtzahl von 8*12=96 Lösungen vermuten. Da aber eine der Lösungen (siehe Diagramm) bei einer Drehung um 180° in sich selbst übergeht, lassen sich aus dieser nur 4 verschiedene Lösungen konstruieren und es ergeben sich insgesamt 92 Lösungen. Die folgende Tabelle führt die Anzahl der einfachen Lösungen bis zur Brettgröße 15×15 und die der gesamten Lösungen bis zur Brettgröße 24×24 auf:

Allgemein lässt sich feststellen, dass die Anzahl der Lösungen etwas schneller als exponentiell mit der Brettgröße anwächst. Interessanterweise gibt es auf dem 6×6-Brett weniger Lösungen als auf dem 5×5-Brett.

Algorithmen zur Lösungssuche

Das Damenproblem ist ein gutes Beispiel für ein einfach zu formulierendes Problem mit nicht trivialen Lösungen. Eine Reihe von Programmiertechniken sind geeignet, alle Lösungen zu erzeugen: klassisch ist rekursives Backtracking ; dieses ist besonders einfach zu realisieren mit logischer Programmierung . Eine weitere Möglichkeit sind genetische Algorithmen .

Derartige Ansätze sind wesentlich effizienter als ein naiver Brute Force -Algorithmus, der (im 8×8 Fall) alle 64*63*62*61*60*59*58*57 (knapp 64⁸ = 2⁴⁸) möglichen Positionierungen der acht Damen durchprobiert und dabei alle Stellungen ausfiltert, in denen zwei Damen sich schlagen könnten. Dieser Algorithmus erzeugt mehrfach die gleichen Lösungen, wenn Permutationen der Damen gleiche Felder besetzen.

Ein effizienterer Brute Force-Algorithmus platziert in jeder Reihe nur eine Dame und reduziert dadurch die Komplexität auf 8⁸ = 2²⁴ mögliche Stellungen.

Rekursives Backtracking

Das Damenproblem ist ein gutes Beispiel für ein einfaches, 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.

Das folgende Python -Programm findet alle Lösungen des n-Damenproblems mit Hilfe eines rekursiven Algorithmus. Ein n×n-Brett wird dabei rekursiv auf kleinere Bretter mit geringerer Anzahl an Reihen, n×n-1, n×n-2, ... reduziert. Das Programm nutzt direkt aus, dass keine zwei Damen in der gleichen Reihe stehen. Außerdem wird benutzt, dass eine Lösung mit n-1 Damen auf einem n×n-1-Brett auf jeden Fall eine Lösung mit n-2 Damen auf einem n×n-2-Brett enthalten muss. (In anderen Worten, wenn man die untere (oder obere) Reihe der Teillösung eines n×n-1-Bretts entfernt, bleiben n-2 Damen auf einem n×n-2-Brett übrig, die wiederum eine Teillösung auf dem n×n-2-Brett darstellen.)

Der Algorithmus konstruiert also alle Lösungen aus den Lösungen eines jeweils kleineren Brettes. Da sichergestellt wird, dass die Teillösungen auf den kleinen Brettern konfliktfrei sind, spart dieser Algorithmus das Ãœberprüfen vieler Stellungen. Insgesamt werden für das 8×8-Brett nur 15720 Stellungen überprüft.

# Erzeuge eine Liste von Lösung auf einem Brett mit
# reihen und spalten.
# Eine Lösung wird durch eine Liste der Spaltenpositionen,
# indiziert durch die Reihennummer, angegeben.
# Die Indizes beginnen mit Null.
def damenproblem( reihen, spalten ):
    if reihen == 0:
        return [[]] # Eine Lösung, keine Damen auf dem nicht-existierenden Brett
    else:
        return eine_dame_dazu(reihen-1, spalten , damenproblem(reihen-1, spalten ))

# Probiere alle Spalten, in denen für eine gegebene Teilloesung
# eine Dame in "neue_reihe" gestellt werden kann.
# Wenn kein Konflikt mit der Teilloesung auftritt,
# ist eine neue Loesung des um eine Reihe erweiterten
# Bretts gefunden.
def eine_dame_dazu(neue_reihe, spalten, vorherige_loesungen):
    neue_loesungen = []
    for loesung in vorherige_loesungen:
        # Versuche, eine Dame in jeder Spalte von neue_reihe einzufegen.
        for neue_spalte in range(spalten):
            # print 'Versuch: ', neue_spalte, ' in Reihe ', neue_reihe
            if kein_konflikt( neue_reihe, neue_spalte, loesung ):
                # Kein Konflikte, also ist dieser Versuch eine Loesung.
                neue_loesungen.append( loesung + [neue_spalte] )
    return neue_loesungen

# Kann eine Dame in neu_Spalte in neue_reihe gestellt werden,
# ohne dass sie eine der schon stehenden Damen schlagen kann?
def kein_konflikt( neue_reihe, neue_spalte, loesung ):
    # Stelle sicher, dass die neue Dame mit keiner der existierenden
    # Damen auf einer Spalte oder Diagonalen steht.
    for reihe in range(neue_reihe):
        if ( loesung[reihe]         == neue_spalte              or  # Gleiche Spalte
             loesung[reihe] + reihe == neue_spalte + neue_reihe or  # Gleiche Diagonale
             loesung[reihe] - reihe == neue_spalte - neue_reihe):   # Gleiche Diagonale
                return 0
    return 1

for loesung in damenproblem( 8, 8 ):
   print loesung 

Dieser rekursiv programmierte Algorithmus kann leicht in einen nicht-rekursiven umgewandelt werden.

Constraintprogrammierung

Die Constraintprogrammierung über endliche Bereiche kann eine Aufgabe wie das Damenproblem sehr kompakt formulieren. Das folgende Prologprogramm findet schnell eine Lösung auch für große Schachbretter.

/* Dieses Prädikat erzeugt eine Liste, die eine einzige Lösung darstellt.
   Es ist sichergestellt, dass jeder Wert zwischen 1 und N genau einmal auftritt. */
n_damen(N,Ls) :- length(Ls,N),
               fd_domain(Ls,1,N),
               fd_all_different(Ls),
               _damen(Ls),
               fd_labeling(Ls,[variable_method(random)]).

/* Dieses Prädikat stellt sicher,
   dass alle Stellungen die Lösungsbedingungen erfuellen */
constraint_damen([]).
constraint_damen([X|Xs]) :- nicht_schlagen(X,Xs,1), constraint_damen(Xs).

/* Mit diesem Prädikat wird sichergestellt,
   dass zwei Damen nicht auf einer Diagonalen stehen */
nicht_schlagen(_,[],_).
nicht_schlagen(X,[Y|Xs],N) :- X#\=Y+N, X#\=Y-N, T#=N+1, nicht_schlagen(X,Xs,T).

Andere Methoden

Ein 'iterativer Reparaturalgorithmus' beginnt mit einer beliebigen Stellung der Damen auf dem Brett. Es zählt dann die Anzahl der Konflikte, und versucht, durch Umpositionieren der Damen die Anzahl der Konflikte zu reduzieren. Effizient ist etwa, die Dame mit den meisten Konflikten senkrecht auf die Position zu verschieben, auf der die geringste Anzahl von Konflikten auftritt. Mit dieser Methode kann das 1.000.000-Damenproblem, ausgehend von einer "vernünftigen" Versuchsposition gelöst werden. Derart große Bretter lassen sich mit expliziten Konstruktionsalgorithmen nicht lösen; allerdings kann der Iterationsalgorithmus nicht mit Sicherheit eine Lösung finden.

Verwandte Problemstellungen

Andere Figuren

Das Problem kann auch für andere Schachfiguren (König, Läufer, Springer, Turm) formuliert werden.

Eine weitere Verallgemeinerung des Problems stellt das N-Superdamenproblem dar. Superdamen dürfen wie Damen und Springer ziehen. Es ist nicht klar, wer Superdamen oder das N-Superdamenproblem erfunden hat. In Mathematische Knobeleien, Vieweg-Verlag (1973) erwähnt Martin Gardner eine Schachvariation in der mit einer Superdame gespielt wird. Gardner nennt diese Figur dort Maharadscha. Andere kennen sie als Amazone .

Auch die Frage, auf wieviele Arten sich n Superdamen auf einem n x n Schachbrett bedrohungsfrei platzieren lassen, wurde bereits untersucht. Für n = 1 ... 19 lauten die Lösungen 1, 0, 0, 0, 0, 0, 0, 0, 0, 4, 44, 156, 1876, 5180, 32516, 202900, 1330622, 8924976, 64492432

Seit 2001 existiert auch für das N-Superdamenproblem eine explizite Lösung von Frank Schwellinger. Ein Javascriptprogramm, welches zu beliebigen Brettgrößen jeweils eine explizite Lösung ausgibt, findet sich unter [1] .

Andere Brettgeometrie

George Pólya betrachtete das Damenproblem auf einem torusförmigen Brett. Auch dreidimensionale Verallgemeinerungen wurden untersucht.

Andere Aufgabenstellung

Für ein n×n Schachbrett, bestimme die Dominanzzahl, das ist die Mindestzahl an Damen, die ausreicht, jedes Feld des Brettes zu beherrschen. Auf dem 8×8-Brett reichen 5 Damen aus.

Das 9-Damenproblem verlangt, auf einem 8×8-Brett neun Damen und einen Bauern derart unterzubringen, dass die Damen sich nicht gegenseitig schlagen können. Dieses Problem kann wiederum auf belebige Brettgröße und eine höhere Anzahl von Bauern verallgemeinert werden.

Siehe auch

• Schachproblem
• Funktionale Programmierung
• Backtracking

Literatur

• Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press. ISBN 0-691-11503-6 .
• http://www.liacs.nl/home/kosters/nqueens.html Walter Koster's Literaturliste (englisch)

Weblinks

(alle bisher hier aufgeführten Seiten sind auf Englisch)

• http://bridges.canterbury.ac.nz/features/eight.html
• http://mathworld.wolfram.com/QueensProblem.html MathWorld Artikel
• http://www.durangobill.com/N_Queens.html Durango Bill's N-Damen-Seite
• http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html - Anleitungen zur Constraintprogrammierung

Weblinks zu Lösungen

• http://www.atarimagazines.com/v3n12/Queens8.html Atari BASIC
• http://www.scdi.org/%7eavernet/projects/jaskell/queens/ Haskell/Java hybrid
• http://www.math.utah.edu/%7Ealfeld/queens/queens.html Java
• http://www.dcs.ed.ac.uk/home/mlj/demos/queens/ Standard ML
• http://www.ijon.de/comp/programme/damen/damen_de.html ANSI-C
• http://www.faust.fr.bw.schule.de/mhb/backtrack/achtdamen/eight.htm - Finde eine Lösung
• http://www.jsomers.com/nqueen_demo/nqueens.html J. Somers N-Damen-Programm
• http://www.dossier-andreas.net/ai/ga.html - Genetische Algorithmen
• http://www.geocities.com/quirkasaurus/queens8/index.html - Quirkasaurus' 8-Damenlösung
• http://www.muljadi.org/EightQueens.htm - Zahlenfolgen
• http://8damen.liebhard.net/ -Javabasierend

Dieser Artikel wurde in die Liste der Lesenswerten Artikel aufgenommen.