Das Damenproblem

Das Damenproblem ist ein gutes Beispiel für ein einfach zu formulierendes Problem mit nicht-trivialen Lösungen.

wikipedia

Das Damenproblem ist eine schachmathematische Aufgabe.

Es sollen jeweils acht Damen auf einem Schachbrett so aufgestellt werden, dass keine zwei Damen einander gemäß ihren in den Schachregeln definierten Zugmöglichkeiten schlagen können.

Die Figurenfarbe wird dabei ignoriert, und es wird angenommen, dass jede Figur jede andere angreifen könnte. Solcherart auf dem Schachbrett angeordnete Figuren werden auch als „unabhängig“ bezeichnet.

Für Damen heißt dies konkret und anders ausgedrückt: Es dürfen keine zwei Damen auf derselben Reihe, Linie oder Diagonale stehen.

Das Problem kann auf quadratische Schachbretter beliebiger Größe verallgemeinert werden: Dann gilt es, n unabhängige Damen auf einem Brett von n × n Feldern zu positionieren (mit n als Parameter aus den natürlichen Zahlen n ∈ ℕ .

Motivation

  1. abstrakte Abbildung von realen "Dingen"
    - Dame
    - Schachbrett
    - Spiel (Dame mit Schachbrett verbinden)
  2. Zustände festhalten
    - alle Lösungen
  3. Höhere Basistypen
    - Arrays
    - Maps
    - Sets
  1. Rekursion
    - Funktionen die sich selbst wieder aufrufen.
    - Parameter werden angepasst (aktuelle Tiefe, …).
    - Abbruchbedingung ist essentiell (→ Endlosschleife).
  2. Duplikate finden
    - Spiegelsymetrie
    - Rotationssymmetrie
  3. Didaktik
    - Umsetzten und erlernen von etwas Unbekanntem

Das Spielbrett

8
7
6
5
4
3
2
1
A B C D E F G H

Das Spielbrett: Datentyp

7 56 57 58 59 60 61 62 63
6 48 49 50 51 52 53 54 55
5 40 41 42 43 44 45 46 47
4 32 33 34 35 36 37 38 39
3 24 25 26 27 28 29 30 31
2 16 17 18 19 20 21 22 23
1 8 9 10 11 12 13 14 15
0 0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7

multidimensionales Array

Das Spielbrett

2 6 7 8
1 3 4 5
0 0 1 2
0 1 2

im Speicher mit Größe n=3 und Index f

feld 0 1 2 3 4 5 6 7 8
x,y 0,0 1,0 2,0 0,1 1,1 2,1 0,2 1,2 2,2

Array

Das Spielbrett

feld 0 1 2 3 4 5 6 7 8
x,y 0,0 1,0 2,0 0,1 1,1 2,1 0,2 1,2 2,2

im Speicher mit Größe n=3 und Index f

f = n × y + x = 3 × 2 + 1 = 5

x
y
=
f mod n
⌊f / n⌋
=
f - (n × y)
(f - x) / n
=
5 - (3 × 1)
(5 - 2) / 3
=
5 - 3
3 / 3
=
2
1

Welche Felder bedroht eine Dame

7
6
5
4
3 ♕
2
1
0
0 1 2 3 4 5 6 7

Welche Felder bedroht eine Dame

7 b1 c1
6
5 d2
4
3 a2 ♕ a1
2
1 c2
0 b2 d1
0 1 2 3 4 5 6 7

Geraden

a1)
2
3
…
7
3
+
1
0

a2)
2
3
…
0
3
-
1
0
b1)
2
3
…
2
7
+
0
1

b2)
2
3
…
2
0
-
0
1
c1)
2
3
…
6
7
+
1
1

c2)
2
3
…
0
1
-
1
1
d1)
2
3
…
5
0
+
1
-1

d2)
2
3
…
0
5
-
1
-1

Welche Felder bedroht eine Dame

Mit durchgehenden Geraden

7 b
6
5 d
4
3 a ♕
2
1 c
0
0 1 2 3 4 5 6 7

Geraden

x1
y1
…
x2
y2
+
Δx
Δy
m = n - 1 = 8 - 1 = 7
ma = min(x, m-y) = min(2, 7-3) = min(2, 4) = 2
mb = min(y, m-x) = min(3, 7-2) = min(3, 5) = 3
mc = min(x, y) = min(2, 3) = 2
md = min(m-x, m-y) = min(7-2, 7-3) = min(5, 4) = 4
a)
0
y
…
m
y
+
1
0
→
0
3
…
7
3
+
1
0
b)
x
0
…
x
m
+
0
1
→
2
0
…
2
7
+
0
1
c)
x-mc
y-mc
…
x+md
y+md
+
1
1
→
2-2
3-2
…
2+4
3+4
+
1
1
→
0
1
…
6
7
+
1
1
d)
x-ma
y+ma
…
x+mb
y-mb
+
1
-1
→
2-2
3+2
…
2+3
3-3
+
1
-1
→
0
5
…
5
0
+
1
-1

