Information Technology Reference
In-Depth Information
(a) Zugmöglichkeiten einer Dame
(b) Eine Lösung des 8-Damen-Problems
Abbildung 10.1: Zugmöglichkeiten einer Dame und eine Lösung des 8-Damen-
Problems
Wie wahrscheinlich bekannt ist, kann das
n
-Damen-Problem leicht mit Hilfe des
Backtracking-Algorithmus gelöst werden. Dafür platzieren wir die Damen zeilen-
weise, also von unten nach oben. Alternativ könnten wir sie auch spaltenweise, lies
von links nach rechts, platzieren. Jede Zeile wird dann wie folgt bearbeitet:
• Wir setzen in einer Zeile eine Dame der Reihe nach, von links nach rechts, auf
die Felder der Zeile.
• Für jede Platzierung der Dame prüfen wir, ob es zu einer Kollision mit Damen
in tieferliegenden Zeilen kommt.
•
Ist dies nicht der Fall, bearbeiten wir rekursiv die nächste Zeile.
• Anschließend rücken wir die Dame ein Feld weiter nach rechts.
Können wir eine Dame in der obersten Zeile des Brettes platzieren, ohne dass es zu
einer Kollision kommt, geben wir die gefundene Lösung aus. Dieser Algorithmus
entspricht demnach einer Tiefensuche (engl.
depth first search
).
Ist nur eine Lösung (lies eine Platzierung der Damen) von Interesse, so können
wir die Positionen für alle
n
>
3wiefolgtberechnen:
• Falls
n
ungerade ist (
n
mod 2
=
1), dann setzen wir eine Dame auf
(
n
1,
n
1
)
und verringern
n
um 1.
• Falls
n
mod 6 = 2, dann setzen wir die Damen in den Zeilen
y
= 0, . . . ,
2
1
in die Spalten
x
= 2
y
+1unddieDamenindenZeilen
y
=
2
,...,
n
1indie
Spalten
x
= 2
y
n
.
• Falls
n
mod 6
=
2, dann setzen wir die Damen in den Zeilen
y
=
0, . . . ,
2
1in
die Spalten
x
=(
2
y
+
2
)
mod
n
und die Damen in den Zeilen
y
=
2
,...,
n
1
in die Spalten
x
=(
2
y
2
+
2
)
mod
n
.