Lösungansatz

recursive backtracking

  1. Rekursiv Funktionen die sich selbst mit veränderten Parametern aufrufen
  2. Backtracking Algorithmus der ohne Datenverlust einen Schritt zurückgehen kann
  3. Optimierungen
    1. Setze pro Spalte nur eine Dame (88 ≈ 16 Millionen)
      Nachteil: kann nicht ohne Änderungen für Springer und Läufer angewendet werden
    2. Ist ein Dame am rechten Rand angekommen gehe einen weiteren Schritt zurück (≈ 1 Million)

Beschreibung

  1. Start Setze ein Dame auf das erste Feld
  2. Schritt
    1. Damen setzten Gehe die Felder der Reihe nach durch, bis zum nächsten Feld ohne Bedrohung und setzte die nächste Dame.
    2. Backtracking
      • Sind noch nicht alle Damen gesetzt, aber kein Feld mehr frei, nimm die letzte Dame vom Brett und wiederhole den oberen Schritt.
      • Ist eine Dame am rechten Rand angekommen nimm eine weiter Damen vom Brett und wiederhole den oberen Schritt.
  3. weitere Lösungen Sind alle Damen gesetzt, speichere die Lösung ab, nimm die letzte Dame aus dem Spiele und wiederhole die oberen Schritte.
  4. Beendung des Algorithmus Ist die erste Dame auf dem letzten Feld, ist die Suche beendet.

Showcase

8
7
6
5
4
3
2
1
A B C D E F G H

Die Anzahl der Möglichkeiten

Brute Force

= 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57
= n2 × (n2-1) × (n2-3) × (n2-4) × (n2-5) × (n2-6) × (n2-7)
=
n2! / (n2-n)!
=
64! / 56!

≈ 179 Billionen

Anzahl für optimierte Lösung

 88 ≈ 16 Millionen

Anzahl für größere Bretter

 8:  64! / 56!  = 2 × 1014
 9:  81! / 72!  = 9 × 1016
10: 100! / 90!  = 6 × 1019
11: 121! / 110! = 5 × 1022
12: 144! / 132! = 4 × 1025

Anzahl der Lösungen

92 Lösungen

12 indiviudelle Lösungen

{H, V, D1, D2, 0°, 90° 180° 270°} × 12 = 8 × 12 = 96

ein Lösung ist Rotationsidentisch

12 × 8 - 4 = 96 - 4 = 92

Spiegel-symetrische Lösungen

7
6 ♛
5 ♛
4
3
2 ♛ ♛
1 ♛
0
0 1 2 3 4 5 6 7 
m = n - 1 = 8 - 1 = 7

Horizontal

xm
ym
→
x
m-y
=
1
7-2
=
1
5

Vertikal

xm
ym
→
m-x
y
=
7-1
2
=
6
2

Hauptdiagonale

xm
ym
→
y
x
=
1
2
→
2
1

Nebendiagonale

xm
ym
→
m-y
m-x
=
7-2
7-1
=
5
6

Rotations-symetrische Lösungen

4i
3i ♛
2i ♛
1i
-1i
-2i ♛
-3i ♛
-4i
-4 -3 -2 -1 1 2 3 4

Drehen

0° → 90° → 180° → 270°

Wie drehen? → Komplexe Zahlen

Komplexe Zahlen

i = -1 → i2 = -1

Nullpunkt justieren

m =
n - 1 / 2
=
8 - 1 / 2
=
7 / 2
= 3,5 → ⌈3,5⌉ = 4
a = x - m = 1 - 4 = -3
bi = (y - m)i = (2 - 4)i = -2i
a + bi = -3 -2i

Drehung durchführen

a+bi
→ ×i =
-b+ai
→ ×i =
-a-bi
→ ×i =
b-ai
→ ×i =
a+bi
-3-2i
→ ×i =
2-3i
→ ×i =
3+2i
→ ×i =
-2+3i
→ ×i =
-3-2i

Nullpunkt re-justieren

x = Re(a + m)
y = Im(b + m)

The Game

iterations
game
8
7
6
5
4
3
2
1
A B C D E F G H
solutions